Skip to main content
added 17 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

I assume you intend the problem in which the polygon's vertices must be exactly the given set of points. If so, then, Yes, the problem is NP-hard:

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


          ![Fig1a][1]

Approximation algorithms have been explored:

Taranilla, María Teresa, Edilma Olinda Gagliardi, and Gregorio Hernández Peñalver. "Approaching minimum area polygonization." (2011): 161-170. (Authors' link.)

The key search term for this problem is polygonization.

I assume you intend the problem in which the polygon's vertices must be exactly the given set of points. If so, then, Yes, the problem is NP-hard:

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


          ![Fig1a][1]

Approximation algorithms have been explored:

Taranilla, María Teresa, Edilma Olinda Gagliardi, and Gregorio Hernández Peñalver. "Approaching minimum area polygonization." (2011): 161-170. (Authors' link.)

The key search term is polygonization.

I assume you intend the problem in which the polygon's vertices must be exactly the given set of points. If so, then, Yes, the problem is NP-hard:

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


          ![Fig1a][1]

Approximation algorithms have been explored:

Taranilla, María Teresa, Edilma Olinda Gagliardi, and Gregorio Hernández Peñalver. "Approaching minimum area polygonization." (2011): 161-170. (Authors' link.)

The key search term for this problem is polygonization.

Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

I assume you intend the problem in which the polygon's vertices must be exactly the given set of points. If so, then, Yes, the problem is NP-hard:

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


          ![Fig1a][1]

Approximation algorithms have been explored:

Taranilla, María Teresa, Edilma Olinda Gagliardi, and Gregorio Hernández Peñalver. "Approaching minimum area polygonization." (2011): 161-170. (Authors' link.)

The key search term is polygonization.