3

I have a set of points in the plane and I want to find all convex polygons without including a point inside them.

For example I want to find all triangles, all four sized polygons, all four five sized polygons and so on until is possible to find them without including a point inside them.

In the image, row a corresponds to convex polygons of size 3. While column 1 and 2 show correct examples of what I want, column 3 shows a triangle including two points inside of it, which I dont want.

Rows b and c show examples of polygons of size 4 and 5.

enter image description here

I appreciate the help.

jessica
  • 131
  • 1
    Can you clarify your question? Suppose that there's just one point in your set -- the origin (0,0) -- and you want to only find all triangles. What would be a reasonable answer to this question? Do you want a function whose values are all possible triangles not containing the origin? A list (which would be infinitely long)? A test that would tell you, for any particular triangle $T$, whether $T$ was in your answer-set or not? Give us a clue what you're looking for, please, and maybe we can help. – John Hughes Feb 18 '14 at 03:18
  • You could draw every polygon that has its vertices at the given points, and then throw out the non-convex ones and the ones with interior points. Maybe considering this possibility will help you reword your problem. – Gerry Myerson Feb 18 '14 at 06:20
  • 1
    Dehnhardt proved that, given $n\ge12$ points in the plane in general position, there are at least $n^2-5n+10$ empty triangles. Trivially, there are at most $n-choose-3$, and that's achieved if each of the $n$ points is on the convex hull. – Gerry Myerson Feb 18 '14 at 06:27

0 Answers0