Three problems about simple polygons

We give three related algorithmic results concerning a simple polygon P:1.Improving a series of previous work, we show how to find a largest pair of disjoint congruent disks inside P in linear expected time.2.As a subroutine for the above result, we show how to find the convex hull of any given subset of the vertices of P in linear worst-case time.3.More generally, we show how to compute a triangulation of any given subset of the vertices or edges of P in almost linear time.