Triangulating and guarding realistic polygons

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

doi:10.1016/j.comgeo.2013.03.005

Triangulating and guarding realistic polygons

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

Research output: Contribution to journal › Article › Academic › peer-review

126 Downloads (Pure)

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	https://doi.org/10.1016/j.comgeo.2013.03.005
Publication status	Published - 2014

Access to Document

10.1016/j.comgeo.2013.03.005

triangulating-guarded-polygons-journalFinal author version , 332 KB

Cite this

@article{8ccce4c676aa417e919148c047737ea2,

title = "Triangulating and guarding realistic polygons",

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.",

author = "G. Aloupis and P. Bose and V. Dujmovic and C.M. Gray and S. Langerman and B. Speckmann",

year = "2014",

doi = "10.1016/j.comgeo.2013.03.005",

language = "English",

volume = "47",

pages = "296--306",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier",

number = "2, Part C",

}

TY - JOUR

T1 - Triangulating and guarding realistic polygons

AU - Aloupis, G.

AU - Bose, P.

AU - Dujmovic, V.

AU - Gray, C.M.

AU - Langerman, S.

AU - Speckmann, B.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1016/j.comgeo.2013.03.005

DO - 10.1016/j.comgeo.2013.03.005

M3 - Article

VL - 47

SP - 296

EP - 306

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 2, Part C

ER -

Triangulating and guarding realistic polygons

Abstract

Access to Document

Fingerprint

Cite this