Plane-Sweep Algorithms for Intersecting Geometric Figures

摘要

This report considers various types of geometric figures in the plane defined by points connected by straight line segments, such as polygons (not necessarily simple) and maps (embedded planar graphs); and the problem of computing the intersection of such figures by means of a 'greedy' type of algorithm that sweeps the plane unidirectionally. Let n be the total number of points of all the figures involved, and s the total number of intersections of line segments. It is shown in the general case (no converity) a previously known algorithm can be extended to compute in time O((n+s)logn) and space O(n+s) all the connected regions into which the plane is divided by intersecting the figures. When the regions of each figure are convex, the same can be achieved in time O(nlogn+s) and space O(n).