Finding the Contour of a Union of Iso-Oriented Rectangles

摘要

Let R(1),...,R(m) be rectangles on the plane with sides parallel to the coordinate axes. An algorithm is described to find the contour of F = R(1) U ... U R(m) in o(mlogm + plog(2 sq m/p)) time, where p is the number of edges in the contour. This is o(sq. m) (optimal) in the general case, and o(mlogm) (optimal) when F is without holes (then p < or = 8m-4). (Author)