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

CC BY-SA 3.0
2015-12-10T13:07:43.370Z
2015-12-10T13:07:43.370Z
László Kozma
<p><b>ETA: Everything below is in the paper "<a href="http://dl.acm.org/citation.cfm?id=314258" rel="nofollow">On the maximum scatter TSP</a>", Arkin et al, SODA 1997.</b></p>

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2011-10-13T21:09:27.820Z
Is there any reason to believe that there is no PTAS in the Euclidean case?
Jukka Suomela
CC BY-SA 3.0
2011-10-13T23:21:54.223Z
No reason that I know of. But the usual PTAS methods for Euclidean network design problems only work for minimization, not maximization.
David Eppstein
CC BY-SA 3.0
2011-10-17T03:28:21.023Z
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.
Chandra Chekuri
CC BY-SA 3.0
2015-12-10T11:17:25.910Z
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)
László Kozma
CC BY-SA 3.0
2011-10-13T20:27:02.590Z
2011-10-14T16:38:48.420Z
2011-10-14T16:38:48.420Z
David Eppstein
<p>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.</p>

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

CC BY-SA 3.0
2011-10-13T17:50:45.587Z
[Crossposted](http://stackoverflow.com/questions/7731501/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-point), [motivation](http://stackoverflow.com/questions/7656179/generate-visually-different-colors-with-an-unknown-color-collection-size).
Jukka Suomela
CC BY-SA 3.0
2011-10-13T17:55:06.100Z
Sounds like the maximisation version of [bottleneck TSP](http://en.wikipedia.org/wiki/Bottleneck_traveling_salesman_problem). Or the bottleneck version of the [longest path problem](http://en.wikipedia.org/wiki/Longest_path_problem). Does it have a name?
Jukka Suomela
CC BY-SA 3.0
2011-10-13T18:12:20.427Z
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 ?
Suresh Venkat
CC BY-SA 3.0
2011-10-13T20:44:36.697Z
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.
Suresh Venkat
<graph-algorithms><cg.comp-geom><optimization>
Sorting points such that the minimal Euclidean distance between consecutive points would be maximized
Lior Kogan
# Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

(Asked by: username_0 on 2011-10-13)

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.

**Tags:** graph-algorithms, cg.comp-geom, optimization

> **Comments:**
> **username_1**: [Crossposted](http://stackoverflow.com/questions/7731501/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-point), [motivation](http://stackoverflow.com/questions/7656179/generate-visually-different-colors-with-an-unknown-color-collection-size).  
> **username_1**: Sounds like the maximisation version of [bottleneck TSP](http://en.wikipedia.org/wiki/Bottleneck_traveling_salesman_problem). Or the bottleneck version of the [longest path problem](http://en.wikipedia.org/wiki/Longest_path_problem). Does it have a name?  
> **username_2**: 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 ?  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_4 on 2011-10-13. Score: 6 | Accepted answer

**ETA: Everything below is in the paper "[On the maximum scatter TSP](http://dl.acm.org/citation.cfm?id=314258)", 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.

> **Comments:**
> **username_1**: Is there any reason to believe that there is no PTAS in the Euclidean case?  
> **username_4**: No reason that I know of. But the usual PTAS methods for Euclidean network design problems only work for minimization, not maximization.  
> **username_5**: 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.  
> **username_3**: 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 (username_3, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP)  

---

### Answer by username_3 on 2015-12-10. Score: 3

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>
(username_3, Tobias Mömke: A PTAS for Euclidean Maximum Scatter TSP)


---

