We study the following range searching problem: Preprocess a set P of n points in the plane with respect to a set O of k orientations in the plane so that given an O-oriented convex polygon Q as a query, the convex hull of P ∩ Q, and its perimeter and area, can be reported efficiently, where an O-oriented polygon is a polygon whose edges have orientations in O. We present a data structure with O(nk~3 log~2 n) space and O(nk~3 log~2 n) construction time, and a query algorithm to compute the perimeter or area of the convex hull of P ∩ Q in O(s log~2 n) time for any query O-oriented convex s-gon Q. For reporting the convex hull, O(h) is added to the running times of query algorithms, where h is the complexity of the convex hull.
展开▼
