CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

authors Lipski, Witold Jr. and Preparata, Franco P.
year 1980
title Finding the Contour of a Union of Iso-Oriented Rectangles
source Journal of Algorithms. Academic Press Inc., January, 1980. pp. 235-246 : some ill. a short bibliography
summary In this paper the following geometric problem is considered. Let R1,...,Rm be rectangles on the plane with sides parallel to the coordinate axes. An algorithm is described for finding the contour of F = R1, U...U Rm, in O(m log m+p log(2m2/p)) time, where p is the number of edges in the contour. This is O(m2) in the general case, and o(m log m) when F is without holes (then p < 8m - 4); both of these performances are optimal
keywords rectangles, geometry, computational geometry, algorithms
series CADline
references Content-type: text/plain
last changed 2003/06/02 08:24
HOMELOGIN (you are user _anon_604777 from group guest) Works Powered by SciX Open Publishing Services 1.002