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

.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 [Int. J. Comput. Geom. Appl., 1 (1991), pp. 1–22; first appeared in SODA 1990] proposed a data structure of \(O(n)\) space and \(O(\log n\log \log n)\) query time; they also reduced the query time to \(O(\log n)\) by increasing the space to \(O(n\log \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. The preprocessing time of our data structure is \(O(n)\) after the vertices of \(\pi\) are sorted by \(x\) -coordinate. As the subpath convex hull query problem has many applications, our new result leads to improvements for several other problems. In particular, with the help of the above result, along with other techniques, 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 \((\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)\) . As a by-product, given a set of \(n\) (possibly intersecting) segments in the plane, we build a data structure of \(O(n)\) space that can determine whether a query line intersects a segment in \(O(\sqrt{n}\log n)\) time. The preprocessing time is \(O(n^{1.5})\) for all four problems, which can be reduced to \(O(n\log n)\) time by a randomized algorithm so that the query time is bounded by \(O(\sqrt{n}\log n)\) with high probability. All these are classical problems that have been studied extensively. Previously data structures of \(\widetilde{O}(\sqrt{n})\) query time were known in the early 1990s (the notation \(\widetilde{O}\) suppresses a polylogarithmic factor); nearly no progress has been made for more than two decades. For all these problems, our new 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.Keywordssubpath hull queriesconvex hullscompact interval treesray-shootingMSC codes68Q2568W4068U0565D18