Polygon Queries for Convex Hulls of Points

Abstract

We study the following range searching problem: Preprocess a set $P$ of $n$ points in the plane with respect to a set $\mathcal{O}$ of $k$ orientations % , for a constant, in the plane so that given an $\mathcal{O}$-oriented convex polygon $Q$, the convex hull of $P\cap Q$ can be computed efficiently, where an $\mathcal{O}$-oriented polygon is a polygon whose edges have orientations in $\mathcal{O}$. We present a data structure with $O(n{k}^3{\log }^{2}n)$ space and $O(n{k}^3{\log }^{2}n)$ construction time, and an $O(h+s{\log }^{2}n)$-time query algorithm for any query $\mathcal{O}$-oriented convex $s$-gon $Q$, where $h$ is the complexity of the convex hull. Also, we can compute the perimeter or area of the convex hull of $P\cap Q$ in $O(s{\log }^{2}n)$ time using the data structure.