H. Edelsbrunner
ABSTRACT
We show that the total number of edges of m faces of an arrangement of n lines in the plane is Ο(m2/3-δ n2/3+2δ + n), for any δ > 0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of these m faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and, with high probability, its time complexity is within a log2n factor of the above bound. If instead of lines we have an arrangement of n line segments, then the maximum number of edges of m faces is Ogr;(m2/3-δn2/3+2δ + nα(n)logm), for any δ > 0, where α(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and, with high probability, takes time that is within a log2n factor of the combinatorial bound.
- Ca.Canham, R. J. A theorem on arrangements of lines in the plane, israel j. Math. 7 (1969), 393-397.Google Scholar
- CD.Chazelle, B. and Dobkin, D. P. Intersection of convex objects in two and three dimensions. J. Assoc. Comput. Math. 34 (1987), 1-27. Google ScholarDigital Library
- Cl.Clarkson, K. New applications of random sampling in computational geometry. Discrete Comput. Geom. 2 (1987), 195- 222.Google ScholarDigital Library
- CEGSW.Clarkson, K., Edelsbrunner, H., Guibas, L. J., Sharir, M. and Welzl, E. Complexity bounds for arrangements. In preparation.Google Scholar
- CSY.Cole, R., Sharir M. and Yap, C. K. On k-hulls and related problems. SIAM J. Comput. 16 (1987), 61-77. Google ScholarDigital Library
- Ed.Edelsbrunner, H. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987. Google ScholarDigital Library
- EGSh.Edelsbrunner, H., Guibas, L. J. and Sharir, M. The complexity of many cells in arrangements of planes and related problems. In preparation.Google Scholar
- ES.Edelsbrunner, H. and Sharir, M. The maximum number of ways to stab n convex non-intersecting objects in the plane is 2n -2. To appear in Discrete Comput. Geom.Google Scholar
- EW.Edelsbrunner, H. and Welzl, E. On the maximal number of edges of many faces in an arrangement. J. Combin. Theory, 5er. A 41 (1986), 159-166. Google ScholarDigital Library
- EW2.Edelsbrunner, H. and Welzl, E. Halfplanar range search in linear space and O(n~'695) query time. Inform. Process, Letl. 23 (1986), 289-293. Google ScholarDigital Library
- Gr.Grfinbaum, B. Convex Polytopes. John Wiley & Sons, Lon. don, 1967.Google Scholar
- GOS.Guibas, L. J., Overmars, M.H. and Sharir, M. Intersections, connectivity, and related problems for arrangements of line segments. In preparation.Google Scholar
- GSS.Guibas, L. J., Sharir, M. and Sifrony, S. On general motion planning problems with two degrees of freedom. In "Proc. 4'h ACM Syrup. Comput. Geom. 1988". Google ScholarDigital Library
- HS.Hart, S. and Sharir, M. Nonlinearity of Davenport Schinzel sequences and of generalized path compression schemes. Combinatorica 6 (1986), 151-177. Google ScholarDigital Library
- HW.Haussler, D. and Welzl, E. Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2 (1987), 127-151.Google ScholarDigital Library
- OR.O'Rourke, J. The signature of a plane curve. SIAM J. Comput. 15 (1986), 34-51. Google ScholarDigital Library
- PSS.Pollack, R., Sharir, M. and Sifrony, S. Separating two simple polygons by a sequence of translations. Discrete Corn- . put. Geom. 3 (1988), 123-136.Google ScholarDigital Library
- PS.Preparata, F. P. and Shamos, M. I. Computational Geometry - an Introduction. Springer-Verlag, New York, 1985. Google ScholarDigital Library
- SML.Schmitt, A., Muller, H. and Leister, W. Ray tracing algorithms - theory and practice. In Theoretical Foundations of Computer Graphics and CAD (R.A. Earnshaw, Ed.), NATO ASI Series, Vol. F40, Springer Verlag, Berlin, 1988, 997-1030.Google ScholarCross Ref
- ST.Szemerbti, E. and Trotter, W. T. Extremal problems in discrete geometry. Combinatorica 3 (1983), 381-392.Google ScholarCross Ref
- WS.Wiernik, A. and Sharir, M. Planar realization of nonlinear Davenport Schinzel sequences by segments. Discrete Comput. Geom. 3 (1988), 15-47. Google ScholarDigital Library
Index Terms
- The complexity of many faces in arrangements of lines of segments
Recommendations
The complexity and construction of many faces in arrangements of lines and of segments
We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m2/3 n2/3+2 +n) for any >0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper ...
Computing many faces in arrangements of lines and segments
SCG '94: Proceedings of the tenth annual symposium on Computational geometryWe present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. The main new idea is a simple randomized O(nlogn) ...
Comments