| 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 10:24 |
|
