3
$\begingroup$

Euclidian (planar) TSP asks for a tour with the minimum total length. The problem is known to be NP-hard. I am interested in the variant of finding a closed tour with the minimum enclosed area (assuming that the solution has no crossing edges).

What is known about this problem and its computational complexity? Is the decision problem NP-hard?

Decision problem: Given a set of points on the plane, integer A

Question: Is there a tour that has enclosed area less than A?

$\endgroup$
2
  • $\begingroup$ There are closed curves with arbitrarily small enclosed areas visiting all the points. But I suppose your definition of a tour involves line segments, each joining two of the points, and each of the points being an endpoint of exactly two segments. $\endgroup$ Apr 16, 2019 at 22:26
  • $\begingroup$ @GerryMyerson Yes. Your understanding is correct. $\endgroup$ Apr 16, 2019 at 23:25

1 Answer 1

5
$\begingroup$

Indeed the problem is NP-complete:

Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23, no. 1 (2000): 73-110. (Journal link.)

Your problem is what Fekete calls $\text{Min-Area}$. He also proves $\text{Max-Area}$ is NP-complete, and addresses higher-dimensional variations.


          Fig1a
          Fekete: Fig.1a.


A version of this question was asked earlier: Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?.

$\endgroup$
4
  • $\begingroup$ Thanks Joseph. Are you aware of NP-complete 2D variants other than Max-Area? $\endgroup$ Apr 17, 2019 at 9:45
  • $\begingroup$ "for fixed dimensions $k$ and $d$, finding a simple $d$-dimensional polyhedron with a given set of vertices that has minimal volume of its $k$-dimensional faces is NP-hard." This answers a question I had posed myself. $\endgroup$ Apr 17, 2019 at 9:45
  • $\begingroup$ Glad to see the interest in this; let me know if you have further specific questions. You may also be interested to know that right now there is an contest going on about finding good solutions for specific instances: cgshop.ibr.cs.tu-bs.de This is part of a broader workshop on open problems in geometric optimization: sites.google.com/stonybrook.edu/cgweek2019-workshop There's still time to participate if you are up for it! Best regards, Sándor Fekete $\endgroup$ Apr 18, 2019 at 13:31
  • $\begingroup$ Thanks for the links. BTW, Is this problem NP-complete?: Given a set of rectilinear points and a number A, Is there a simple polygonization with area A? $\endgroup$ Apr 18, 2019 at 14:00

Your Answer

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