**Next:** Problem 15: Output-sensitive Convex Hull in \R^d

**Previous:** Problem 13: Point Location in 3D Subdivision

- 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
- Categories
data structures; combinatorial geometry

- Entry Revision History
J. O’Rourke, 2 Aug. 2001. Nina Amenta & JOR, 6 Jan. 2011.

- [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.