---
_id: '4117'
abstract:
- lang: eng
  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."
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Jan
  full_name: Van Leeuwen, Jan
  last_name: Van Leeuwen
- first_name: Thomas
  full_name: Ottmann, Thomas
  last_name: Ottmann
- first_name: Derick
  full_name: Wood, Derick
  last_name: Wood
citation:
  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>
  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>
  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.
  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.
  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>.
  short: H. Edelsbrunner, J. Van Leeuwen, T. Ottmann, D. Wood, Rairo-Informatique
    Theorique Et Applications-Theoretical Informatics and Applications 18 (1984) 171–183.
date_created: 2018-12-11T12:07:02Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2022-01-27T15:22:30Z
day: '01'
doi: 10.1051/ita/1984180201711
extern: '1'
intvolume: '        18'
issue: '2'
language:
- iso: eng
month: '01'
oa_version: None
page: 171 - 183
publication: Rairo-Informatique Theorique Et Applications-Theoretical Informatics
  and Applications
publication_identifier:
  eissn:
  - 1290-385X
  issn:
  - 0397-9326
publication_status: published
publisher: EDP Sciences
publist_id: '2001'
quality_controlled: '1'
status: public
title: Computing the connected components of simple rectilinear geometrical objects
  in D-Space
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 18
year: '1984'
...