On the complexity of halfspace area queries

ABSTRACT

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.

REFERENCES

• 1: K.-F. B.ohringer, B.R. Donald and D. Halperin. On the area bisectors of a polygon Discrete and Computational Geometry, 22(1999), 269-285.
• 2: R. Boland and J. Urrutia. Polygon Area Problems. Proc. of the 12th Canadian Conf. on Computational Geometry, Fredericton, NB, Canada, 2000.
• 3: F. Contreras-Alcala. Cutting polygons and a problem on illumination of stages. Masters thesis, Dept. Comp. Sci. University of Ottawa, Ottawa, ON, Canada, 1998. http://www.csi.uottawa.ca/~fhca/thesis/
• 4: Open Problems Session. Twelfth Computational Geometry Day, 1997. Courant Institute, NYU, New York, USA.
• 5: R. Guardia and F. Hurtado. On the equipartitions of convex bodies and convex polygons. 16th European Workshop on Computational Geometry, Eilat, Israel, 2000.
• 6: John Iacono , Stefan Langerman, Volume Queries in Polyhedra, Revised Papers from the Japanese Conference on Discrete and Computational Geometry, p.156-159, November 22-25, 2000
• 7: Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 8: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory