6
$\begingroup$

Let us consider fixed points in space, if we apply the well-known Traveling Salesperson Problem algorithm, we get the shortest route. It can give a nontrivial knot in the three-space. The question is what is the minimum number of points that can be like this, i.e. "TSP non-trivial"?

I have found $16$ points, but don't know if we can get less.

The coordinates for the example are:

[[-2.35172872,  0.87499447, -0.86062952],
   [-1.27279499, -0.58250424, -0.79981732],
   [-0.35964634, -0.96662397,  0.24847584],
   [ 0.77356703, -1.69027479,  0.9899925 ],
   [ 2.68106959, -0.99753048,  0.50923161],
   [ 2.54586669,  1.16513512, -0.60024349],
   [ 0.61077421,  1.64158209, -0.96863809],
   [-0.42031143,  0.91839722, -0.14112001],
   [-1.39719379,  0.51984603,  0.86062952],
   [-2.36439472, -1.0820831 ,  0.79981732],
   [-1.03519417, -2.78229854, -0.24847584],
   [ 0.89102032, -1.94691491, -0.9899925 ],
   [ 1.06785291, -0.39731003, -0.50923161],
   [ 1.09132302,  0.49945222,  0.60024349],
   [ 0.78406629,  2.10734042,  0.96863809],
   [-1.24427592,  2.71879248,  0.14112001]]
Improve this question
$\endgroup$
3
  • $\begingroup$ Isn't it 6 with the trefoil? $\endgroup$
    – Ryan Budney
    Commented Sep 25 at 15:55
  • $\begingroup$ Yeah, 6 seems to be the size of the shortest polygonal trefoil, but can it be arranged that the TSP solution is this trefoil? $\endgroup$
    – Daniel Asimov
    Commented Sep 25 at 16:16
  • 1
    $\begingroup$ This is an interesting question rich with points to explore! It lets you both describe collections of points as well as assign a number (the min # of points) to each knot. You can also look at the moduli space of fixed collections of points which generates a particular knot. $\endgroup$
    – Sidharth Ghoshal
    Commented Sep 25 at 16:34

0

Reset to default

You must log in to answer this question.