A note on binary plane partitions

被引：11

作者：

Tóth, CD ^{[1
]}

机构：

[1] Univ Calif Santa Barbara, Dept Comp Sci, Santa Barbara, CA 93106 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2003年 / 30卷 / 01期

关键词：

D O I：

10.1007/s00454-003-2921-x

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper considers binary space partitions (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ohm(n log n/log log n) in the worst case.

引用

页码：3 / 16

页数：14

共 8 条

[1] Binary space partitions or fat rectangles [J].

Agarwal, PK ;

Grove, EF ;

Murali, TM ;

Vitter, JS .

SIAM JOURNAL ON COMPUTING, 2000, 29 (05) :1422-1448

[2] New results on binary space partitions in the plane [J].

deBerg, M ;

deGroot, M ;

Overmars, M .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1997, 8 (06) :317-333

[3]

Fuchs H., 1980, Computer Graphics, V14, P124, DOI 10.1145/965105.807481

[4] EFFICIENT BINARY SPACE PARTITIONS FOR HIDDEN-SURFACE REMOVAL AND SOLID MODELING [J].

PATERSON, MS ;

YAO, FF .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (05) :485-503

[5] OPTIMAL BINARY SPACE PARTITIONS FOR ORTHOGONAL OBJECTS [J].

PATERSON, MS ;

YAO, FF .

JOURNAL OF ALGORITHMS, 1992, 13 (01) :99-113

[6]

SCHUMACKER RA, 1969, AFHRLTR6914

[7]

SUTHERLAND IE, 1984, ACM COMPUT SURV, V9, P1

[8]

TOTH CD, IN PRESS SIAM J COMP

← 1 →