Let $S$ be a finite set of points in the plane. A linear partition of $S$ is an unordered pair $\{A,B\}$ of subsets of $S$ such that $A \cup B = S, A \cap B = \emptyset,$ and $A$ and $B$ lie on opposite sides of some straight line disjoint from $S$ ($A$ or $B$ may be empty). Let $L_S$ be the number of linear partitions of $S$. If $|S| = n,$ then $L_S \le (n^2 - n + 2)/2.$
I showed that equality holds when $S$ forms a convex polygon. To prove the result in general, consider a point $P$ inside the convex hull of $S.$ Now we need an operation that moves $P$ to $P'$ such that $P'$ is on the new convex hull and no point on the original convex hull is inside the new convex hull. Furthermore, this operation should have the property that $L_S$ does not decrease. If these properties are satisfied, we will be done. Unfortunately, I was unable to find such an operation.
Is there another method of moving more points to the convex hull such that $L_S$ does not decrease? I don't want to start over and throw away all my work on proving the convex case. Any hints, ideas, or approaches?