HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Parabola separation queries and their application to stone throwing

Abstract : Given two sets $A$ and $B$ of $m$ non-crossing line segments in the plane, we show how to compute in $O(m \log m)$ time a data structure that uses $O(m)$ 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 $O(n \log n)$ storage and $O(n \log^{2} n)$ preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Friday, November 20, 2009 - 4:57:00 PM
Last modification on : Thursday, January 20, 2022 - 4:16:34 PM
Long-term archiving on: : Thursday, June 17, 2010 - 7:05:15 PM


Files produced by the author(s)




Otfried Cheong, Hazel Everett, Hyo-Sil Kim, Sylvain Lazard, René Schott. Parabola separation queries and their application to stone throwing. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2007, 17 (4), pp.349-360. ⟨10.1142/S0218195907002379⟩. ⟨inria-00434090⟩



Record views


Files downloads