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

1. Nov 29, 2013

### ShNaYkHs

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 $c'$ 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 $\Phi(A_2) \leq \Phi(A)$ ?