2
$\begingroup$

I would like to find the $m$ (where $n$ $\geq$ $m$ > 1) maximally distant subset of points from a collection of $n$ $d$-dimensional points. Maximally distant means the sum of the pairwise distances between the $m$ point subset is maximized.

This $m$ point subset will maximize some sort of distance metric (I am primarily interested in $L_2$-norm). The dimension $d$ will likely be 3 - however if there was a way to define a distance metric that was meaningful in $SE(3)$ (Special-Euclidean Group Lie Algebra) that would be favorable (the points in my motivating example are 6-Degrees of Freedom locations in 3-$D$ space i.e. 3 - position + 3 - orientation). Having said this any solution that works just in cartesian 3-space will also be fine.

Here is a simple example in 2-$D$

A set of 16 2-$D$ points $$\begin{array}{rrrr} + & + & + & + \\ + & + & + & + \\ + & + & + & + \\ + & + & + & + \\ \end{array}$$

Would lead to the maximally distant subset of $m$ = 4 points
$$\begin{array}{rrrr} + & & & + \\ & & & \\ & & & \\ + & & & + \\ \end{array}$$

Or for example with $m$ = 2 one of the two possible solutions would be $$\begin{array}{rrrr} + & & & \\ & & & \\ & & & \\ & & & + \\ \end{array}$$

Note: I found a similar question on this topic, but unfortunately the proposed answer requires convex optimization (QP) which is not suitable for the very large number of points that I require ($n$).

https://stackoverflow.com/questions/5400905/most-mutually-distant-k-elements-clustering

I have tried the following algorithm

Add the n d-dimensional points to a kd-tree
while subset S size is greater than n
   find the point q from the kd-tree that is least distant to any of its neighbors
   remove point q from the kd-tree and the subset S
return the subset S of m maximally distant points

This is obviously non-deterministic since the order in which the points are removed affects the eventual subset of $S$ (this however occasionally returns the correct solution). But the complexity is $(n - m)log(n)$ which is favorable considering $n$ will be $> 100,000$.

Does anyone have ideas about how to improve/replace the above algorithms whilst keeping the complexity down? Even if there is away to solve the QP in reasonable time with very large $n$ that would be great.

Improve this question
$\endgroup$
20
  • 3
    $\begingroup$ What is "maximally distant"? What exactly is to be maximized? $\endgroup$
    – Alex Degtyarev
    Commented Dec 4, 2014 at 22:33
  • 2
    $\begingroup$ It's not even clear to me what this means in the case $m=1$. Would you want the point whose closest point is farthest away? the point whose farthest point is farthest away? the point farthest away from the average of the other points? $\endgroup$
    – Gerry Myerson
    Commented Dec 4, 2014 at 22:41
  • 2
    $\begingroup$ Why did you classify it as graph theory when your question doesn't mention a graph? $\endgroup$
    – Brendan McKay
    Commented Dec 4, 2014 at 22:41
  • 3
    $\begingroup$ I think perhaps you should just compute the convex hull of your $n$ points, and then select $m$ of the hull points. I suggest this without really understanding what you are seeking. :-) $\endgroup$
    – Joseph O'Rourke
    Commented Dec 5, 2014 at 2:21
  • 2
    $\begingroup$ @difftator here the promised binary programming formulation: introduce binary variables $v_i$ for the selecting a point itself and $e_{ij}$ for selecting the pair $v_i$ and $v_j$ of points and, let further $w_{ij}$ denote the entries of the distance table. The objective is then to maximize the sum over all $w_{ij}e_{ij}$ under the constraints, that $e_{ij}\le v_i, e_{ij}\le v_j,\Sigma v_i = m, \Sigma e_{ij} = m^2$. In the relaxed version the additional constraint $e_{ij}\ge v_i+v_j-1$ further reduces the integrality gap. I hope that helps in utilizing existing LP solvers for your problem. $\endgroup$
    – Manfred Weis
    Commented Dec 6, 2014 at 11:57

0

Reset to default

Browse other questions tagged .