@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},
}