Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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.