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.; Ottmann, T. A., Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., 28, 643-647, (1979) · Zbl 0414.68074
[5] Canham, R. J., A theorem on arrangements of lines in the plane, Isreal J. Math., 7, 393-397, (1969) · Zbl 0204.55205
[6] Chazelle, B.; Dobkin, D. P., Intersection of convex objects in two and three dimensions, J. Assoc. Comput. Mach., 34, 1-27, (1987)
[7] Clarkson, K., New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 195-222, (1987) · Zbl 0615.68037
[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.; Yap, C. K., On \(k\)-hulls and related problems, SIAM J. Comput., 16, 61-77, (1987) · Zbl 0637.68074
[10] Edelsbrunner, H.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001
[11] Edelsbrunner, H.; Guibas, L. J.; Hershberger, J.; Seidel, R.; Sharir, M.; Snoeyink, J.; Welzl, E., Implicitly representing arrangements of lines or segments, Discrete Comput. Geom., 4, 433-466, (1989) · Zbl 0688.68031
[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.; Stolfi, J., Optimal point location in a monotone subdivision, SIAM J. Comput., 15, 317-340, (1986) · Zbl 0602.68102
[14] Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, 341-363, (1986) · Zbl 0603.68104
[15] Edelsbrunner, H.; Sharir, M., The maximum number of ways to stab \(n\) convex nonintersecting sets in the plane is \(2n \)− 2, Discrete Comput. Geom., 5, 35-42, (1990) · Zbl 0712.52009
[16] Edelsbrunner, H.; Welzl, E., On the maximal number of edges of many faces in an arrangement, J. Combin. Theory Ser. A, 41, 159-166, (1986) · Zbl 0585.52002
[17] Edelsbrunner, H.; Welzl, E., Halfplanar range search in linear space and \(O(n0.695)\) query time, Inform. Process. Lett., 23, 289-293, (1986) · Zbl 0634.68064
[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.; Sharir, M., Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177, (1986) · Zbl 0636.05003
[22] Haussler, D.; Welzl, E., Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2, 127-151, (1987) · Zbl 0619.68056
[23] Moise, E. E.Geometric Topology in Dimension 2 and 3. Springer-Verlag, New York, 1977. · Zbl 0349.57001
[24] O’Rourke, J., The signature of a plane curve, SIAM J. Comput., 15, 34-51, (1986) · Zbl 0611.68061
[25] Pollack, R.; Sharir, M.; Sifrony, S., Separating two simple polygons by a sequence of translations, Discrete Comput. Geom., 3, 123-136, (1988) · Zbl 0646.68052
[26] Preparata, F. P., and Shamos, M. I.Computational Geometry—An Introduction. Springer-Verlag, New York, 1985.
[27] Schmitt, A.; Müller, H.; Leister, W.; Earnshaw, R. A. (ed.), Ray tracing algorithms—theory and practice, No. F40, 997-1030, (1988), Berlin
[28] Szemerédi, E.; Trotter, W. T., Extremal problems in discrete geometry, Combinatorica, 3, 381-392, (1983) · Zbl 0541.05012
[29] Wiernik, A.; Sharir, M., Planar realization of nonlinear Davenport-Schinzel sequences by segments, Discrete Comput. Geom., 3, 15-47, (1988) · Zbl 0636.68043
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.