PROBLEM LINK:Author: Praveen Dhinwa DIFFICULTY:Hard PREREQUISITES:Geometry PROBLEM:Given $n$ points each with a positive weight, find the minimum weighted convex polygon with $k$ vertices chosen among the $n$ points. Do this for all $k$ from $3$ to $n$. The weight of a polygon is the sum of the weights of the points enclosed by it (including the boundaries). SHORT EXPLANATIONSuppose we fix a point $p_1$ as the lower right corner of the polygon we are about to construct. We will sort all the valid points (i.e. those that are above $p_1$) in counter clock wise direction with respect to $p_1$. Now let us define $dp(p_3, p_2, k)$ as the minimum weighted polygon which has $p_1$ as the lowest point, $p_3$ and $p_2$ are the last two added points and we have to add $k$ more vertices. Now, for all vertices in counter clock wise order, we try adding each point $i$ which is to the left of the line connecting $p2$ to $p3$ and recursively solve the $dp(i, p3, k + 1)$ and add we also add the weights of the point inside the triangle $p2  p3  i$. We take minimum over all such $i$ and that will be the answer for $dp(p_3, p_2, k)$. Now we try fixing each of the point as the lower most one (i.e. $p_1$) and do the above procedure. For each $k$, we take minimum over all such fixed points. We do this for all $k$ (3 \leq k \leq n) to get the final answer$. EXPLANATION:Let us fix a point $p_1$ as the bottom most point of the polygon (i.e. the one with the least $y$ coordinate). Since this is the bottom most point, we can ignore all the points which have $y$ values less than $p_1$. Now we sort the remaining points in counter clockwise direction. We want to get the minimum weighted convex polygon for each $k$ having $p_1$ as the bottom most point. The key observation is that suppose we have a minimum weighted convex polygon with $k$ vertices, then if we remove any vertex, we will be left with a minimum weighted convex polygon of $k  1$ vertices having $p_1$ as the bottom most point. So, to get the answer for $k$, we try adding each valid point as the next vertex and solve the problem for $k  1$ vertices. Then take the minimum over all such valid points to get the minimum value for $k$ vertices. In other words, we are building the polygon triangle by triangle. What other information are needed for implementing this?
Let the function $dp(p_3, p_2, k)$ return the minimum weighted convex polygon with $p_1$ as the bottom most vertex, $p_3$ and $p_2$ as the last two vertex and $k$ vertices remaining to be added. Now we loop through all valid points $i$ which are ahead of $p_3$ in counter clockwise order and see if can add $i$ to the polygon. We can add $i$ only if it is to the left of the line formed by $p_2  p_3$. Otherwise the angle made by $p_2  p_3  i$ will be greater than 180 degrees and hence it won't be a convex polygon. Now to get the weight, we recursively solve for $dp(i, p3, k  1)$ and add the weights of the points inside the triangle formed by $p_2  p_3  i$ to the weight. We try this for all $i$ and the minimum among them would be the answer. Finally note that for a fixed $p_1$, the state may repeat. So, we memoize the values to avoid recalculation. For getting the final answer, we loop through all points and fix them as $p_1$. Then we store all the points which are not below $p_1$ and sort them in counter clockwise order. Now we have to select the next 2 vertices of the polygon. So we loop through all pairs of valid points and keep them as the next 2 vertices. Finally we need to solve for all $k$, so we will loop for $k$ from 3 to $n$ and call $dp(p3, p2, k  3)$ to get the answer for this case. We keep updating the minimum weighted polygon for $k$ vertices using this value. Please consult author's solution for the sample implementation of this idea. Time Complexity:$\mathcal{O} (n^5)$
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 May '15, 21:01
