<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-30T18:44:47.477Z
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.
Mikola
CC BY-SA 2.5
2011-03-29T20:07:37.760Z
2011-03-29T20:07:37.760Z
David Eppstein
<p>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?</p>

<cg.comp-geom>
Size of BSP tree for a simple polygon?
Mikola
# Size of BSP tree for a simple polygon?

(Asked by: username_0 on 2011-03-29)

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?

**Tags:** cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2011-03-29. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

