Window Queries On Planar Subdivisions Arising From Overlapping Polygons
Stuart A. Macgillivray, Bradford G. Nickerson · Canadian Conference on Computational Geometry · 2014
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.