The complexity and construction of many faces in arrangements of lines and of segments. (English) Zbl 0691.68035

The authors show that the number of edges of m faces of an arrangement of n lines in the plane is \(0(m^{2/3-\delta}n^{2/3+2\delta}+n)\) for any \(\delta >0\). This bound is slightly weaker than a tight bound \(\theta (m^{2/3}n^{2/3}+n)\), obtained in another paper by the same authors in a companion paper with K. Clarkson and E. Welzl. The slightly weaker result presented here is a introduction to the more complex case of segments, where the first non-trivial upper bound known for the maximum number of edges of m faces is given.
The approach to the combinatorial problem of the paper is also different from previous work in that it has an algorithmic flavor. The algorithm in the case of lines uses randomization and its expected time complexity is \(0(m^{2/3-\delta}n^{2/3+2\delta}\log n+n \log n \log m)\). In the case of line segments an randomized algorithm is also given. The technique used uses \(\epsilon\)-nets and random sampling as basic tools.
Reviewer: H.-D.Hecker


68Q25 Analysis of algorithms and problem complexity
51D20 Combinatorial geometries and geometric closure systems
Full Text: DOI EuDML


[1] Agarwal, P. K. An efficient algorithm for partitioning arrangements of lines and its applications. InProc. 5th ACM Symp. Comput. Geom., 1989, pp. 11-22.
[2] Aronov, B., Edelsbrunner, H., Guibas, L., and Sharir, M. Improved bounds on the number of edges of many faces in arrangements of line segments. Report UIUCDCS-R-89-1527, Department of Computer Science, University of Illinois, Urbana, Illinois, 1989.
[3] Aronov, B., and Sharir, M. Triangles in space, or: Building (and analyzing) castles in the air. InProc. 4th ACM Symp. Comput. Geom., 1988, pp. 381-391. · Zbl 0717.68099
[4] Bentley, J. L., and Ottmann, T. A. Algorithms for reporting and counting geometric intersections.IEEE Trans. Comput.28 (1979), 643-647. · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[5] Canham, R. J. A theorem on arrangements of lines in the plane.Isreal J. Math.7 (1969), 393-397. · Zbl 0204.55205 · doi:10.1007/BF02788872
[6] Chazelle, B., and Dobkin, D. P. Intersection of convex objects in two and three dimensions.J. Assoc. Comput. Mach.34 (1987), 1-27. · doi:10.1145/7531.24036
[7] Clarkson, K. New applications of random sampling in computational geometry.Discrete Comput. Geom.2 (1987), 195-222. · Zbl 0615.68037 · doi:10.1007/BF02187879
[8] Clarkson, K., Edelsbrunner, H., Guibas, L. J., Sharir, M., and Welzl, E. Combinatorial complexity bounds for arrangements of curves and spheres.Discrete Comput. Geom., this issue, 99-160. · Zbl 0704.51003
[9] Cole, R., Sharir M., and Yap, C. K. Onk-hulls and related problems.SIAM J. Comput.16 (1987), 61-77. · Zbl 0637.68074 · doi:10.1137/0216005
[10] Edelsbrunner, H.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[11] Edelsbrunner, H., Guibas, L. J., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., and Welzl, E. Implicitly representing arrangements of lines or segments.Discrete Comput. Geom.4 (1989), 433-466. · Zbl 0688.68031 · doi:10.1007/BF02187742
[12] Edelsbrunner, H., Guibas, L. J., and Sharir, M. The complexity of many cells in arrangements of planes and related problems.Discrete Comput. Geom., this issue, 197-216. · Zbl 0691.68036
[13] Edelsbrunner, H., Guibas, L. J., and Stolfi, J. Optimal point location in a monotone subdivision.SIAM J. Comput.15 (1986), 317-340. · Zbl 0602.68102 · doi:10.1137/0215023
[14] Edelsbrunner, H., O’Rourke, J., and Seidel, R. Constructing arrangements of lines and hyperplanes with applications.SIAM J. Comput.15 (1986), 341-363. · Zbl 0603.68104 · doi:10.1137/0215024
[15] Edelsbrunner, H., and Sharir, M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n − 2.Discrete Comput. Geom.5 (1990), 35-42. · Zbl 0712.52009 · doi:10.1007/BF02187778
[16] Edelsbrunner, H., and Welzl, E. On the maximal number of edges of many faces in an arrangement.J. Combin. Theory Ser. A41 (1986), 159-166. · Zbl 0585.52002 · doi:10.1016/0097-3165(86)90078-6
[17] Edelsbrunner, H., and Welzl, E. Halfplanar range search in linear space andO(n0.695) query time.Inform. Process. Lett.23 (1986), 289-293. · Zbl 0634.68064 · doi:10.1016/0020-0190(86)90088-8
[18] Grünbaum, B.Convex Polytopes. Wiley, London, 1967. · Zbl 0163.16603
[19] Guibas, L. J., Overmars, M. H., and Sharir, M. Counting and reporting intersections in arrangements of line segments. Tech. Report 434, Computer Science Department, NYU, 1989.
[20] Guibas, L. J., Sharir, M., and Sifrony, S. On the general motion planning problem with two degrees of freedom. InProc. 4th ACM Symp. Comput. Geom., 1988, pp. 289-298. · Zbl 0685.68049
[21] Hart, S., and Sharir, M. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes.Combinatorica6 (1986), 151-177. · Zbl 0636.05003 · doi:10.1007/BF02579170
[22] Haussler, D., and Welzl, E. Epsilon-nets and simplex range queries.Discrete Comput. Geom.2 (1987), 127-151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[23] Moise, E. E.Geometric Topology in Dimension 2 and 3. Springer-Verlag, New York, 1977. · Zbl 0349.57001 · doi:10.1007/978-1-4612-9906-6
[24] O’Rourke, J. The signature of a plane curve.SIAM J. Comput.15 (1986), 34-51. · Zbl 0611.68061 · doi:10.1137/0215003
[25] Pollack, R., Sharir, M., and Sifrony, S. Separating two simple polygons by a sequence of translations.Discrete Comput. Geom.3 (1988), 123-136. · Zbl 0646.68052 · doi:10.1007/BF02187902
[26] Preparata, F. P., and Shamos, M. I.Computational Geometry—An Introduction. Springer-Verlag, New York, 1985. · Zbl 0759.68037
[27] Schmitt, A.; Müller, H.; Leister, W.; Earnshaw, R. A. (ed.), Ray tracing algorithms—theory and practice, No. F40, 997-1030 (1988), Berlin · doi:10.1007/978-3-642-83539-1_42
[28] Szemerédi, E., and Trotter, W. T. Extremal problems in discrete geometry.Combinatorica3 (1983), 381-392. · Zbl 0541.05012 · doi:10.1007/BF02579194
[29] Wiernik, A., and Sharir, M. Planar realization of nonlinear Davenport-Schinzel sequences by segments.Discrete Comput. Geom.3 (1988), 15-47. · Zbl 0636.68043 · doi:10.1007/BF02187894
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.