I found this question on reddit math, and couldn’t figure out the answer, nor was any answer posted on the site, I’m hoping I can get a hint on how to figure this out.
I know I need to work in the dual to solve this one...
Consider a set P of n points in the plane. For k ≤ ⌊n/2⌋, point q (which may or may not be in P) is called a k-splitter if every line ℓ passing through q has at least k points of P lying on or above it and at least k points on or below it. (For example, the point q shown in the figure on the next page is a 3-splitter, since every line passing through q has at least 3 points of P lying on either side. But it is not a 4-splitter since a horizontal line through q has only 3 points below it.) Observe that any point outside the convex hull of P is a 0-splitter, whereas a point within the convex hull is a k-splitter with k ≥ 1.
Show that for all (sufficiently large) n, there exists a set of n points that has no ⌊n/2⌋ splitter.