7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ May I ask what you need this for? Your specific bounds on input and time are interesting... Either way, sounds like a hard question. $\endgroup$ – jmite Jun 7 '13 at 21:15
  • 1
    $\begingroup$ Two observations: convexity is not important. See this: cs.mcgill.ca/~cs507/projects/1998/mas/main2.html It's easy to determine if one can build a polygon from set of lengths: mathoverflow.net/questions/96617/… $\endgroup$ – Chao Xu Jun 7 '13 at 21:24
  • $\begingroup$ Is this for the TKCONVEX problem on Codechef? The point of these contests is to find the relevant algorithms or at least the relevant literature on your own. (Note that on Computer Science, we have no policy against ongoing contests, unlike Mathematics.) $\endgroup$ – Gilles Jun 10 '13 at 9:35
  • $\begingroup$ @Gilles even the algorithm below will give one WA. This is not enough to get the problem correct. And we are undergrad students who are not that good at programming, but we want to learn. And contests motivate everyone. And If we learn even 10 new algorithms per contest, the gain is huge. If someone points us into the right direction (note that just pointing, no codes, nothing), there are more chances that we would learn the actual algorithm for the problem. So just trying to learn.. if I solve a problem more, that wont effect the leaderboard. So i think it doesn't matter, if it helps us learn $\endgroup$ – Alice Jun 10 '13 at 12:47
  • $\begingroup$ I think Codechef has a discussion forum where people post solutions after the contest is over. $\endgroup$ – Chao Xu Jun 13 '13 at 9:17
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ that theorem 2 is that an extension of triangle inequality? And why is sorting necessary? We can choose any k-subset of the given points that satisfies the second theorem. $\endgroup$ – Alice Jun 7 '13 at 22:41
  • $\begingroup$ You don't have to sort, sorting just brings down the time complexity: check only $O(n)$ subsequences instead of $2^n$. $\endgroup$ – Chao Xu Jun 7 '13 at 22:47
  • $\begingroup$ doesn't seem to work. are you sure we have to check only n-k polygons? $\endgroup$ – Alice Jun 8 '13 at 0:12
  • $\begingroup$ Please provide a example when this doesn't work. $\endgroup$ – Chao Xu Jun 8 '13 at 6:33
  • 3
    $\begingroup$ There is a slightly better way to do it. Keep a running total of the last $k$ edges (by adding $a_{i+k}$ to and subtracting the $a_i$ from this running total), and use this running total to check the $k$-gon inequality. This reduces the time from $O(kn)$ to $O(n)$. $\endgroup$ – Peter Shor Jun 8 '13 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.