I am doing some exercises from my textbook and I have stuck by this one. Any help would be great
Give an example of a set S of n non-intersecting line segments in the plane for which a BSP tree of size n exists, whereas any auto-partition of S has size at least 4n/3 .
So far I have tried following, but I am not sure if this is the right path for my problem
To provide a simple estimate: let's say each segment splits at least one other segment when used as the splitting line (this is a conservative estimate, especially when n is large). If we build the BSP tree using the middle segment strategy, we will split roughly n/2 segments, creating an extra n/2 fragments. Thus, the auto-partitioned BSP tree will have at least n+n/2=3n/2 nodes. For larger n and considering segments may split more than one segment when used as the splitting line, the number could be more in line with the 4n/3 stated.
I think the following works:
The red line segment is not part of $S$, it just shows that a BSP of size $n$ can be done manually.
The first step of the auto-partition already produces $\left\lfloor\frac{4n}{3}\right\rfloor$ fragments in total.
In order to show that there will be at least $\frac{4n}{3}$ fragments (without the rounding), you would have to show that there is one more split in one of the next steps. But I think the claim is only meant to hold for the rounded result, anyway (consider the cases $n=1$ and $n=2,$ in which the statement "Any auto-partition of $S$ has size at least $\frac{4n}{3}$" is wrong.)
Note: I assume that "size of partition" means the number of fragments we have in the end.