Abstract
We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5−δ n 4/5+2δ+m+n logm), for anyδ>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m 3/4−δ n 3/4+3δ+m) log2 n+n logn logm) for anyδ>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m 3/4−δ n 3/4+3δ+m] log2 n+n logn logm) for anyδ>0. (v) The maximum number of facets (i.e., (d−1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m 2/3 n d/3 logn+n d−1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. K. Agarwal, Intersection and decomposition algorithms for arrangements of curves in the plane, Ph.D. Dissertation, Computer Science Department, New York University, June 1989.
B. Aronov and M. Sharir, Triangles in space, or: Building and analyzing castles in the air,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 381–391.
R. J. Canham, A theorem on arrangements of lines in the plane,Israel J. Math. 7 (1969), 393–397.
B. Chazelle, How to search in history,Inform. and Control 64 (1985), 77–99.
K. Clarkson, A probabilistic algorithm for the post office problem,Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 75–84.
K. Clarkson, New applications of random sampling in computational geometry,Discrete Comput. Geom. 2 (1987) 195–222.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 568–579. (Also,Discrete Comput. Geom., this issue, 99–160.)
D. Dobkin and D. Kirkpatrick, Fast detection of polyhedral intersections,Theoret. Comput. Sci. 27 (1983), 241–253.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
H. Edelsbrunner, The upper envelope of piecewise linear functions: Tight bounds on the number of faces,Discrete Comput. Geom. 4 (1989), 337–343.
H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl, Implicitly representing arrangements of lines or segments,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 56–69. (Also,Discrete Comput. Geom. 4, (1989), 433–466.)
H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity of many faces in arrangements of lines or segments,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 44–55. (Also,Discrete Comput. Geom., this issue, 161–196.)
H. Edelsbrunner and D. Haussler, The complexity of cells in three-dimensional arrangements,Discrete Math. 60 (1986), 139–146.
H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341–363.
H. Edelsbrunner and E. Welzl, On the maximal number of edges of many faces in an arrangement,J. Combin. Theory Ser. A 41 (1986), 159–166.
D. Haussler and E. Welzl, Epsilon-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127–151.
F. P. Preparata and D. E. Muller, Finding the intersection ofn half space in timeO(n logn),Theoret. Comput. Sci. 8 (1979), 44–55.
G. Purdy and P. Erdős, Some extremal problems in combinatorial geomery, manuscript, 1987.
E. Szemerédi and W. T. Trotter, Extremal problems in discrete geometry,Combinatorica 3 (1983), 381–392.
Author information
Authors and Affiliations
Additional information
Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.
Rights and permissions
About this article
Cite this article
Edelsbrunner, H., Guibas, L. & Sharir, M. The complexity of many cells in arrangements of planes and related problems. Discrete Comput Geom 5, 197–216 (1990). https://doi.org/10.1007/BF02187785
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187785