ON THE OPTIMAL BINARY PLANE PARTITION FOR SETS OF ISOTHETIC RECTANGLES

被引：24

作者：

DAMORE, F

FRANCIOSA, PG

机构：

[1] Dipartimento di Informatia e Sistemistica, Università di Roma La Sapienza, I-00198 Roma

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 44卷 / 05期

关键词：

ANALYSIS OF ALGORITHMS; COMPUTATIONAL GEOMETRY; BINARY SPACE PARTITIONS; ISOTHETIC RECTANGLES;

D O I：

10.1016/0020-0190(92)90210-M

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：255 / 259

页数：5