<p>I don't know how your polygons look, but perhaps a simplified version of the <a href="http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm" rel="noreferrer">Ramer–Douglas–Peucker algorithm</a> is enough:</p>

<ul>
<li>for each <em>convex</em> part, calculate the area $A_j$ of of the triangles $P_i P_{i+1} P_{i+2}$ formed by three consecutive points;</li>
<li>for each <em>concave</em> 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}$</li>
<li>calculate the $min\{A_j,B_k\}$ and delete the corresponding point (and shift points if the operation is done on the concave part);</li>
<li>loop until $n-m$ points have been deleted.</li>
</ul>

<p><img src="https://i.sstatic.net/817Z2.jpg" alt="enter image description here"><br>
The border of the polygon ($A_j$ green triangles, $B_k$ red triangles). On the right, the border after the elimination of two points.</p>

<p>For more complex algorithms you can search for "<a href="http://www.google.it/search?q=polygon%20generalisation%20techniques" rel="noreferrer">polygon generalization techniques</a>" though your first condition (points in A are contained in B) implies some additional scaling operations.</p>

CC BY-SA 3.0
2012-04-13T22:01:43.790Z
@Suresh: I'm pretty sure that the current 4 upvotes are for the transparency, not for the (almost trivial) algorithm :)
Marzio De Biasi
CC BY-SA 3.0
2012-04-14T07:23:23.130Z
This suffers from the same problem as the Ramer-Douglas-Peucker algorithms: The output is not guaranteed to be a simple polygon!
Jeffε
CC BY-SA 3.0
2012-04-14T10:24:08.077Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2012-04-15T08:37:45.997Z
@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!
Jeffε
CC BY-SA 3.0
2012-04-16T13:51:07.740Z
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).
Thirlan
CC BY-SA 3.0
2012-04-13T17:31:42.430Z
2012-04-13T17:31:42.430Z
Marzio De Biasi
<p>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):</p>

<blockquote>
  <p>J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin,
  "An optimal algorithm for finding minimal enclosing triangles,"
  <em>J. Algorithms</em>, 1986, <strong>7</strong>:258--269. <a href="http://www.sciencedirect.com/science/article/pii/0196677486900076">Link</a>.</p>
</blockquote>

<p>Our work was followed by a general algorithm:</p>

<blockquote>
  <p>"Minimum area circumscribing polygons,"
  Alok Aggarwal, J. S. Chang and Chee K. Yap,
  <em>The Visual Computer</em>,
  Volume 1, Number 2 (1985), 112-117. <a href="http://www.springerlink.com/content/n82r1k7261145298/">Link</a>.</p>
</blockquote>

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

CC BY-SA 3.0
2012-05-04T20:43:18.747Z
2012-05-04T20:43:18.747Z
Joseph O'Rourke
<p>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.</p>

<p>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:</p>

<ol>
<li>all points in A are contained within B</li>
<li>3 &lt;= m &lt; n</li>
<li>B is the polygon in the set of all Bs with the smallest area</li>
<li>B must be a simple polygon (i.e. no self-intersections).</li>
<li>The input to the algorithm is polygon A and "m".</li>
<li>Coincidence of segments in B with segments in A are allowed.</li>
</ol>

<p>Some example inputs and expected outputs:</p>

