# Selecting a subset from a set such that a given quantity is minimized

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$.

-
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