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.

Keywords: Geometric optimization; Polygon triangulation; Convex hull