Triangulating and guarding realistic polygons
We propose a new model of realistic input: k-guardable objects. An object is k-guardable if its boundary can be seen by k guards. We show that k-guardable polygons generalize two previously identified classes of realistic input. Following this, we give two simple algorithms for triangulating k-guardable polygons. One algorithm requires the guards as input while the other does not. Both take linear time assuming that k is constant and both are easily implementable.
|Keywords||Art gallery, Guarding, Polygon, Triangulation|
Aloupis, G, Bose, P, Dujmović, V, Gray, C. (Chris), Langerman, S. (Stefan), & Speckmann, B. (Bettina). (2014). Triangulating and guarding realistic polygons. Computational Geometry, 47(2 PART C), 296–306. doi:10.1016/j.comgeo.2013.03.005