1
$\begingroup$

This question is based on Distributing points evenly on a sphere and Facility location on manifolds

The 'dispersal problem' (which can be mapped to packing disks in many cases) places $n$ points in a region $R$ such that the minimum pair-wise distance among them is maximized.

Question: Does the solution to the dispersal problem with $n$ points in a region $R$ also maximize the length of the shortest Hamiltonian circuit (the optimal traveling salesman trajectory) among any $n$ points in $R$?

Under what conditions on $R$ will this question have a "yes" answer (conditions such as "$R$ has Euclidean metric", "$R$ is a convex planar region" etc.)?

Example: To optimally disperse 5 points on a square, we could place them at the 4 corners and the center — in which case, the best TSP path too appears to be maximally long among all TSP answers with 5 points on the square.

$\endgroup$

0

You must log in to answer this question.