We present ecient algorithms for partitioning 2dimensional space into faces arising from the boundaries of overlapping polygons. In particular, we examine the case where the partitioning arises from overlaying m k-sided simple polygons. A dynamic data structure is presented for storing the partitioning that arises from m polygons with at most k sides each in space O(km 2 ) if the polygons are assumed to be convex, and space O(k 2 m 2 ) for simple polygons. Our structure returns T distinct regions from an axis-aligned orthogonal range search in worst case O(mk + (m + k)(logmk)T ) time, and can be updated in O(k 2 m 2 ) time.
['Stuart A. Macgillivray', 'Bradford G. Nickerson']
Window Queries On Planar Subdivisions Arising From Overlapping Polygons