Euclidean-squared max-cut in low dimensions Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that is at least $\frac 2 3$ of the total weight? If not, which constant should replace the $\frac 2 3$?

The worst example I'm able to find is 3 points on an equilateral triangle, which achieves the $\frac 2 3$. Note that a random split would produce $\frac 1 2$, but it seems intuitively obvious that in low dimensions, one can cluster better than randomly.

What happens for max-k-cut for k > 2? How about a dimension d > 2? Is there a framework to answer such questions? I know about Cheeger's inequalities, but those apply to sparsest cut (not max-cut) and only work for regular graphs.

(Question is inspired by the problem of clustering light sources in computer graphics to minimize variance).
The constant does tend to 1/2 as the dimension increases. In d dimensions, you can have d+1 points at distance one from each other, so the the sum of distance-squared is ${d+1 \choose 2}$ and the maximum cut is at most $(d+1)^2/4$, which is a $\frac 12 \cdot \frac {d+1}{d}$ fraction of the total weight