RAY SHOOTING AMIDST CONVEX POLYGONS IN 2D

We consider the problem of ray shooting in a two-dimensional scene con sisting of m convex polygons with a total of n edges. We present a dat a structure that requires O(mn log m) space and preprocessing time and that answers a ray shooting query in O(log(2) m log(2) n) time. If th e polygons are pairwise disjoint, the space and preprocessing time can be improved to O((m(2) + n)log m) and O((m(2) + n log n)log m), respe ctively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow only O(n) space, a ray shootin g query among a collection of disjoint simple polygons can be answered in time O([m/root n](1 + epsilon) log(2) n) lime, for any epsilon > 0 . (C) 1996 Academic Press, Inc.