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$
  • 2
    $\begingroup$ Crossposted, motivation. $\endgroup$ – Jukka Suomela Oct 13 '11 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$ – Jukka Suomela Oct 13 '11 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$ – Suresh Venkat Oct 13 '11 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$ – Suresh Venkat Oct 13 '11 at 20:44
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$
  • $\begingroup$ Is there any reason to believe that there is no PTAS in the Euclidean case? $\endgroup$ – Jukka Suomela Oct 13 '11 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$ – David Eppstein Oct 13 '11 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$ – Chandra Chekuri Oct 17 '11 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$ – László Kozma Dec 10 '15 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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