A theorem on polygon cutting with applications

Let P be a simple polygon with N vertices, each being assigned a weight ∈ 0, 1, and let C, the weight of P, be the added weight of all vertices. We prove that it is possible, in O (N) time, to find two vertices a, b in P, such that the segment ab lies entirely inside the polygon P and partitions it into two polygons, each with a weight not exceeding 2C/3. This computation assumes that all the vertices have been sorted along some axis, which can be done in O (Nlog N) time. We use this result to derive a number of efficient divide-and-conquer algorithms for: 1. Triangulating an N-gon in O (Nlog N) time. 2. Decomposing an N-gon into (few) convex pieces in O (Nlog N) time. 3. Given an O (Nlog N) preprocessing, computing the shortest distance between two arbitrary points inside an N-gon (i. e. , the internal distance), in O (N) time. 4. Computing the longest internal path in an N-gon in O (N2) time. In all cases, the algorithms achieve significant improvements over previously known methods, either by displaying better performance or by gaining in simplicity. In particular, the best algorithms for Problems 2, 3, 4, known so far, performed respectively in O (N2), O (N2), and O (N4) time.