Shooting Permanent Rays among Disjoint Polygons in the Plane

Alexis Beingessner

Shooting Permanent Rays among Disjoint Polygons in the Plane
by: Mashhood Ishaque, Bettina Speckmann, Csaba D. Tóth

Abstract:
We present a data structure for ray shooting-and-insertion in the free space among disjoint polygonal obstacles with a total of n vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses O(n log n) space and preprocessing time, and it supports m successive ray shooting-and-insertion queries in O((m+n)log2n + m log m) total time.

My own note:
This structure is better at ray shooting in disjoint polygonal obstacles than any static structure we are aware of. However, this is a consequence of it being dynamic, and does not imply a better static algorithm. We will discuss how this is possible.