Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments
Haitao Wang · SIAM Journal on Computing · 2024
Abstract. In this paper, we first consider the subpath convex hull query problem: Given a simple path [Formula: see text] of [Formula: see text] vertices, preprocess it so that the convex hull of any query subpath of [Formula: see text] 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 [Formula: see text] space and [Formula: see text] query time; they also reduced the query time to [Formula: see text] by increasing the space to [Formula: see text]. We present an improved result that uses [Formula: see text] space while achieving [Formula: see text] 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 [Formula: see text] time each. The preprocessing time of our data structure is [Formula: see text] after the vertices of [Formula: see text] are sorted by [Formula: see text]-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 [Formula: see text] (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 [Formula: see text] space that can answer each query in [Formula: see text] time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to [Formula: see text]. As a by-product, given a set of [Formula: see text] (possibly intersecting) segments in the plane, we build a data structure of [Formula: see text] space that can determine whether a query line intersects a segment in [Formula: see text] time. The preprocessing time is [Formula: see text] for all four problems, which can be reduced to [Formula: see text] time by a randomized algorithm so that the query time is bounded by [Formula: see text] with high probability. All these are classical problems that have been studied extensively. Previously data structures of [Formula: see text] query time were known in the early 1990s (the notation [Formula: see text] 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.