4
$\begingroup$

Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function

\begin{align} cost(\mathcal{P},c) = \sum_{i\in[n]}\max_{p\in P_i}\Vert p-c\Vert^2 \end{align}

Let $c^\star$ be the point which minimizes the above objective function and the optimal cost is $opt(\mathcal{P}) = cost(\mathcal{P},c^\star)$.

For a point $c\in\mathbb{R}^d$ and $i \in [n]$, let $p_i^{(c)}$ be the point of $P_i$ farthest from $c$, i.,e. \begin{align*} \Vert p_i^{(c)} -c\Vert^2 = \max_{p\in P_i}\Vert p-c\Vert^2 \end{align*} Define $c$-mean to be the mean of these farthest points \begin{align*} \mu^{(c)} = \frac{1}{n}\sum_{i=1}^n p_i^{(c)} \end{align*}

So we have \begin{align*} cost_2(\mathcal{P},c) = \sum_{i=1}^n \Vert p_i^{(c)} -c\Vert^2 \end{align*} For ease of notation, let $p_i^\star = p_i^{(c^\star)}$ and $\mu^\star = \mu^{(c^\star)}$. So \begin{align*} opt_2(\mathcal{P}) = \sum_{i=1}^n \Vert p_i^\star - c^\star\Vert^2 \end{align*}

Note that if every set in $\mathcal{P}$ is singleton, then this is the well-known $k$-means objective and $c^\star = \mu^\star$.

It is easy to show the following, for any $c\in \mathbb{R}^d$ \begin{align} cost(\mathcal{P},c) \leq opt(\mathcal{P}) + n\Vert c - \mu^{(c)}\Vert^2 \end{align}

It follows that if there is a point $c$ such that $c = \mu^{(c)}$, then $c$ is an optimum center. This already helps to find the optimal solution in some simple scenarios, such as $\mathcal{P} = \{P_1,P_2\}$, where $P_1=\{(1,1),(1,-1)\}$ and $P_2=\{(-1,1),(-1-1)\}$. However it seems to me that the reverse direction may not hold: meaning for any optimal center $c^\star$, it may not be the case that $c^\star = \mu^{(c^\star)}$. So far I have not been able to come up with a counter example.

Does anyone have some idea as to finding a counter example.

P.s. Is this objective function already known?

$\endgroup$
2
  • 1
    $\begingroup$ Yes, this objective function is known. Check Definition 1.1. of this paper. Yours is a special case for $k = 1$, $p = \infty$, and $q = 1$. $\endgroup$ Dec 1 '21 at 17:16
  • $\begingroup$ @InuyashaYagami thanks for the reference. I have seen this paper but did not read it. $\endgroup$ Dec 2 '21 at 3:33
0
$\begingroup$

I have not verified the forward direction. However, here is a counterexample for reverse direction: $\mathcal{P} = \{ P_1, P_2,P_3\}$, where $P_{1} = \{(-1,0)\}$, $P_{2} = \{(1,0)\}$, and $P_{3} = \{(0,1),(0,-1)\}$. Here $c^{*} = (0,0)$. However, $p_{1}^{*} = (-1,0)$, $p_{2}^{*} = (1,0)$, and $p_{3}^{*} = (0,1)$ or $(0,-1)$ that have mean either $(0,1/3)$ or $(0,-1/3)$

$\endgroup$
3
  • $\begingroup$ Why is origin is the optimal center? $\endgroup$ Dec 2 '21 at 15:17
  • $\begingroup$ @SudiptaRoy Let $(a,b)$ be the center. Then, the cost is $(a-1)^2 + (a+1)^2 + 2b^2 + \max\{a^2+(b-1)^2, a^2+(b+1)^2\}$. Solve it. The function is minimized at the origin. $\endgroup$ Dec 2 '21 at 15:28
  • $\begingroup$ After my reply, I was thinking about this approach. Thank you $\endgroup$ Dec 2 '21 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.