14
$\begingroup$

Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to minimize the average Euclidean distance between region $C_i$ and point $p_i$: $$\min_{C_1,\dots,C_n}\sum_{i=1}^n\iint_{C_i}\|x-p_i\|dx$$ It is easy to show that the boundaries at the optimal solution must be hyperbolic arcs, like this:

hyperbolas

Now, let's say I'd like to solve the same problem, but minimizing the average squared Euclidean distance: $$\min_{C_1,\dots,C_n}\sum_{i=1}^n\iint_{C_i}\|x-p_i\|^2dx$$ it is also easy to show that the optimal boundaries are straight lines and form a weighted Voronoi diagram:

hyperbolas

My question is: how different, in general, are these two solutions? More formally, if I take the optimal solution to one problem and evaluate its cost under the other problem, is there a bound as to how big the difference can be? When I coded this it looks like the gap is not very big.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Let ${\cal A}_p$ be the cost with the $\|\cdot\|^p$ term. Then by Cauchy-Schwarz,${\cal A}_1\leq {\cal A}_2^{1/2}$. Do you expect anything better, universally? If all the $p_i$s are extremely close to each other and to the center of the square, you can't really say much more.... $\endgroup$
    – ofer zeitouni
    Commented Apr 13, 2015 at 8:38
  • $\begingroup$ I'm interested in the objective value when I take the optimal solution to one problem, and plug it into the other, not a direct comparison of the two optimal objective values. If all the $p_i$'s are close to each other and to the center, then the cost of any subdivision is about the same. $\endgroup$
    – Tom Solberg
    Commented Apr 13, 2015 at 16:08
  • $\begingroup$ My comment still stands, but maybe was not well stated: ${\cal A}_p$ is the value for a particular partition, not necessarily the optimal one. Thus, if you take the optimal solution for the 2 functional and substitute it in the 1 functional, you will get the comparison I wrote. $\endgroup$
    – ofer zeitouni
    Commented Apr 13, 2015 at 19:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.