9
$\begingroup$

I would like to apologize to all the posts below. Picked the wrong forum to post this in originally. However rather than make this a complete waste I've reworked the question to be a true "Theoretical Computer Science" problem.

Problem: Create an algorithm that takes a set of n ordered points in a 2D plane that form the contour of a simple polygon A that may or may not be concave and creates a new polygon B with m points such that:

  1. all points in A are contained within B
  2. 3 <= m < n
  3. B is the polygon in the set of all Bs with the smallest area
  4. B must be a simple polygon (i.e. no self-intersections).
  5. The input to the algorithm is polygon A and "m".
  6. Coincidence of segments in B with segments in A are allowed.

Some example inputs and expected outputs:

  1. If A is a square and m is 3 then B would be the triangle with the smallest surface area that contains A.
  2. If A is a hexagon and m is 4 then B would be a quadrilateral with the smallest surface area that contains A.

Good luck to everyone who tries this problem out. I can promise you this will be very hard especially now that the solution must be optimal.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ @Joe: Not true: If A is a square, then Thirian is asking for the minimum-area triangle containing A. On the other hand, if A is a triangle ($n=3$) then indeed there is no valid solution. $\endgroup$
    – Jeffε
    Commented Apr 12, 2012 at 19:11
  • 3
    $\begingroup$ Add 17 to my first comment, I guess. Why 20? $\endgroup$
    – Jeffε
    Commented Apr 13, 2012 at 1:40
  • 3
    $\begingroup$ Isn't FFT a low threshold for "complicated"? $\endgroup$
    – Sasho Nikolov
    Commented Apr 13, 2012 at 13:58
  • 2
    $\begingroup$ I don't think it's entirely true that the problem doesn't change at all if you (say) set m = 3. The problem is that you might require time exponential in m, and that's fine if m is fixed to some number, but is not fine if m is part of the input. $\endgroup$
    – Suresh Venkat
    Commented Apr 13, 2012 at 14:42
  • 5
    $\begingroup$ "everyone knows what the problem is" is not true. We're asking because the choices not specified make a difference. $\endgroup$
    – Suresh Venkat
    Commented Apr 13, 2012 at 19:53

2 Answers 2

Reset to default
10
$\begingroup$

I don't know how your polygons look, but perhaps a simplified version of the Ramer–Douglas–Peucker algorithm is enough:

  • for each convex part, calculate the area $A_j$ of of the triangles $P_i P_{i+1} P_{i+2}$ formed by three consecutive points;
  • for each concave part, calculate the area $B_k$ of of the two triangles $P_i P'_i P_{i+1}$ and $P_{i+1} P'_{i+2} P_{i+2}$ formed by the extension of the two points $P_i, P_{i+2}$ and the middle point $P_{i+1}$
  • calculate the $min\{A_j,B_k\}$ and delete the corresponding point (and shift points if the operation is done on the concave part);
  • loop until $n-m$ points have been deleted.

enter image description here
The border of the polygon ($A_j$ green triangles, $B_k$ red triangles). On the right, the border after the elimination of two points.

For more complex algorithms you can search for "polygon generalization techniques" though your first condition (points in A are contained in B) implies some additional scaling operations.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @Suresh: I'm pretty sure that the current 4 upvotes are for the transparency, not for the (almost trivial) algorithm :) $\endgroup$
    – Marzio De Biasi
    Commented Apr 13, 2012 at 22:01
  • 1
    $\begingroup$ This suffers from the same problem as the Ramer-Douglas-Peucker algorithms: The output is not guaranteed to be a simple polygon! $\endgroup$
    – Jeffε
    Commented Apr 14, 2012 at 7:23
  • 1
    $\begingroup$ @Jeffe: you're right, but (far from optimal if the polygon is complex) one can avoid simplifications that lead to a conflict. At the end, if there are other points that must be removed but non-simple polygon cannot be avoided, use a conflict resolution method (for example calculate intersection points and completely discard the "holes"). However I would like to see a real example from the OP. $\endgroup$
    – Marzio De Biasi
    Commented Apr 14, 2012 at 10:24
  • 1
    $\begingroup$ @MarzioDeBiasi That might work. But it might not. I think it's possible for every simplification you describe to cause a self-intersection. And "throwing out loops" can makes things worse, not better. This is probably a fine solution in practice, but remember where we are! $\endgroup$
    – Jeffε
    Commented Apr 15, 2012 at 8:37
  • $\begingroup$ Thanks Marzio, I now at least know what these kinds of problems are called now! Sadly the solution you gave is what (3) and (4) are in my suggested solutions and (4) has an issue with it. Elipses that are very stretched, and thus have sharp tips with angles roughly 30 degrees and less, will easily violate requirement (1). $\endgroup$
    – Thirlan
    Commented Apr 16, 2012 at 13:51
6
$\begingroup$

I wrote a paper long ago that detailed an linear-time algorithm for finding the smallest area triangle enclosing a point set (or a polygon):

J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin, "An optimal algorithm for finding minimal enclosing triangles," J. Algorithms, 1986, 7:258--269. Link.

Our work was followed by a general algorithm:

"Minimum area circumscribing polygons," Alok Aggarwal, J. S. Chang and Chee K. Yap, The Visual Computer, Volume 1, Number 2 (1985), 112-117. Link.

You can use Google Scholar to track those later papers that cite these to find improvements and related work.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.