2007
05.12

Min Area Convex Polygon with k sides

Consider the following natural problem: Given a set **P** of **n** points in the plane, and a number **k**, find the smallest area _convex_ polygon that contains all the points of **P** and has exactly **k** edges. This is a natural question that was solved more than 20 years ago, and here I quickly sketch the (cute) solution and some key observations.

So, let **C** be the convex hull of **P**. Consider the unknown optimal polygon **S**. An edge of **S** is _flush_ if it contains an edge of **C**. Assume for the time being that all edges are flushed. Then it is not too hard to compute in (say) **O( n5)** time (but faster time is possible with a bit of thinking, but heck, I don’t care – I just want a polynomial time algorithm right now). Indeed, the recursive problem would be specified by two edges of **C** and a number **k**, and the answer would be the smallest area chain with **k** edges which starts and ends at these two edges. Now using memoization the above running time follows.

Unfortunately, morosely, dejectedly, wistfully, sorrowfully, dolefully, grievously, gloomily, joylessly, dismally, and cheerlessly, it could be that there are edges in the optimal solution that are unflushable (not to be confused with the other interpretation of this word).

Here is how an unflushable edge looks like.

!unflushable edge

We are assuming that the two edges adjacent to the unflushable edge **e** in the optimal solution has their supporting lines intersect on the other side of **e** than **C**, as in the figure. Note, that there is at most one unflushable edge which is not of this type for **k>3** (since the turning angle along the boundary of **C** on the two angles adjacent to **e** is more than **pi**). So, let us show that an unflushable edge (of this type) can be flushed.

The first observation is that an unflushable edge, must have the vertex it hinges on, smack in the middle of the edge **e**. Otherwise, we can slightly (aka infinitesimally) rotate the edge into the polygon **S** into the longer side of **e**.
!middle edge
As any half a moron with a quarter of a brain who is not blind can see, the area of **S** shrinks (if you are not a moron, then well, you would just have to find one to explain this to you). This is impossible, as **S** is the minimum area solution.

So, consider the case when the hinge point **p** is in the middle of the unflushable edge **e**. Let **h** be the line supporting the counterclockwise edge from **e**, and reflect it through **p**. By reflectionism (a common early Greek belief that stated that if you reflect a vertex of an edge through a point in the middle of the edge, the image of the reflection would be the other endpoint – this is sometime confused in the literature with Pastafarianism), the reflected line **h’** passes through the other endpoint of **e** and it is parallel to **h**.

!middle edge

Now, rotate **e** slightly around **p**, say clockwise, and consider the new area:

!middle edge

We lose the green area, but gain the yellow area. But by reflectionism (again, not be confused with the invisible pink unicorn), we have that the green area is larger:

!middle edge

So, again, we get a smaller solution than **S**, which is impossible. (Surprisingly, the same argument works if you rotate in the other direction. Namely, **S** is in fact a local maximum of the area, as far as rotation around **p**.)

Thus, there are no unflushable edges in **S** of this type.

But there is at most one unflushable edge in the optimal solution **S** that is not of this type if **k >3**. (For **k=3** we can get a triangle with all three edges being unflushable – but this is an easy case that can be handled by a direct approach.) It is now easy to modify the dynamic programming to handle this case, by guessing the hinge vertex. We conclude that in polynomial time (say **O(n7)**) one can compute the smallest area polygon with **k** edges,

For people interested in more details (and way faster algorithm), see here.

And now that I am done with this blog entry, I can start looking for Russel’s teapot – the poor guy didn’t have tea in like forever.