Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A$ be is a set of some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^A$ denote the mean Euclidean distance from the point $x$ to its $k$ nearest points in $A$ (others than $x$). Let $C \subset A$ be a subset of points chosen randomly from $A$. We have $\Phi(A) = \sum_{x \in A} d_x^C$.

Now suppose that I remove a point $x'$ from $A$, I get a new set $A_2 = A \setminus \{x'\}$.

Question: Which condition should a new set $C_2 \subset A_2$ satisfies, in order to have $\Phi(A_2) = \sum_{x \in A_2} d_x^{C_2} \leq \Phi(A)$ ? In other words, how can I choose a subset $C_2$ from $A_2$ such that reduces the quantity $\Phi(A)$ (if such $C_2$ exists) ?

Note: $C$ and $C_2$ has a fixed size: $|C| = |C_2| = |A|/2$. And I have a constraint that $C \neq C_2$.

share|cite|improve this question
Do you have some context about this question ? Like why you were thinking about that ? I find it pretty strange, especially because the sum is on a smaller number of items ($A_2$ and A) on the two sides of the inequality – Thomas Dec 7 '13 at 15:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.