TY - CONF
AB - 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.
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
AU - Grigni, Michelangelo
AU - Guibas, Leonidas
AU - Hershberger, John
AU - Sharir, Micha
AU - Snoeyink, Jack
ID - 4059
T2 - 18th International Colloquium on Automata, Languages and Programming
TI - Ray shooting in polygons using geodesic triangulations
VL - 510
ER -