Implicitly representing arrangements of lines or segments. (English) Zbl 0688.68031

Line arrangements, i.e. partitions of the plane by lines find numerous applications in computational geometry. However their full representation of size \(O(n^ 2)\) is sometimes excessive. The paper deals with the basic problem of face queries: given a query point p one has to retrieve the face containing p. Via geometric duality the latter problem is transformed into one of its own interest: given a planar pointset for any query line find convex hulls of points on both sides of it quickly. The paper presents algorithms with subquadratic space and preprocessing and sublinear face query time for arrangements of lines and line segments. A tradeoff for space vs. query time is also shown possible via random sampling method. Some other related problems are also considered.
Reviewer: N.Korneenko


68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
68U99 Computing methodologies and applications
Full Text: DOI EuDML


[1] B. Aronov and M. Sharir. Triangles in space, or building and analyzing castles in the air. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 381-391, ACM, June 1988. · Zbl 0717.68099
[2] J. L. Bentley and T. A. Ottman. Algorithms for reporting and counting geometric intersections.IEEE Transactions on Computers, 28(9):643-647, 1979. · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[3] K. Q. Brown. Geometric Transforms for Fast Geometric Algorithms. Ph.D. thesis, Carnegie-Mellon University, 1980.
[4] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. InProceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 590-600, IEEE, 1988. · Zbl 0799.68191
[5] B. Chazelle and L. Guibas. Visibility and intersection problems in plane geometry. InProceedings of the ACM Symposium on Computational Geometry, pages 135-146, ACM, 1985. Submitted toDiscrete and Computational Geometry. · Zbl 0695.68033
[6] B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications.Algorithmica, 1:163-191, 1986. · Zbl 0639.68057 · doi:10.1007/BF01840441
[7] B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality.BIT, 25:76-90, 1985. · Zbl 0603.68072 · doi:10.1007/BF01934990
[8] B. Chazelle and E. Welzl. Range searching and VC-dimension: a characterization of efficiency. 1988. Manuscript. · Zbl 0681.68081
[9] K. Clarkson. New applications of random sampling in computational geometry.Discrete and Computational Geometry, 2:195-222, 1987. · Zbl 0615.68037 · doi:10.1007/BF02187879
[10] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arrangements of curves and surfaces. InProceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 568-579, IEEE, 1988. · Zbl 0704.51003
[11] H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, Volume 10, Springer-Verlag, Berlin, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[12] H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement. InProceedings of the 18th ACM Symposium on Theory of Computing, pages 389-403, ACM, May 1986. · Zbl 0676.68013
[13] H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir. Arrangements of curves in the plane: Topology, combinatorics, and algorithms. InProceedings of the 15th ICALP, 1988. · Zbl 0649.68040
[14] H. Edelsbrunner, L. J. Guibas, and M. Sharir. The complexity of many faces in arrangements of lines and of segments. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 44-55, ACM, June 1988. · Zbl 0691.68035
[15] H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision.SIAM Journal on Computing, 15:317-340, 1986. · Zbl 0602.68102 · doi:10.1137/0215023
[16] H. Edelsbrunner, J. O’Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM Journal on Computing, 15:341-363, 1986. · Zbl 0603.68104 · doi:10.1137/0215024
[17] H. Edelsbrunner and E. Welzl. Halfplanar range search in linear space andO(n0 695) query time.Information Processing Letters, 23:289-293, 1986. · Zbl 0634.68064 · doi:10.1016/0020-0190(86)90088-8
[18] L. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. InProceedings of the 3rd ACM Symposium on Computational Geometry, pages 50-63, ACM, June 1987. · Zbl 0681.68065
[19] L. Guibas, J. Hershberger, and J. Snoeyink. Bridge trees: a data structure for convex hulls. 1989. In preparation. · Zbl 0800.68953
[20] Guibas, L.; Overmars, M.; Sharir, M., Interesting line segments, ray shooting, and other applications of geometric partitioning techniques, No. 318, 64-73 (1988), Berlin · Zbl 0651.68058
[21] D. Haussler and E. Welzl. Epsilon-nets and simplex range queries.Discrete and Computational Geometry, 2:127-151, 1987. · Zbl 0619.68056 · doi:10.1007/BF02187876
[22] D. Kirkpatrick. Optimal search in planar subdivisions.SIAM Journal on Computing, 12:28-35, 1983. · Zbl 0501.68034 · doi:10.1137/0212002
[23] D. E. Knuth.Sorting and Searching. The Art of Computer Programming, Volume 3, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[24] J. Matoušek. Spanning trees with low crossing number. 1988. Manuscript. · Zbl 0732.68100
[25] M. Overmars and H. van Leeuwen. Maintenance of configurations in the plane.Journal of Computer and System Sciences, 23:166-204, 1981. · Zbl 0474.68082 · doi:10.1016/0022-0000(81)90012-X
[26] F. P. Preparata and M. I. Shamos.Computational Geometry. Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[27] N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees.Communications of the ACM, 29:669-679, 1986. · doi:10.1145/6138.6151
[28] M. I. Shamos and D. Hoey. Geometric intersection problems. InProceedings of the 17th IEEE Symposium on Foundations of Computer Science, pages 208-215, IEEE, 1976.
[29] E. Welzl. Partition trees for triangle counting and other range searching problems. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 23-33, ACM, June 1988.
[30] D. E. Willard. Polygon retrieval.SIAM Journal on Computing, 11:149-165, 1982. · Zbl 0478.68060 · doi:10.1137/0211012
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.