RAY SHOOTING IN POLYGONS USING GEODESIC TRIANGULATIONS

Let P be a simple polygon with n vertices. We present a simple decompo sition scheme that partitions the interior of P into O(n) so-called ge odesic triangles, so that any line segment interior to P crosses at mo st 2 log n of these triangles. This decomposition can be used to prepr ocess 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 a nd O(n log n) preprocessing time. By using more sophisticated techniqu es, we can reduce the preprocessing time to O(n). We also extend our g eneral technique to the case of ray shooting amidst k polygonal obstac les with a total of n edges, so that a query can be answered in O(squa re-root k log n) time.