×

On the zone of a surface in a hyperplane arrangement. (English) Zbl 0773.52007

For a collection of \(n\) hyperplanes in \(\mathbb{R}^ d\) the complex of all open cells and their lower dimensional faces is called an arrangement. The collection of all those cells which are met by a set \(\sigma\) is called its zone and its complexity is the number of all the faces. Asymptotic estimates for the complexity are given the simplest, for the case that \(\sigma\) is the boundary of a convex set or an algebraic surface, is \(O(n^{d-1}\log n)\).
Reviewer: E.Heil (Darmstadt)

MSC:

52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Agarwal, P. K.; Matoušek, J., On range searching with semialgebraic sets, No. 629, 1-13 (1992), Berlin · Zbl 1493.68366
[2] B. Aronov, J. Matoušek, and M. Sharir, On the sum of squares of cell complexities in hyperplane arrangements,Proc. 7th Symp. on Computational Geometry, 1991, pp. 307-313. · Zbl 0799.52009
[3] B. Aronov and M. Sharir, On the zone of a surface in a hyperplane arrangement,Proc. 2nd Workshop on Algorithms and Data Structures, Ottawa, 1991, pp. 13-19. · Zbl 0764.68166
[4] B. Aronov and M. Sharir, Castles in the air revisited,Proc. 8th Symp. on Computational Geometry, 1992, pp. 146-156. · Zbl 0805.52005
[5] Bern, M.; Eppstein, D.; Plassman, P.; Yao, F.; Goodman, J. (ed.); Pollack, R. (ed.); Steiger, W. (ed.), Horizon theorems for lines and polygons, No. 6, 45-66 (1991), Providence RI · Zbl 0733.68082
[6] M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld, Efficient ray shooting and hidden surface removal,Proc. 7th Symp. on Computational Geometry, 1991, pp. 21-30. · Zbl 0813.68160
[7] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[8] H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, Arrangements of curves in the plane: Topology, combinatorics, and algorithms,Proc. 15th Internat. Colloq. on Automata, Languages and Programming, 1988, pp. 214-229. · Zbl 0649.68040
[9] H. Edelsbrunner, R. Seidel, and M. Sharir, On the zone theorem for hyperplane arrangements,SIAM J. Computing, to appear. · Zbl 0778.52007
[10] B. Grünbaum,Convex Polytopes, Wiley, New York, 1967. · Zbl 0163.16603
[11] M. E. Houle and T. Tokuyama, On zones of flats in hyperplane arrangements, Technical Report 92-3, Department of Information Science, Faculty of Science, University of Tokyo, April 1992.
[12] J. Milnor, On the Betti numbers of real varieties,Proc. Amer. Math. Soc.15 (1964), 275-280. · Zbl 0123.38302 · doi:10.1090/S0002-9939-1964-0161339-9
[13] M. Pellegrini, Combinatorial and algorithmic analysis of stabbing and visibility problems in 3-dimensional space, Ph.D. Thesis, Courant Institute, New York University, February 1991.
[14] M. Pellegrini, Ray-shooting and isotopy classes of lines in 3-dimensional space,Proc. 2nd Workshop on Algorithms and Data Structures, Ottawa, 1991, pp. 20-31. · Zbl 0765.68212
[15] M. Pellegrini, On the zone of a codimensionp surface in a hyperplane arrangement,Proc. 3rd Canadian Conference on Computational Geometry, Vancouver, 1991, pp. 233-238.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.