@article{4117,
abstract = {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.},
author = {Edelsbrunner, Herbert and Van Leeuwen, Jan and Ottmann, Thomas and Wood, Derick},
issn = {1290-385X},
journal = {Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications},
number = {2},
pages = {171 -- 183},
publisher = {EDP Sciences},
title = {{Computing the connected components of simple rectilinear geometrical objects in D-Space}},
doi = {10.1051/ita/1984180201711},
volume = {18},
year = {1984},
}