H. Edelsbrunner
J. Hershberger
ABSTRACT
An arrangement of n lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists of Ο(n2) regions, called faces. In this paper we study the problem of calculating and storing arrangements implicitly, using subquadratic space and preprocessing, so that, given any query point p, we can calculate efficiently the face containing p. First, we consider the case of lines and show that with Λ(n) space1 and Λ(n3/2) preprocessing time, we can answer face queries in Λ(√n) + Ο(K) time, where K is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: 1) given a set of n points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, 2) given a simple polygonal path Γ, form a data structure from which we can find the convex hull of any subpath of Γ quickly, and 3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a trade-off between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in Λ(n1/3) time, given Λ(n4/3) space and Λ(n5/3) preprocessing time.
Lastly, we note that our techniques allow us to compute m faces in an arrangement of n lines in time Λ(m2/3n2/3 + n), which is nearly optimal.
- AS87.Boris Aronov and Micha Sharir. Triangles in space, or building and analyzing castles in the air. 1987. Manuscript.Google Scholar
- BO79.Jon L. Bentley and Thomas A. Ottman. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28(9):643-647, 1979.Google ScholarDigital Library
- Bro80.K.Q. Brown. Geometric Transforms for Fast Geometric Algorithms. PhD thesis, Carnegie-Mellon University, 1980. Google ScholarDigital Library
- CE87.Bernard Chazelle and Herbert Edelsbrunner. A fast algorithm for line segment intersection and its extensions. Manuscript, 1987.Google Scholar
- CEG*88.Ken Clarkson, Herbert Edelsbrunner, Leo Guibas, Micha Sharir, and Emo Welzl. 1988. In preparation.Google Scholar
- CG85.B. Chazelle and L. Guibas. Visibility and intersection problems in plane geometry. In Proceedings of the A CM Symposium on Computational Geometry, pages 135-146, ACM, 1985. Submitted to Discrete and Computational Geometry. Google ScholarDigital Library
- CG86.B. Chazelle and L. J. Guibas. Fractional cascading: II. applications. Algorithmica, 1:163-191, 1986.Google ScholarCross Ref
- CGL85.B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality. BIT, 25:76-90, 1985. Google ScholarDigital Library
- Cla87.Ken Clarkson. New applications of random sampling in computational geometry. Discrete and Computational Geometry, 2:195-222, 1987.Google ScholarDigital Library
- Ede87.Herbert Edelsbrunner. Algorithms in Combinatorial Geometry. Volume 10 of EA TCS Monographs on Theoretical Computer Science, Springer-Verlag, 1987. Google ScholarDigital Library
- EGP*87.Herbert Edelsbrunner, Leonidas Guibas, Janos Pach, Richard Pollack, Raimund Seidel, and Micha Sharir. Arrangements of curves in the plane: topology, combinatorics~ and algorithms. 1987. Manuscript.Google Scholar
- EGS86.H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15:317-340, 1986. Published earlier as DEC/SRC report number 2. Google ScholarDigital Library
- EGS87.Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir. The complexity of many faces in arrangements of lines and of segments. 1987. Manuscript.Google Scholar
- EOS86.H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput., 15:341-363, 1986. Google ScholarDigital Library
- EW86.Herbert Edelsbrunner and Emo Welzl. Halfplanar range search in linear space and O(n~'695) query time. Information Processing Letters, 23:289-293, 1986. Google ScholarDigital Library
- GH87.Leonidas Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. In Proceedings of the 3rd ACM Symposium on Computational Geometry, pages 50-63, ACM, June 1987. Google ScholarDigital Library
- GHS88.Leo Guibas, John Hershberger, and Jack Snoeyink. Bridge trees: a data structure for convex hulls. 1988. In preparation.Google Scholar
- GOS87.Leonidas Guibas, Mark Overmars, and Micha Sharir. Intersections, connectivity, and related problems for arrangements of line segments. 1987. Manuscript.Google Scholar
- HW87.David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. Discrete and Computational Geometry, 2:127-151, 1987.Google ScholarDigital Library
- Kir83.David Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12:28-35, 1983.Google ScholarDigital Library
- KLPS86.K. Kedem, R. Livne, J. Pach, and M. Sharir. On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete and Computational Geometry, 1(1):59-71, 1986. Google ScholarDigital Library
- Knu73.Donald E. Knuth. Sorting and Searching. Volume 3 of The Art of Computer Programming, Addison-Wesley, 1973.Google Scholar
- OvL81.M. Overmars and H. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166-204, 1981.Google ScholarCross Ref
- PS85.F.P. Preparata and M. I. Shamos. Computational Geometry. Springer Verlag, New York, 1985. Google ScholarDigital Library
- SH76.M.I. Shaznos and D. Hoey. Geometric intersection problems. In Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, pages 208-215, IEEE, 1976.Google Scholar
- ST86.Neil Sarnak and Robert E. Tarjan. Planar point location using persistent search trees. Communications of the A CM, 29:669-679, 1986. Google ScholarDigital Library
- Wel88.Emo Welzl. Partition trees for triangle counting and other range searching problems. In Proceedings of the 4th A CM Symposium on Computational Geometry, ACM, June 1988. Google ScholarDigital Library
- Wil82.D.E. Willard. Polygon retrieval. SIAM J. Comput., 11:149-165, 1982.Google ScholarDigital Library
Index Terms
- Implicitly representing arrangements of lines or segments
Recommendations
Implicitly representing arrangements of lines or segments
Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n2) regions, calledfaces. In this paper we study the problem of calculating and storing ...
Partitioning arrangements of lines II: Applications
In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m2/3n2/3 log2/3n log /3 (...
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 ...
Comments