Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
