A new algorithm for finding the contour of a set of isorectangles is developed. The algorithm requires O(n2) time and O(n) space. This resolves the question, raised by Guting (4), of whether there exists an O(n) space algorithm which reports the pieces of the contour in the order of contour-cycles. The algorithm uses a data structure that facilitates a clear separation of the geometrical and topological aspect of the contour problem. A notion of topological equivalence is introduced and applied for avoiding repetitive computations for sets of !so-rectangles belonging to the same equivalence class. A modified definition of a slab ls introduced for handling special cases (induced by colinear edges) in a consistent way.
Download PDF here (1.7 Mb).