License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.69
URN: urn:nbn:de:0030-drops-122275
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12227/
Wang, Haitao
Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments
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.
BibTeX - Entry
@InProceedings{wang:LIPIcs:2020:12227,
author = {Haitao Wang},
title = {{Algorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {69:1--69:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12227},
URN = {urn:nbn:de:0030-drops-122275},
doi = {10.4230/LIPIcs.SoCG.2020.69},
annote = {Keywords: subpath hull queries, convex hulls, compact interval trees, ray-shooting, data structures}
}
|
Keywords: |
|
subpath hull queries, convex hulls, compact interval trees, ray-shooting, data structures |
|
Collection: |
|
36th International Symposium on Computational Geometry (SoCG 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
08.06.2020 |
