Ray Shooting in Polygons Using Geodesic Triangulations

Abstract:

Let $P$ be a simple
polygon with $n$ vertices. We present a simple decomposition scheme
that partitions the interior of $P$ into $O(n)$ so-called geodesic
triangles, so that any line segment interior to $P$ crosses at most 2
log $n$ of these triangles. This decomposition can be used to
preprocess $P$ in a very simple manner, so that any ray-shooting query
can be answered in time $O(log^n)$. The data structure required $O(n)$
storage and $O(n$ log $n)$ preprocessing time. By using more
sophisticated techniques, we can reduce the preprocessing time to
$O(n)$. We also extend our general technique to the case of
ray-shooting amidst $k$ polygonal obstacles with a total of $n$ edges,
so that a query can be answered in $O( sqrt k$ log $n$) time.

This technical report has been published as

Ray Shooting in Polygons Using Geodesic Triangulations. Bernard
Chazelle, Herbert Edelsbrunner, Michelangelo Grigni,
Leonidas Guibas, John Hershberger, Micha Sharir, and
Jack Snoeyink, Algorithmica, 12, 1994,
pp. 54-68.