10.1007/3-540-54233-7_172
Chazelle, Bernard
Bernard
Chazelle
Herbert Edelsbrunner
Herbert
Edelsbrunner0000-0002-9823-6833
Grigni, Michelangelo
Michelangelo
Grigni
Guibas, Leonidas
Leonidas
Guibas
Hershberger, John
John
Hershberger
Sharir, Micha
Micha
Sharir
Snoeyink, Jack
Jack
Snoeyink
Ray shooting in polygons using geodesic triangulations
LNCS
Springer
1991
2018-12-11T12:06:42Z
2019-04-26T07:22:39Z
conference
/record/4059
/record/4059.json
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 time O(n log n) and storage O(n), so that any ray-shooting query can be answered in time O(log n).The algorithms are fairly simple and easy to implement. We also extend this 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(radicklog n) time.