Binary space partitions or line segments with a limited number of directions
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 segment in the plane, assuming that the segment 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.
binary space partition line segments computational geometry