Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments
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. …