Next: Problem 15: Outputsensitive 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
Θ(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.
 MO01

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

M. S. Paterson and F. F. Yao.
Efficient binary space partitions for hiddensurface removal and
solid modeling.
Discrete Comput. Geom., 5:485503, 1990.
 Tót09

Csaba Tóth.
Binary plane partitions for disjoint line segments.
In Proc. 25th Sympos. on Comput. Geom., pages 7179, 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 151156,
2001.
The Open Problems Project  September 19, 2017