Triangulating and guarding realistic polygons

G. Aloupis, P. Bose, V. Dujmovic, C.M. Gray, S. Langerman, B. Speckmann

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

87 Downloads (Pure)


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.
Originele taal-2Engels
Pagina's (van-tot)296-306
TijdschriftComputational Geometry
Nummer van het tijdschrift2, Part C
StatusGepubliceerd - 2014

Vingerafdruk Duik in de onderzoeksthema's van 'Triangulating and guarding realistic polygons'. Samen vormen ze een unieke vingerafdruk.

Citeer dit