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

Report ID:

TR-350-91

Authors:

Chazelle, Bernard [1] / Edelsbrunner, Herbert [2] / Grigni, Michelangelo [3] / Guibas, Leonidas [4] / Hershberger, John [5] / Sharir, Micha [6] / Snoeyink, Jack [7]

Date:

August 1991

Pages:

16

Download Formats:

[PDF [8]]

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.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] http://www.cs.princeton.edu/research/techreps/author/404

[3] http://www.cs.princeton.edu/research/techreps/author/61

[4] http://www.cs.princeton.edu/research/techreps/author/417

[5] http://www.cs.princeton.edu/research/techreps/author/424

[6] http://www.cs.princeton.edu/research/techreps/author/461

[7] http://www.cs.princeton.edu/research/techreps/author/466

[8] ftp://ftp.cs.princeton.edu/techreports/1991/350.pdf