Computing the connected components of simple rectilinear geometrical objects in D-Space
Edelsbrunner, Herbert
Van Leeuwen, Jan
Ottmann, Thomas
Wood, Derick
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.
EDP Sciences
1984
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/4117
Edelsbrunner H, Van Leeuwen J, Ottmann T, Wood D. Computing the connected components of simple rectilinear geometrical objects in D-Space. <i>Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications</i>. 1984;18(2):171-183. doi:<a href="https://doi.org/10.1051/ita/1984180201711">10.1051/ita/1984180201711</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1051/ita/1984180201711
info:eu-repo/semantics/altIdentifier/issn/0397-9326
info:eu-repo/semantics/altIdentifier/issn/1290-385X
info:eu-repo/semantics/closedAccess