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 = ax² + 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² n) time, using O(n log n) storage and O(n log² n) preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.

This research was supported by the French-Korean Science and Technology Amicable Relationships program (STAR).

Keywords:

References

P. Agarwal and M. Sharir, J. Algorithms 14, 69 (1993), DOI: 10.1006/jagm.1993.1004. Crossref, Web of Science, Google Scholar
H.-K. Ahn, O. Cheong and R. van Oostrum, Comput. Geom.: Th. Appl. 26, 129 (2003), DOI: 10.1016/S0925-7721(02)00167-0. Crossref, Web of Science, Google Scholar
S. W. Bae and K.-Y. Chwa, Int. J. Comput. Geom. Appl. 16, 117 (2006), DOI: 10.1142/S0218195906001963. Link, Web of Science, Google Scholar
S.-W. Chenget al., Discr. Comput. Geom. 32, 401 (2004), DOI: 10.1007/s00454-004-1098-2. Crossref, Web of Science, Google Scholar
M. de Berg et al. , Computational Geometry: Algorithms and Applications , 2nd edn. ( Springer-Verlag , Berlin, Germany , 2000 ) . Crossref, Google Scholar
J. Hershberger and S. Suri, J. Algorithms 18, 403 (1995), DOI: 10.1006/jagm.1995.1017. Crossref, Web of Science, Google Scholar
R. Klein , Concrete and Abstract Voronoi Diagrams , Lecture Notes Comput. Sci. 400 ( Springer-Verlag , 1989 ) . Crossref, Google Scholar
R. Klein, K. Mehlhorn and S. Meiser, Comput. Geom.: Th. Appl. 3, 157 (1993), DOI: 10.1016/0925-7721(93)90033-3. Crossref, Web of Science, Google Scholar
M. Sharir and H. Shaul, Comput. Geom.: Th. Appl. 30, 239 (2005), DOI: 10.1016/j.comgeo.2004.10.001. Crossref, Web of Science, Google Scholar