<ol>
<li>If A is a square and m is 3 then B would be the triangle with the smallest surface area that contains A.</li>
<li>If A is a hexagon and m is 4 then B would be a quadrilateral with the smallest surface area that contains A.</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2012-04-12T19:11:22.880Z
@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.
Jeffε
CC BY-SA 3.0
2012-04-12T19:12:08.387Z
@Thirlan: Do you want a simple solution, or do you want the optimal solution?  Even if the problem can be solved quickly, the optimal algorithm could be quite complicated.
Jeffε
CC BY-SA 3.0
2012-04-12T19:28:17.993Z
Let me elaborate on the question.
Thirlan
CC BY-SA 3.0
2012-04-12T21:07:56.587Z
@JɛﬀE thanks for clarifying that. I'm deleting my comment.
Joe
CC BY-SA 3.0
2012-04-13T01:39:15.477Z
Is m part of the input?
Jeffε
CC BY-SA 3.0
2012-04-13T01:40:18.893Z
Add 17 to my first comment, I guess.  Why 20?
Jeffε
CC BY-SA 3.0
2012-04-13T13:18:47.783Z
Yes m is part of the input. Why 20? The messaging format I'm using allows a max of 20 to be sent over the wire, however I also wanted to point out that I'm working with large polygons, in case that helps or gives an idea of how much work has to be done. The problem changes little however if I make m 19, 21 or 3.
Thirlan
CC BY-SA 3.0
2012-04-13T13:58:52.740Z
Isn't FFT a low threshold for "complicated"?
Sasho Nikolov
CC BY-SA 3.0
2012-04-13T14:08:48.720Z
Let's not get caught up in the trivial comments in my question and actually focus on the question - : (
Thirlan
CC BY-SA 3.0
2012-04-13T14:42:26.523Z
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.
Suresh Venkat
CC BY-SA 3.0
2012-04-13T15:10:48.393Z
Point taken Suresh, I've clarified the question further. Also please no further comments at this point : ( there have been 8 comments but no answers even though everyone knows what the problem is at this point.
Thirlan
CC BY-SA 3.0
2012-04-13T19:53:46.887Z
"everyone knows what the problem is" is not true. We're asking because the choices not specified make a difference.
Suresh Venkat
CC BY-SA 3.0
2012-04-13T21:58:50.817Z
@Thirlan: can you upload one or two examples of a typical polygon you're working on and the corresponding values for $m$?
Marzio De Biasi
<ds.algorithms><cg.comp-geom><polygon>
Polygon within polygon generalization problem
Thirlan
# Polygon within polygon generalization problem

(Asked by: username_0 on 2012-04-12)

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.

**Tags:** ds.algorithms, cg.comp-geom, polygon

> **Comments:**
> **username_1**: @username_2: 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.  
> **username_1**: @username_0: Do you want a simple solution, or do you want the optimal solution?  Even if the problem can be solved quickly, the optimal algorithm could be quite complicated.  
> **username_0**: Let me elaborate on the question.  
> **username_2**: @JɛﬀE thanks for clarifying that. I'm deleting my comment.  
> **username_1**: Is m part of the input?  
> **username_1**: Add 17 to my first comment, I guess.  Why 20?  
> **username_0**: Yes m is part of the input. Why 20? The messaging format I'm using allows a max of 20 to be sent over the wire, however I also wanted to point out that I'm working with large polygons, in case that helps or gives an idea of how much work has to be done. The problem changes little however if I make m 19, 21 or 3.  
> **username_3**: Isn't FFT a low threshold for "complicated"?  
> **username_0**: Let's not get caught up in the trivial comments in my question and actually focus on the question - : (  
> **username_4**: 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.  
> **username_0**: Point taken Suresh, I've clarified the question further. Also please no further comments at this point : ( there have been 8 comments but no answers even though everyone knows what the problem is at this point.  
> **username_4**: "everyone knows what the problem is" is not true. We're asking because the choices not specified make a difference.  
> **username_5**: @username_0: can you upload one or two examples of a typical polygon you're working on and the corresponding values for $m$?  

---

## 2 answers

### Answer by username_5 on 2012-04-13. Score: 10

I don't know how your polygons look, but perhaps a simplified version of the [Ramer–Douglas–Peucker algorithm](http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_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](https://i.sstatic.net/817Z2.jpg)  
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](http://www.google.it/search?q=polygon%20generalisation%20techniques)" though your first condition (points in A are contained in B) implies some additional scaling operations.

> **Comments:**
> **username_5**: @Suresh: I'm pretty sure that the current 4 upvotes are for the transparency, not for the (almost trivial) algorithm :)  
> **username_1**: This suffers from the same problem as the Ramer-Douglas-Peucker algorithms: The output is not guaranteed to be a simple polygon!  
> **username_5**: @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.  
> **username_1**: @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!  
> **username_0**: 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).  

---

### Answer by username_6 on 2012-05-04. Score: 6

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](http://www.sciencedirect.com/science/article/pii/0196677486900076).

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](http://www.springerlink.com/content/n82r1k7261145298/).

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


---

