[{"publication":"Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications","_id":"4117","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Van Leeuwen, Jan","last_name":"Van Leeuwen","first_name":"Jan"},{"full_name":"Ottmann, Thomas","last_name":"Ottmann","first_name":"Thomas"},{"last_name":"Wood","first_name":"Derick","full_name":"Wood, Derick"}],"issue":"2","oa_version":"None","publication_status":"published","date_created":"2018-12-11T12:07:02Z","article_processing_charge":"No","month":"01","title":"Computing the connected components of simple rectilinear geometrical objects in D-Space","intvolume":"        18","page":"171 - 183","quality_controlled":"1","language":[{"iso":"eng"}],"publisher":"EDP Sciences","article_type":"original","date_updated":"2022-01-27T15:22:30Z","year":"1984","citation":{"chicago":"Edelsbrunner, Herbert, Jan Van Leeuwen, Thomas Ottmann, and Derick Wood. “Computing the Connected Components of Simple Rectilinear Geometrical Objects in D-Space.” <i>Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications</i>. EDP Sciences, 1984. <a href=\"https://doi.org/10.1051/ita/1984180201711\">https://doi.org/10.1051/ita/1984180201711</a>.","ieee":"H. Edelsbrunner, J. Van Leeuwen, T. Ottmann, and D. Wood, “Computing the connected components of simple rectilinear geometrical objects in D-Space,” <i>Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications</i>, vol. 18, no. 2. EDP Sciences, pp. 171–183, 1984.","apa":"Edelsbrunner, H., Van Leeuwen, J., Ottmann, T., &#38; Wood, D. (1984). Computing the connected components of simple rectilinear geometrical objects in D-Space. <i>Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications</i>. EDP Sciences. <a href=\"https://doi.org/10.1051/ita/1984180201711\">https://doi.org/10.1051/ita/1984180201711</a>","ama":"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>","ista":"Edelsbrunner H, Van Leeuwen J, Ottmann T, Wood D. 1984. Computing the connected components of simple rectilinear geometrical objects in D-Space. Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications. 18(2), 171–183.","short":"H. Edelsbrunner, J. Van Leeuwen, T. Ottmann, D. Wood, Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications 18 (1984) 171–183.","mla":"Edelsbrunner, Herbert, et al. “Computing the Connected Components of Simple Rectilinear Geometrical Objects in D-Space.” <i>Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications</i>, vol. 18, no. 2, EDP Sciences, 1984, pp. 171–83, doi:<a href=\"https://doi.org/10.1051/ita/1984180201711\">10.1051/ita/1984180201711</a>."},"date_published":"1984-01-01T00:00:00Z","type":"journal_article","doi":"10.1051/ita/1984180201711","day":"01","publication_identifier":{"issn":["0397-9326"],"eissn":["1290-385X"]},"abstract":[{"text":"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\r\nin 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.","lang":"eng"}],"publist_id":"2001","volume":18,"extern":"1","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"}]