PARABOLA SEPARATION QUERIES AND THEIR APPLICATION TO STONE THROWING
Otfried Cheong, Hazel Everett, Hyo-Sil Kim, Sylvain Lazard, René Schott · International Journal of Computational Geometry & Applications · 2007
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 γ : y = ax2 + bx + c, does γ 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.