A simple space optimal contour algorithm for a set of iso-rectangles

Przemyslaw Prusinkiewicz and Vijay V. Raghavan

Abstract

A new algorithm for finding the contour of a set of iso­rectangles 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.

Reference

Przemyslaw Prusinkiewicz and Vijay V. Raghavan. A simple space optimal contour algorithm for a set of iso-rectangles. Congressus Numerantium. Volume 46. May, 1985.

Download PDF here (1.7 Mb).