| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [11 references]
https://hal.inria.fr/inria-00434090
Contributor : Sylvain Lazard <>
Submitted on : Friday, November 20, 2009 - 4:57:00 PM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM
Long-term archiving on: : Thursday, June 17, 2010 - 7:05:15 PM
Contributor : Sylvain Lazard <>
Submitted on : Friday, November 20, 2009 - 4:57:00 PM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM
Long-term archiving on: : Thursday, June 17, 2010 - 7:05:15 PM
File
ijcga-final.pdf
Files produced by the author(s)