article
Implicitly representing arrangements of lines or segments
published
Herbert
Edelsbrunner
author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833
Leonidas
Guibas
author
John
Hershberger
author
Raimund
Seidel
author
Micha
Sharir
author
Jack
Snoeyink
author
Emo
Welzl
author
Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn 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 tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.
Springer1989
Discrete & Computational Geometry10.1007/BF02187742
41433 - 466
yes
Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete & Computational Geometry</i>. Springer, 1989. <a href="https://doi.org/10.1007/BF02187742">https://doi.org/10.1007/BF02187742</a>.
H. Edelsbrunner <i>et al.</i>, “Implicitly representing arrangements of lines or segments,” <i>Discrete & Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 433–466, 1989.
Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M, Snoeyink J, Welzl E. 1989. Implicitly representing arrangements of lines or segments. Discrete & Computational Geometry. 4(1), 433–466.
Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., & Welzl, E. (1989). Implicitly representing arrangements of lines or segments. <i>Discrete & Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187742">https://doi.org/10.1007/BF02187742</a>
Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete & Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 433–66, doi:<a href="https://doi.org/10.1007/BF02187742">10.1007/BF02187742</a>.
Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements of lines or segments. <i>Discrete & Computational Geometry</i>. 1989;4(1):433-466. doi:<a href="https://doi.org/10.1007/BF02187742">10.1007/BF02187742</a>
H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl, Discrete & Computational Geometry 4 (1989) 433–466.
40882018-12-11T12:06:52Z2021-01-12T07:54:25Z