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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
