TY - JOUR
AB - Two or more geometrical objects (solids) are said to be connected whenever their union is a connected point set in the usual sense. Sets of geometrical objects are naturally divided into connected components, which are maximal connected subsets. We show that the connected components of a given collection of n horizontal and vertical line segments in the plane can be computed in O (n log n) time and O (n) space and prove that this is essentially optimal. The result is generalized to compute the connected components of a set of n rectilinearly-oriented rectangles
in the plane with the same time and space bounds. Several extensions of the results to higher dimensions and to dynamic sets of objects are discussed.
AU - Edelsbrunner, Herbert
AU - Van Leeuwen, Jan
AU - Ottmann, Thomas
AU - Wood, Derick
ID - 4117
IS - 2
JF - Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications
SN - 0397-9326
TI - Computing the connected components of simple rectilinear geometrical objects in D-Space
VL - 18
ER -