Optimal line bipartitions of point sets

Let S be a set of n points in the plane. We study the following problem: Pa rtition S by a line into two subsets S-a and S-b such that max(f(S-a), f(S- b)) is minimal, where f is any monotone function defined over 2(S). We firs t present a solution to the case where the points in S are the vertices of a convex polygon and apply it to some common cases - f(S') is the perimeter , area, or width of the convex hull of S' subset of or equal to S - to obta in linear solutions (or O(n log n) solutions if the convex hull of S is not given) to the corresponding problems. This solution is based on an efficie nt procedure for finding a minimal entry in matrices of some special type, which we believe is of independent interest, For the general case we presen t a linear space solution which is in some sense output sensitive. It yield s solutions to the perimeter and area cases that are never slower and often faster than the best previous solutions.