11
$\begingroup$

Suppose I am given a finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. Assuming $p_i=(x_i,y_i)$ and $x_i<x_{i+1}$, I can formalize this problem as:

Problem 1 (edited in response to Suresh's comments) Determine $C^2$ functions $x(t),y(t)$ of a parameter $t$ such that the arclength $ L = \int_{[t \in 0,1]} \sqrt{x'^2+y'^2}dt$ is minimized, with $x(0) = x_1, x(1) = x_n$ and for all $t_i: x(t_i) = x_i$, we have $y(t_i)=y_i)$.

How do I prove (or perhaps refute) that Problem 1 is NP-hard?

Why I suspect NP-hardness Suppose the $C^2$ assumption is relaxed. Evidently, the function of minimal arclength is the Travelling Salesman tour of the $p_i$'s. Perhaps the $C^2$ constraint only makes the problem much harder?

Context A variant of this problem was posted on MSE. It didn't receive an answer both there and on MO. Given that it's nontrivial to solve the problem, I want to establish how hard it is.

$\endgroup$
  • 1
    $\begingroup$ The constraint that $x_i < x_{i+1}$ seems to make the problem much easier. In particular, if you now drop the $C_2$ constraint, why is this problem not trivially solved because you connect the points by straight lines ? $\endgroup$ – Suresh Apr 8 '12 at 23:12
  • 1
    $\begingroup$ That's not a function. If you "loop around" from $p_3$ to $p_2$, under the constraint that $x_1 < x_2 < x_3$, your curve will intersect a vertical line twice. $\endgroup$ – Suresh Apr 8 '12 at 23:47
  • 1
    $\begingroup$ It is not clear, you need to state what you mean by "determine" here. It is not a standard terminology. It is not even a decision problem so using the term NP-hard doesn't make sense. $\endgroup$ – Kaveh Apr 9 '12 at 3:19
  • 1
    $\begingroup$ @Suresh, can you expand on the output part? I am guessing that you mean outputting the name of a curse from a enumerable set of curves. Note that in that case, it is not clear that the optimal curve will always be from that class. On the other hand, if we mean to find the best or a good one between those (or an approximation up to some given parameter to the optimal curve) then the class of parametric curves should be specified, otherwise the question is incomplete and cannot be answered. $\endgroup$ – Kaveh Apr 9 '12 at 5:20
  • 1
    $\begingroup$ The input/output is not a finite object anymore, e.g. if you are really dealing with real numbers/functions then your problem is higher-type. Each infinite objects are given by an infinite series of approximations to the intended object. CCA network's page contains more links if you are interested. $\endgroup$ – Kaveh Apr 9 '12 at 5:44
12
$\begingroup$

The differentiability requirement doesn't change the nature of the problem: requiring $\mathcal{C}^0$ (continuity) or $\mathcal{C}^{\infty}$ (infinite differentiability) gives the same lower bound for the length and the same order of points, and is equivalent to solving the traveling salesman problem.

If you have a solution to the TSP, you have a $\mathcal{C}^0$ curve that goes through all the points. Conversely, suppose you have a $\mathcal{C}^0$ curve of finite length that goes through all the points, and let $p_{\sigma(1)}, \ldots, p_{\sigma(n)}$ be the order in which it traverses the points and $t_1,\ldots,t_n$ the corresponding parameters (if the curve traverses a point more than once, pick any of the possible values of $t$). Then the curve built from $n$ segments $[p_{\sigma(1)},p_{\sigma(2)}], \ldots, [p_{\sigma(n-1)},p_{\sigma(n)}], [p_{\sigma(n)},p_{\sigma(1)}]$ is shorter, because for each segment a straight line is shorter than any other curve that connects the point. Thus for every ordering of the points, the best curve is a TSP solution, and the TSP solution provides the best ordering of the points.

Let's now show that requiring the curve to be $\mathcal{C}^{\infty}$ (or $\mathcal{C}^k$ for any $k$) doesn't change the best ordering of points. For any TSP solution of total length $\ell$ and any $\epsilon > 0$, we can round every corner, i.e. build a $\mathcal{C}^{\infty}$ curve that traverses the points in the same order and has a length of at most $\ell + \epsilon$ (the explicit construction relies on algebraic functions and $e^{-1/t^2}$ to define bump functions and from those smooth connections between curve segments such as $e^{1-1/x^2} (x-e^{-1/(1-x)^2})$ which connects with $y=0$ at $x=0$ and with $y=x$ at $x=1$; it is tedious to make these explicit, but they are computable); hence, the lower bound for a $\mathcal{C}^{\infty}$ curve is the same as for a collection of segments (note that the lower bound is not reached in general).

$\endgroup$
  • $\begingroup$ This is exactly the argument I was looking for , for a long time! Can you give a reference for the tedious construction? $\endgroup$ – PKG Apr 9 '12 at 23:20
  • 1
    $\begingroup$ This is not entirely rigorous, especially since in the plane you can get an arbitrarily good approximation to TSP in polynomial time. $\endgroup$ – Suresh Apr 10 '12 at 0:36
  • $\begingroup$ I thought you could approximate TSP only to within a factor of 2 in poly time? $\endgroup$ – PKG Apr 10 '12 at 0:49
  • $\begingroup$ @PKG The construction probably has a name, but I'm afraid my calculus classes were too long ago for me to remember it. I've just remembered the basic connection is called a bump function. $\endgroup$ – Gilles 'SO- stop being evil' Apr 10 '12 at 0:59
  • 1
    $\begingroup$ It's not a mistake per se. Your reduction is approximate - upto some error term $\epsilon$. This matters, because the reduction might be expensive (i.e exponential in $1/\epsilon$). So the reduction is not exact. @PKG you can approximate TSP to factor 3/2 in general metric spaces and arbitrarily close (to within $1+\epsilon$) in the plane or any Euclidean space. $\endgroup$ – Suresh Apr 10 '12 at 2:30

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.