Abstract
We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n λ), whereγ=log2(1+���5)−1≈0.695. The techniques are fairly simple and easy to understand.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agarwal, P. K.,An efficient deterministic algorithm for partitioning arrangements of lines and its applications, Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 11–22.
Agarwal, P. K.,Ray shooting and other applications of spanning trees with low stabbing number, Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 315–325.
Chazelle, B.,Polytope range searching and integral geometry, Proc. 28th IEEE Symp. on Foundations of Computer Science, 1987, pp. 1–10.
Chazelle, B.,A functional approach to data structures and its use in multidimensional searching, SIAM J. Comput. 17 (1988), pp. 427–462.
Chazelle, B. and L. Guibas,Visibility and intersection problems in plane geometry, Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 135–146.
Chazelle, B. and E. Welzl,Quasi optimal range searching in spaces with finite VC-dimension, Discrete Comput. Geom. 4 (1989), pp. 467–490.
Dobkin, D. and H. Edelsbrunner,Space searching for intersecting objects, J. Algorithms 8 (1987), pp. 348–361.
Edelsbrunner, H.,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987.
Edelsbrunner, H., L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink and E. Welzl,Implicitly representing arrangements of lines and of segments, Discrete Comput. Geom. 4 (1989), pp. 433–466.
Edelsbrunner, H. and E. Welzl,Halfplanar range search in linear space and O(n 0.695)query time, Inform. Proc. Lett. 23 (1986), pp. 289–293.
Guibas, L., J. Hershberger, D. Leven, M. Sharir and R. Tarjan,Linear time algorithms for visibility and shortest path problems in triangulated simple polygons, Algorithmica 2 (1987), pp. 209–233.
Guibas, L., M. H. Overmars and M. Sharir,Intersecting line segments, ray shooting and other applications of geometric partitioning techniques, Proc. SWAT88, Lect. Notes in Comp. Science 318, Springer-Verlag, Heidelberg, 1988, pp. 64–73.
Guibas, L., M. H. Overmars and M. Sharir,Ray shooting, implicit point location, and related queries in arrangements of segments, Techn. Rep. 433, Courant Inst. of Math. Sciences, New York University, 1989.
Guibas, L., M. Sharir and S. Sifrony,On the general motion planning problem with two degrees of freedom, Discrete Comput. Geom. 4 (1989), pp. 491–522.
Haussler, D. and E. Welzl,ε-nets and simplex range searching, Discrete Comput. Geom. 2 (1987), pp. 127–151.
Matoušek, J.,Construction of ε-nets, Proc. 5th ACM Symp. on Computational Geometry, 1989, pp. 1–10.
McCreight, E. M.,Priority search trees, SIAM J. Comput. 14 (1985), pp. 257–276.
Pollack, R., M. Sharir and S. Sifrony,Separating two simple polygons by a sequence of translations, Discrete Comput. Geom. 3 (1988), pp. 123–136.
Preparata, F. and M. Shamos,Computational Geometry: An Introduction, Springer-Verlag, Heidelberg, 1985.
Schipper, H. and M. H. Overmars,Dynamic partition trees, Proc. SWAT 90, Springer-Verlag, Heidelberg, 1990, to appear.
Tarjan, R. and C. Van Wyk,An O(n log logn)algorithm for triangulating simple polygons, SIAM J. Comput. 17 (1988), pp. 143–178.
Welzl, E.,Partition trees for triangle counting and other range searching problems, Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 23–33.
Wiernik, A. and M. Sharir,Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete Comput. Geom. 3 (1988), pp. 15–47.
Willard, D. E.,Polygon retrieval, SIAM J. Comput. 11 (1982), pp. 149–165.
Author information
Authors and Affiliations
Additional information
Research of the first author was partially supported by the ESPRIT II Basic Research Action of the EC under contract No. 3075 (Project ALCOM).
Work by the third author has been supported in part by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the Digital Equipment Corporation, the IBM Corporation, the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.