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 "stone-throwing" queries in $O(log^2 n)$ time, using O(n log n) storage and $O(n log^2n)$ preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.
이 논문은 각각 m개의 선분을 원소로 가진 집합 A, B가 주어지고 선분들 사이에 끝점을 제외한 교차점이 존재하지 않을 때, $'y=ax^2+bx+c$ 의 식으로 표현된 포물선 $\gamma$가 A와 B를 분리시키는가'라는 질의의 답을 O(log m) 시간에 찾아주는 자료 구조를 O(m)의 저장공간을 사용하면서 O(mlog m)의 시간에 계산할 수 있는 방법을 제시한다. 이 자료 구조를 사용하여, 단순다각형 내에서 주축이 수직인 포물선 운동을 하는 ray shooting 질의가 주어졌을 때, ray가 처음으로 만나는 단순다각형의 경계선을 알 수 있다. 복잡도가 n인 다각형의 경우, O(nlog n)의 저장공간과 $O(nlog^2 n)$ 의 전처리 시간으로 "돌던지기 질의" 라고 알려진 이 문제에 대한 답을 $O(log^2 n)$ 에 계산할 수 있다. 이는 ray가 원모양의 운동을 할 때 알려진 최적의 시간바운드와 일치한다.
