1
$\begingroup$

Let me define my question formally. Suppose we have a set of points $C = \{x_i|x_i \in \mathbb R^d, i=1,\dots, n\}$, $n>d$. The goal is to find a "center" point $x\in \mathbb R^d$, such that $$ x = \arg\min_{u\in \mathbb R^d} (\max_{x_i\in C}\|u - x_i\|^2 - \min_{x_i\in C}\|u - x_i\|^2) $$ My first thought was that $x$ must be at the center of $C$. But the mass center is the minimizer of the sum of squared distances and does not satisfy our requirement. Also, I noticed that the function to minimize is actually convex. (The objective is convex when $n=2$ and for $C>2$ it can be viewed as a pointwise maximization for ($x_i,x_j$) pairs).

So here is my question: Is there any closed-form solution for this seemingly concise problem? If not, is there any way to give a lower bound for this objective given the set of points $C$? Thanks!

$\endgroup$
0

2 Answers 2

2
$\begingroup$

This is known as the bounding sphere problem (a special case of the 1-center problem), and it does not appear to a have a closed-form solution.

$\endgroup$
1
$\begingroup$

I'm not sure this is a well-formed goal, if the intent is to find some analog to a center. If you take $\lim_{u \to \infty^d}$, we trivially minimize the objective, as $$\lim_{u \to \infty^d} \left( \max_{x_i\in C}\|u - x_i\|^2 - \min_{x_i\in C}\|u - x_i\|^2 \right) = 0$$ (Also, as a result, save for under specific conditions / trivial cases on the set of points $C$ such as a single point or all points on the surface of a $d$-dim sphere, we only have an infinum, no achievable min).

Adding some form of regularization or constraints could fix that property, but would also continue to complicate your question and possibly skew the final answer; if you were just looking to encode a specific property it may be easier to consider different problem formulations to capture the dynamics you want. What's the larger context of the problem you're trying to solve?

$\endgroup$
1
  • $\begingroup$ It seems $u\to \infty^d$ does not minimize the objective, because $\lim_{u\to\infty^d} (\|u- x_1\|^2 - \|u-x_2\|^2) = \lim_{u\to\infty} 2 u^T(x_2 - x_1) + \|x_1\|^2 - \|x_2\|^2$. And since $x_i - x_j$ are not always in parallel, this makes the objective function infinity. Moreover, the objective seems to be convex (as I edited). This question is indeed a component of a larger problem. Actually, I only need a lower bound for it to prove a worst-case of an algorithm. But one can easily design a specific set $C$ to make this objective zero. That's why I am looking for a closed-form solution. $\endgroup$
    – Wenda
    Commented May 7, 2022 at 17:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .