TY - JOUR
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 a very simple manner, so that any ray-shooting query can be answered in time O(log n). The data structure requires 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(√ log n) time.
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
AU - Grigni, Michelangelo
AU - Guibas, Leonidas
AU - Hershberger, John
AU - Sharir, Micha
AU - Snoeyink, Jack
ID - 4039
IS - 1
JF - Algorithmica
SN - 0178-4617
TI - Ray shooting in polygons using geodesic triangulations
VL - 12
ER -