0
$\begingroup$

Consider a set of points. For simplicity, let's say that those are 2D points (although the problem works in higher dimensions as well). The goal is to find the minimum possible length of a connected 1-dimensional curve, such that it passes through all the points.

Intuitively, the curve will consist of straight lines but how do those lines look like?

To make things clear, here is an approximation for a solution for a square:

.     .
 \   / 
  ---  
 /   \ 
.     .

For an equilateral triangle, we would pick a point inside and connect all vertices to it. We can find the best point with some differential equations.

The problem is not that hard to solve for these generic shapes. Is there an algorithm that solves the problem for any set of points?

I find this very similar to minimal surfaces -- the only difference is that these aren't surfaces but rather curves.

Improve this question
$\endgroup$
2
  • $\begingroup$ This is a well known problem, and it is a minimal surface indeed, with translational symmetry. For the minimum length curve, if three lines connect at a joint point, they must make 120$^\circ$ angles between them because this boils down to minimization of an energy functional which leads to a force balance constraint. Some people even found how to use the properties of soap to find those minimal surfaces, putting soap film on a set of parallel rods placed at the location of your given 2D vertices. $\endgroup$
    – Maxim Umansky
    Commented Jul 28, 2023 at 21:22
  • $\begingroup$ This is the Steiner tree problem, at least in the case you assume with points in 2D. There exists a polynomial-time approximation scheme (PTAS), but finding an optimal solution (for general numbers of points) is NP-hard. $\endgroup$
    – hardmath ♦
    Commented Aug 4, 2023 at 2:22

0

Reset to default

Your Answer

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