In this paper, we first consider the subpath convex hull query problem: Given a simple path $pi$ of $n$ vertices, preprocess it so that the convex hull of any query subpath of $pi$ can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90] proposed a data structure of $O(n)$ space and $O(log nloglog n)$ query time; reducing the query time to $O(log n)$ increases the space to $O(nloglog 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(nlog n)$ space that can answer each query in $(sqrt{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 $widetilde{O}(sqrt{n})$ query time (the notation $widetilde{O}$ suppresses a polylogarithmic factor) 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.
Download