I have a collection of vectors, let`s say $n$ vectors. I am trying to find an easy way to SORT these vectors in that way that after sorting of vectors $(V_1,V_2,...,V_n)$ the first vector $V_1$ and the last vector $V_n$ will be two furthest vectors. Next $V_{n-1}$ will be the second farthest vector from the $V_1$. $V_{n-2}$ will be the third furthest vector from the $V_1$...and so on. Is there a good algorithm or an easy way to achieve this?
2
-
$\begingroup$ perhaps I understand your question wrongly, but couldn't you just choose an arbitrary vector to be $V_1$, find the distances of all the other vectors to $V_1$ and then simply sort them according to their distances away from $V_1$? $\endgroup$– Vincent TjengCommented Mar 23, 2013 at 12:02
-
$\begingroup$ Clarification is necessary--by two farthest vectors do you mean $\max_{i,j}||V_i - V_j||_2$? (Which may not even be a unique pair in general.) $\endgroup$– adam WCommented Mar 23, 2013 at 12:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
To find two furthest vectors, compute the convex hull and find needed two points on it, it is O(n log n) in summary.
-
$\begingroup$ $V_1$ is not known to begin with, so "choosing" $V_1$ is the question. $\endgroup$– adam WCommented Mar 23, 2013 at 12:45
-
-
$\begingroup$ In the question, $V_1$ and $V_n$ are the (likely) unique pair that have the greatest distance. So $V_1$ here is not arbitrary. I do not see a better way than searching all pair distances to find them... $\endgroup$– adam WCommented Mar 23, 2013 at 12:54
-
-