patternMinor
Convex polygon formulation
Viewed 0 times
convexpolygonformulation
Problem
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.
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.
Solution
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 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.
Proof. Here.
Definition. $a_1,\ldots,a_n$ be $n$ non-negative reals. It satisfies (strict) $n$-gon inequality if $2a_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.
Context
StackExchange Computer Science Q#12516, answer score: 6
Revisions (0)
No revisions yet.