We present a binary space partition algorithm for a set of disjoint isothetic rectangles. It recursively splits the set by means of isothetic cutting lines, until no two rectangles belong to the same portion of the plane. Rectangles intersected by a cutting line are split. We provide an algorithm that given n rectangles builds a linear sized Binary Space Partition with no empty regions by means of at most 4n - 1 cuts. The algorithm runs in 0(n log n) worst-case space and time. We generalize and improve a previous result achieved on isothetic line segments by Paterson and Yao.

ON THE OPTIMAL BINARY PLANE PARTITION FOR SETS OF ISOTHETIC RECTANGLES / D'Amore, Fabrizio; Franciosa, Paolo Giulio. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 44:5(1992), pp. 255-259. (Intervento presentato al convegno 4th Canadian Conference on Computational Geometry tenutosi a St. John's, Newfoundland, Canada nel August 10-14, 1992) [10.1016/0020-0190(92)90210-m].

ON THE OPTIMAL BINARY PLANE PARTITION FOR SETS OF ISOTHETIC RECTANGLES

D'AMORE, Fabrizio;FRANCIOSA, Paolo Giulio
1992

Abstract

We present a binary space partition algorithm for a set of disjoint isothetic rectangles. It recursively splits the set by means of isothetic cutting lines, until no two rectangles belong to the same portion of the plane. Rectangles intersected by a cutting line are split. We provide an algorithm that given n rectangles builds a linear sized Binary Space Partition with no empty regions by means of at most 4n - 1 cuts. The algorithm runs in 0(n log n) worst-case space and time. We generalize and improve a previous result achieved on isothetic line segments by Paterson and Yao.
1992
analysis of algorithms; binary space partitions; computational geometry; isothetic rectangles
01 Pubblicazione su rivista::01a Articolo in rivista
ON THE OPTIMAL BINARY PLANE PARTITION FOR SETS OF ISOTHETIC RECTANGLES / D'Amore, Fabrizio; Franciosa, Paolo Giulio. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 44:5(1992), pp. 255-259. (Intervento presentato al convegno 4th Canadian Conference on Computational Geometry tenutosi a St. John's, Newfoundland, Canada nel August 10-14, 1992) [10.1016/0020-0190(92)90210-m].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/48479
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 25
social impact