authors 
Lipski, Witold Jr. and Preparata, Franco P. 
year 
1980 
title 
Finding the Contour of a Union of IsoOriented Rectangles 
source 
Journal of Algorithms. Academic Press Inc., January, 1980. pp. 235246 : 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 
Contenttype: text/plain

last changed 
2003/06/02 08:24 
