Skip to main content
Added a few more details.
Source Link
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Here is a quote from the first paper cited below: Steinhaus posed a version of your question, which has become known as simple polygonization of a set of points:


  [![Steinhaus][1]][1]

1Agarwal, Pankaj K., Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 42-54.

25Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Dover Publications, Inc., New York, 194.

Subsequently, Michael Gemignani removed the general-position assumption, relaxed to not-all-collinear. And then Grünbaum offered a simple proof that leads to an $O(n \log n)$ algorithm.1

Fedor Petrov's solution is known as a star polygonization.

Finding a minimal-area simple polygonization is NP-hard.

Here is a quote from the first paper cited below: Steinhaus posed a version of your question, which has become known as simple polygonization of a set of points:


  [![Steinhaus][1]][1]

1Agarwal, Pankaj K., Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 42-54.

25Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Dover Publications, Inc., New York, 194.

Here is a quote from the first paper cited below: Steinhaus posed a version of your question, which has become known as simple polygonization of a set of points:


  [![Steinhaus][1]][1]

1Agarwal, Pankaj K., Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 42-54.

25Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Dover Publications, Inc., New York, 194.

Subsequently, Michael Gemignani removed the general-position assumption, relaxed to not-all-collinear. And then Grünbaum offered a simple proof that leads to an $O(n \log n)$ algorithm.1

Fedor Petrov's solution is known as a star polygonization.

Finding a minimal-area simple polygonization is NP-hard.

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

Here is a quote from the first paper cited below: Steinhaus posed a version of your question, which has become known as simple polygonization of a set of points:


  [![Steinhaus][1]][1]

1Agarwal, Pankaj K., Ferran Hurtado, Godfried T. Toussaint, and Joan Trias. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 42-54.

25Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Dover Publications, Inc., New York, 194.