Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 296-306 |
Journal | Computational Geometry |
Volume | 47 |
Issue number | 2, Part C |
DOIs | |
Publication status | Published - 2014 |