| Three problems about simple polygons \Lambda (2004) | |||||||||||||||||
Abstract | |||||||||||||||||
| Demaine, Kim, Kranakis, Lubiw, Maheshwari, Morin, Shin, Toussaint, Vigneron, and Yang, 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. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||