On the complexity of halfspace area queries
Stefan Langerman · 2001
Given a non convex simple polygon $P$, is it possible to construct a d ata structure which after preprocessing can answer halfspace area queries (i.e. given a line, determine the area of the portion of the polygon above the line) in $o(n)$ time? We answer negatively, proving a $\Omega(n)$ lower bound on the query time of any data structure performing this task. We then consider the batched version of the same problem: given a polygon $P$ with $n$ vertices, and $k$ query lines, we present an algorithm that computes the area of $P$ on both sides of each line in $O^{*}(n^{3/5}k^{4/5}+n+k)$ time. Variants of our method allow the query of a collection of weighted polygons with or without holes, and solve several other related problems within the same time bounds.