Next: Problem 15: Output-sensitive Convex Up: The Open Problems Project Previous: Problem 13: Point Location

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 $\Theta$ (n log n)?
Origin: Paterson and Yao [PY90].
Status/Conjectures: Open.
Partial and Related Results: The upper bound of O(n log n) was established by Paterson and Yao [PY90]. Recently Tóth [T $\normalsize{\'{0\/}}$ 01] improved the trivial $\Omega$ (n) lower bound to $\Omega$ (n log n/loglog n). Can the remaining gap be closed?
Appearances: [MO01]
Categories: data structures; combinatorial geometry
Entry Revision History: J. O'Rourke, 2 Aug. 2001.

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 $\normalsize{\'{0\/}}$ 01

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

The Open Problems Project - July 24, 2008