Convex polygon formulation

Problem Detail: 

We have a sorted list of side lengths that can be used to form a polygon. There are $n$ such values ($n \le 1000$).

Now we need to find if we can use any 10 of these values to form a non-degenerate convex polygon.

How do we approach this? Anything up to the order of $O(n^2 \log n)$ is acceptable. Better if possible. I need the general idea on how to proceed, the properties of convex polygons which can be exploited here, etc.

Asked By : Alice

Answered By : Chao Xu

Theorem 1. For every polygon with edge length sequence $a_1,\ldots,a_m$, there exist a convex polygon with same edge length sequence.

Proof. Here.

Definition. $a_1,\ldots,a_n$ be $n$ non-negative reals. It satisfies (strict) $n$-gon inequality if $2a_j < \sum_{i=1}^n a_i$ for all $j$.

Theorem 2. The sequence $a_1,\ldots,a_n$ is a sequence of edge length for a polygon iff it satisfies $n$-gon inequality.

Proof. Here. (note the proof here requires advanced math and also proves Theorem 1)

The problem reduce to:

Given a sequence of $n$ non-negative reals, find a $k$ element subsequence that satisfies $k$-gon inequality.

An simple algorithm: Check if $a_i,\ldots,a_{i+k-1}$ is a solution for every $1 \leq i\leq n-k+1$. If none of them work, then there is no solution.

Proof. If we have any solution $a_{i_1},\ldots,a_{i_k}$, find the largest $j$, such that $a_{i_{j+1}}-a_{i_j}>1$, (i.e. there is a gap). If there is no such gap then we are done. If there is one, then $a_{i_2},\ldots,a_{i_{j}},a_{i_{j+1}-1},a_{i_{j+1}},\ldots,a_{i_k}$ is also a solution. (intuitively, we used the largest element in the gap and removed the smallest element). We can repeat this step (at most $k-1$ times) and fill in all the gaps. Eventually we produced a solution of the form $a_{i_k}-k+1,a_{i_k}-k,\ldots,a_{i_k}-1,a_{i_k}$ for some $i$.

The algorithm can be done naively in $O(kn)$ time. Maybe there is a smarter way to do it.

A interesting follow up question:

Given a sequence of $n$ non-negative reals, find the longest subsequence $S$, such that every $k$ element subsequence of $S$ satisfies $k$-gon inequality.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12516