Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem

Problem. Find in linear time a diagonal of $P$ such that the absolute difference of the areas of the obtained polygons is as small as possible.

It is easy to solve the problem if one knows through which vertex must the diagonal pass but I do not see if this sub-problem is solvable in linear time.

Anyone happens to see a linear time algorithm for the stated problem?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Start with some diagonal $AB$ and alternate between moving $A$ along the boundary until the difference between the diagonals switches sign and doing the same with $B$ in the same direction. When they've both completed one revolution, you've spent linear time and you must have encountered the desired diagonal.

share|improve this answer
    
Thank you for the answer. Could you please explain it a bit further? I don't quite understand why this algorithm works properly and what is its key idea. –  Jernej Nov 26 '12 at 16:10
    
@Jernej: The desired diagonal must be such that reducing the larger part (by moving either point) switches the sign of the difference (else it would reduce the absolute difference). The algorithm traverses all diagonals with this property, since for each point there is exactly one pair of opposite points between which the sign changes, and the algorithm finds that pair for each point. –  joriki Nov 26 '12 at 16:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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