Document Open Access Logo

Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments

Author Haitao Wang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.69.pdf
  • Filesize: 492 kB
  • 14 pages

Document Identifiers

Author Details

Haitao Wang
  • Department of Computer Science, Utah State University, Logan, UT 84322, USA

Cite As Get BibTex

Haitao Wang. Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.69

Abstract

In this paper, we first consider the subpath convex hull query problem: Given a simple path π of n vertices, preprocess it so that the convex hull of any query subpath of π can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90'] proposed a data structure of O(n) space and O(log n log log n) query time; reducing the query time to O(log n) increases the space to O(nlog log n). We present an improved result that uses O(n) space while achieving O(log n) query time. Like the previous work, our query algorithm returns a compact interval tree representing the convex hull so that standard binary-search-based queries on the hull can be performed in O(log n) time each. Our new result leads to improvements for several other problems.
In particular, with the help of the above result, we present new algorithms for the ray-shooting problem among segments. Given a set of n (possibly intersecting) line segments in the plane, preprocess it so that the first segment hit by a query ray can be quickly found. We give a data structure of O(n log n) space that can answer each query in (√n log n) time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to O(n). All these are classical problems that have been studied extensively. Previously data structures of Õ(√n) query time were known in early 1990s; nearly no progress has been made for over two decades. For all problems, our results provide improvements by reducing the space of the data structures by at least a logarithmic factor while the preprocessing and query times are the same as before or even better.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Computational geometry
Keywords
  • subpath hull queries
  • convex hulls
  • compact interval trees
  • ray-shooting
  • data structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. P.K. Agarwal. Ray shooting and other applications of spanning trees with low stabbing number. SIAM Journal on Computing, 21:540-570, 1992. Google Scholar
  2. P.K. Agarwal and M. Sharir. Applications of a new space-partitioning technique. Discrete and Computational Geometry, 9(1):11-38, 1993. Google Scholar
  3. R. Bar-Yehuda and S. Fogel. Variations on ray shootings. Algorithmica, 11:133-145, 1994. Google Scholar
  4. B. Becker, P.G. Franciosa, S. Gschwind, S. Leonardi, T. Ohler, and P. Widmayer. Enclosing a set of objects by two minimum area rectangles. Journal of Algorithms, 21:520-541, 1996. Google Scholar
  5. B. Becker, P.G. Franciosa, S. Gschwind, T. Ohler, T. Ohler, G. Thiemt, and P. Widmayer. An optimal algorithm for approximating a set of rectangles by two minimum area rectangles. In Workshop on Computational Geometry, pages 13-25, 1991. Google Scholar
  6. T.M. Chan. Optimal partition trees. Discrete and Computational Geometry, 47:661-690, 2012. Google Scholar
  7. B. Chazelle and L. Guibas. Fractional cascading: II. Applications. Algorithmica, 1(1):163-191, 1986. Google Scholar
  8. B. Chazelle and E. Welzl. Quasi-optimal range searching in spaces of finite VC-dimension. Discrete and Computational Geometry, 4(5):467-489, 1989. Google Scholar
  9. D.Z. Chen, J. Li, and H. Wang. Efficient algorithms for the one-dimensional k-center problem. Theoretical Computer Science, 592:135-142, 2015. Google Scholar
  10. D.Z. Chen and H. Wang. Approximating points by a piecewise linear function. Algorithmica, 88:682-713, 2013. Google Scholar
  11. S.W. Cheng and R. Janardan. Algorithms for ray-shooting and intersection searching. Journal of Algorithms, 13:670-692, 1992. Google Scholar
  12. T. Christ, M. Hoffmann, Y. Okamoto, and T. Uno. Improved bounds for wireless localization. Algorithmica, 57:499-516, 2010. Google Scholar
  13. B.-S. Dai, M.-J. Kao, and D.T. Lee. Optimal time-convex hull under the L_p metrics. In Proceedings of the 13rd Algorithms and Data Structures Symposium (WADS), pages 268-279, 2013. Google Scholar
  14. J. Driscoll, N. Sarnak, D. Sleator, and R.E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989. Google Scholar
  15. H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl. Implicitly representing arrangements of lines or segments. Discrete and Computational Geometry, 4:433-466, 1989. Google Scholar
  16. H. Edelsbrunner and E. Welzl. Halfplanar range search in linear space and O(n^0.695) query time. Information Processing Letters, 23:289-293, 1986. Google Scholar
  17. R.L. Graham and F.F. Yao. Finding the convex hull of a simple polygon. Journal of Algorithms, 4:324-331, 1983. Google Scholar
  18. L. Guibas, J. Hershberger, and J. Snoeyink. Compact interval trees: A data structure for convex hulls. International Journal of Computational Geometry and Applications, 1(1):1-22, 1991. First appeared in SODA 1990. Google Scholar
  19. L. Guibas, M. Overmars, and M. Sharir. Intersecting line segments, ray shooting, and other applications of geometric partitioning techniques. In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT), pages 64-73, 1988. Google Scholar
  20. J. Matoušek. Efficient partition trees. Discrete and Computational Geometry, 8(3):315-334, 1992. Google Scholar
  21. J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete and Computational Geometry, 10(1):157-182, 1993. Google Scholar
  22. A. Melkman. On-line construction of the convex hull of a simple polygon. Information Processing Letters, 25:11-12, 1987. Google Scholar
  23. M.H. Overmars, H. Schipper, and M. Sharir. Storing line segments in partition trees. BIT Numerical Mathematics, 30:385-403, 1990. Google Scholar
  24. H. Wagener. Optimal parallel hull construction for simple polygons in O(log log n) time. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), pages 593-599, 1992. Google Scholar
  25. H. Wang and W. Zhang. On top-k weighted sum aggregate nearest and farthest neighbors in the L₁ plane. International Journal of Computational Geometry and Applications, 29:189-218, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact