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

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 [Tót01b] improved the trivial \Omega(n) lower bound to \Omega(n\log n/\log\log 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 \; \mathrm{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.

[Tót01b]

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