Triangulating and guarding realistic polygons (Q390140)

Realistic input models place certain restrictions on the shape of objects fed to geometric algorithms. In this way unusual worst-case examples are excluded and complexity bounds might mimic the observed behavior of an algorithm more accurately. The authors propose \(k\)-guardable objects as a new model of realistic input. They remark that \(\varepsilon\)-good polygons are \(k\)-guardable and show that their notion generalizes the notion of \((\alpha,\beta)\)-covered polygons (Theorem 1). Furthermore, they present two algorithms to triangulate a \(k\)-guardable polygon. The first algorithm is based on an involved subroutine, but does not need the guards as an input. The second algorithm uses visibility-polygon computations and requires the guards as an input. Both algorithms take linear time under the assumption that the number of guards is constant (Theorem 2, Theorem 3).