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 in the interior of the object. In this abstract, we describe a simple algorithm for triangulating k-guardable polygons. Our algorithm, which is easily implementable, takes linear time assuming that k is constant.

Additional Metadata
Conference 20th Annual Canadian Conference on Computational Geometry, CCCG 2008
Citation
Aloupis, G, Bose, P, Dujmović, V, Gray, C., Langerman, S., & Speckmann, B. (2008). Triangulating and guarding realistic polygons. Presented at the 20th Annual Canadian Conference on Computational Geometry, CCCG 2008.