Parabola separation queries and their application to stone throwingReport as inadecuate

Parabola separation queries and their application to stone throwing - Download this document for free, or read online. Document in PDF available to download.

1 KAIST - Department of Electrical Engineering Korea Advanced Institute of Science and Technology 2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications 3 IECN - Institut Élie Cartan de Nancy

Abstract : Given two sets $A$ and $B$ of $m$ non-crossing line segments in the plane, we show how to compute in $Om \log m$ time a data structure that uses $Om$ storage and supports the following query in $O\log m$ time: Given a parabola $\p: y = ax^{2} + bx + c$, does $\p$ separate $A$ and $B$? This structure can be used to build a data structure that stores a simple polygon and allows ray-shooting queries along parabolic trajectories with vertical main axis. For a polygon of complexity~$n$, we can answer such ``stone-throwing- queries in $O\log^{2} n$ time, using $On \log n$ storage and $On \log^{2} n$ preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.

keyword : Ray shooting simple polygon parabola separation queries parabolic arc

Author: Otfried Cheong - Hazel Everett - Hyo-Sil Kim - Sylvain Lazard - René Schott -



Related documents