10
$\begingroup$

Given a set of points in a 3D Cartesian space, I am looking for an algorithm that will sort these points, such that the minimal Euclidean distance between two consecutive points would be maximized.

It would also be beneficial if the algorithm would have a tendency toward a higher average Euclidean distance between consecutive points.

$\endgroup$
4
  • 2
    $\begingroup$ Crossposted, motivation. $\endgroup$ Oct 13, 2011 at 17:50
  • 2
    $\begingroup$ Sounds like the maximisation version of bottleneck TSP. Or the bottleneck version of the longest path problem. Does it have a name? $\endgroup$ Oct 13, 2011 at 17:55
  • 1
    $\begingroup$ I'd recommend using the gonzalez k-clustering heuristic (the greedy strategy). without thinking this through completely, it seems like it should yield a 2-approximation ? $\endgroup$ Oct 13, 2011 at 18:12
  • $\begingroup$ Unfortunately, as stated, Gonzalez won't give a good answer (consider the points (-100,0), (99,0) and (100,0)). If we start at the wrong point (-100,0) for example, we get a terrible answer. It's still possible that running gonzalez from every point and taking the best answer would work. $\endgroup$ Oct 13, 2011 at 20:44

2 Answers 2

6
$\begingroup$

ETA: Everything below is in the paper "On the maximum scatter TSP", Arkin et al, SODA 1997.

I don't know about exact answers, but here's another approach that's a little different from Suresh's suggestion of Gonzalez clustering:

Assume for simplicity that $n$ is even. For each vertex $p$, find the median of the $n-1$ distances $d(p,q)$. Form an undirected graph in which every vertex $p$ is connected to the other vertices that are at least the median distance away. The minimum degree in this graph is at least $n/2$, so by Dirac's theorem it's possible to find a Hamiltonian cycle in this graph.

On the other hand, there are $n/2 + 1$ vertices in the disk centered at $p$ with radius $d(p,q)$, too many to form an independent set in the cycle, so any Hamiltonian cycle would have to have an edge connecting some two of these vertices, of length at most $2d(p,q)$. Therefore, the Hamiltonian cycle found by this algorithm is at worst a 2-approximation to the bottleneck max cycle.

This will work in any metric space, and gives the optimal approximation ratio among algorithms that work in any metric space. For, if you could approximate better than to within a factor of two then you could solve Hamiltonian cycle problems exactly, by reducing the input graph to the Hamiltonian cycle problem into a metric space with distance 2 for every graph edge and distance 1 for every non-edge.

Probably with some care you can massage this into an approximation algorithm for paths instead of cycles.

$\endgroup$
4
  • $\begingroup$ Is there any reason to believe that there is no PTAS in the Euclidean case? $\endgroup$ Oct 13, 2011 at 21:09
  • 2
    $\begingroup$ No reason that I know of. But the usual PTAS methods for Euclidean network design problems only work for minimization, not maximization. $\endgroup$ Oct 13, 2011 at 23:21
  • $\begingroup$ One exception that I know of is the paper of Chen and Har-Peled on a PTAS for Orienteering in the plane. It is a maximization problem. $\endgroup$ Oct 17, 2011 at 3:28
  • $\begingroup$ We uploaded a preprint that addresses this question, i.e. gives a PTAS for max scatter TSP in the euclidean case. arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP) $\endgroup$ Dec 10, 2015 at 11:17
3
$\begingroup$

We uploaded a preprint that addresses this question, i.e. gives a PTAS for max scatter TSP in the euclidean case. http://arxiv.org/abs/1512.02963 (László Kozma, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.