Next: Problem 15: Output-sensitive Convex Hull in \R^d
Previous: Problem 13: Point Location in 3D Subdivision
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)?
Paterson and Yao [PY90].
Solved by Csaba Tóth [Tót09].
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.
data structures; combinatorial geometry
J. O’Rourke, 2 Aug. 2001. Nina Amenta & JOR, 6 Jan. 2011.
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.
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.
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.
Csaba David Tóth. A note on binary plane partitions. In Proc. 17th Annu. ACM Sympos. Comput. Geom., pages 151–156, 2001.