Is there a known bound on the size of a BSP tree for a simple polygon? I am aware of the result by Toth which gives a tight $\Theta(n \log(n) / \log(\log(n)) )$ bound on the size of a BSP consisting of $n$ disjoint segments, but I wonder if it is possible to do better given some of the special properties of simple polygons. For example, it is trivial to show that convex polygons can be represented by BSP trees using at most $O(n)$ nodes. Is it possible to represent simple polygons in linear space as well?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
No, simple polygons are not any easier than disjoint segments. Given any n disjoint segments, there is a simple polygon with O(n) edges that includes all of the input segments as sides of the polygon. Then, any BSP tree for the polygon forms a BSP tree for the segments.
One way to do construct a polygon for a set of segments would be to triangulate the planar straight line graph formed by the input segments, and then pick a spanning tree of the triangulation, which is necessarily non-crossing. Then form a simple polygon by walking around an Euler tour of the spanning tree, using each of the input segments the first time the Euler tour traverses that edge and a parallel segment near it the second time the tour traverses it.
answered Mar 29, 2011 at 20:07
-
$\begingroup$ I had to think about it for a bit to convince myself that this worked, but you are correct! That is a very neat construction. $\endgroup$– MikolaCommented Mar 30, 2011 at 18:44