Geometry Problem...

Zyaad Jaunnoo · Post by **Zyaad Jaunnoo** » Tue Sep 20, 2005 2:44 pm

Given some lengths, can we create a closed polygon with them?

What is the complexity of such algorithm if one exist?

E.g: Given 4, 4, 4, 4 we can build a square...

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Sep 20, 2005 4:22 pm

I believe it's always possible if only the longest edge is shorter than sum of all others.

GeorgeBusch · Post by **GeorgeBusch** » Wed Sep 21, 2005 11:24 am

Yes, what Krzysztof said is right, you can always create it, if longest edge < sum of the other edges.

This was one of the problems of this years Baltic Olympiad of Informatics. One Solution to find such a polygon is to put all the points on a circle and do a binary search over the radius. You can then calculate the arc each edge takes in the circle and if they add up to 360 degrees, you found a solution.

Its always possible to put them on a circle, cause you can always create such a polygon with the above algorithm...

Zyaad Jaunnoo · Post by **Zyaad Jaunnoo** » Wed Sep 21, 2005 11:34 am

Thank you very much..

Will that work for any number of edges? I mean not just poylgons with 4 sides..

GeorgeBusch · Post by **GeorgeBusch** » Wed Sep 21, 2005 11:17 pm

Yes that will work for any number of edges greater than 2

Martin Macko · Post by **Martin Macko** » Fri Sep 23, 2005 2:19 am

GeorgeBusch wrote:Yes that will work for any number of edges greater than 2

If you have just 2 edges, the longest one in never shorter then sum of the others (actually the shorter edge). Thus the condition works even for 2

Zyaad Jaunnoo · Post by **Zyaad Jaunnoo** » Fri Sep 23, 2005 7:44 pm

Is there an algorithm that searches for such a polygon.. if one exists?

Martin Macko · Post by **Martin Macko** » Sat Sep 24, 2005 12:20 am

Zyaad Jaunnoo wrote:Is there an algorithm that searches for such a polygon.. if one exists?

What's wrong with the algorithm GeorgeBusch's described?