Parabola separation queries and their applicationto 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 gamma : y = ax(2) + bx + c, does gamma 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 "such-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.