Problem 14: Binary Space Partition Size

Statement

Is it possible to construct a binary space partition (BSP) for n disjoint line segments in the plane of size less than Θ(n log n)?

Origin

Paterson and Yao [PY90].

Status/Conjectures

Solved by Csaba Tóth [Tót09].

Partial and Related Results

The upper bound of O(n log n) was established by Paterson and Yao [PY90]. Tóth [T01] improved the trivial Ω(n) lower bound to Ω(n log n/loglog n). Then in 2009 he established a matching upper bound [Tót09]. His proof is constructive and leads to a deterministic algorithm that runs in O(n  polylog  n) time. As his algorithm produces BSP trees whose height might be linear in n, it remains open whether his complexity bound can be achieved while achieving O(log n) height.

Appearances

[MO01]

Categories

data structures; combinatorial geometry

Entry Revision History

J. O'Rourke, 2 Aug. 2001. Nina Amenta & JOR, 6 Jan. 2011.

Bibliography

MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.

PY90

M. S. Paterson and F. F. Yao.
Efficient binary space partitions for hidden-surface removal and solid modeling.
Discrete Comput. Geom., 5:485-503, 1990.

Tót09

Csaba Tóth.
Binary plane partitions for disjoint line segments.
In Proc. 25th Sympos. on Comput. Geom., pages 71-79, 2009.
Discrete Comput. Geom., to appear.

T01

Csaba David Tóth.
A note on binary plane partitions.
In Proc. 17th Annu. ACM Sympos. Comput. Geom., pages 151-156, 2001.