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?

Improve this question
$\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$
    – Gerry Myerson
    Commented Apr 16, 2019 at 22:26
  • $\begingroup$ @GerryMyerson Yes. Your understanding is correct. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Apr 16, 2019 at 23:25

1 Answer 1

Reset to default
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?.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks Joseph. Are you aware of NP-complete 2D variants other than Max-Area? $\endgroup$
    – Mohammad Al-Turkistany
    Commented 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$
    – Joseph O'Rourke
    Commented 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$
    – Sándor Fekete
    Commented 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$
    – Mohammad Al-Turkistany
    Commented Apr 18, 2019 at 14:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .