Binary Space Partitions for Line Segments with a Limited Number of Directions
Csaba D. Tóth · SIAM Journal on Computing · 2003
We show that there is always a binary space partition (BSP) of size O(n log k) and an autopartition of size O(nk) for n disjoint line segments in the plane, assuming that the segments have k distinct orientations. In particular, if k is a constant, these bounds imply that there is a linear-size BSP and autopartition. Our proof is constructive and can be turned into algorithms computing such a BSP or autopartition in O(n 2 ) and O(n 2 k ) times.