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?