Furko's blog

Polygon
By Furko, 11 years ago, translation, In English

I have some unsolved problem. There is some description of it.

You are given set of points with size N. You should build polygon with minimal square without intersections that contain every point such a vertex of polygon.

It will be great if you attach your code :)

Please give me any hints about it. I need optimal algorithm as such as possible.

Thanks.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

The problem statement is not very clear to me. Is the following what you want?

You are given N points on the Euclidean plane. Among the simple N-gons whose vertices are the given points, find the one with the minimum area.

If this is the problem you are asking about, I have a bad news: it is known to be NP-hard. For a proof, see:

Sándor P. Fekete. On simple polygonalizations with optimal area. Discrete and Computational Geometry, 23(1):73–110, Jan. 2000. DOI: 10.1007/PL00009492. Author copy: http://www.ibr.cs.tu-bs.de/users/fekete/hp/publications/papers/f-spoa-00.pdf.

→ Reply