Triangulating and guarding realistic polygons

被引：0

作者：

Aloupis, Greg ^{[1
,2
]}

Bose, Prosenjit ^{[1
]}

Dujmovic, Vida ^{[1
]}

Gray, Chris ^{[3
]}

Langerman, Stefan ^{[4
]}

Speckmann, Bettina ^{[3
]}

机构：

[1] Carleton Univ, Ottawa, ON K1S 5B6, Canada

[2] Univ Libre Bruxelles, Brussels, Belgium

[3] TU Eindhoven, Eindhoven, Netherlands

[4] Univ Libre Bruxelles, Chercheur Qualifie FNRS, Brussels, Belgium

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2014年 / 47卷 / 02期

关键词：

Triangulation; Art gallery; Guarding; Polygon; LINEAR ALGORITHM; CONVEX-HULL; POINT; COMPLEXITY; GALLERIES; POLYHEDRA; OBJECTS; TIME;

D O I：

10.1016/j.comgeo.2013.03.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2013 Published by Elsevier B.V.

引用

页码：296 / 306

页数：11

共 50 条

[1] TRIANGULATING POLYGONS WITHOUT LARGE ANGLES
BERN, M
DOBKIN, D
EPPSTEIN, D
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (1-2) : 171 - 192
[2] On triangulating three-dimensional polygons
Barequet, G
Dickerson, M
Eppstein, D
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1998, 10 (03): : 155 - 170
[3] Guarding polygons with holes for robot motion planning applications
Elnagar, A
Lulu, L
2004 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN & CYBERNETICS, VOLS 1-7, 2004, : 923 - 928
[4] APPROXIMATION ALGORITHMS FOR GUARDING HOLEY POLYGONS
Moghaddam, M. H.
Divdel, H.
Alipour, G.
JOURNAL OF FUNDAMENTAL AND APPLIED SCIENCES, 2016, 8 : 1063 - 1068
[5] Inapproximability results for guarding polygons and terrains
Eidenbenz, S
Stamm, C
Widmayer, P
ALGORITHMICA, 2001, 31 (01) : 79 - 113
[6] The Parameterized Complexity of Guarding Almost Convex Polygons
Agrawal, Akanksha
Knudsen, Kristine V. K.
Lokshtanov, Daniel
Saurabh, Saket
Zehavi, Meirav
DISCRETE & COMPUTATIONAL GEOMETRY, 2024, 71 (02) : 358 - 398
[7] K-vertex guarding simple polygons
Salleh, Ihsan
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2009, 42 (04): : 352 - 361
[8] The Parameterized Complexity of Guarding Almost Convex Polygons
Akanksha Agrawal
Kristine V. K. Knudsen
Daniel Lokshtanov
Saket Saurabh
Meirav Zehavi
Discrete & Computational Geometry, 2024, 71 : 358 - 398
[9] Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
Ashur, Stav
Filtser, Omrit
Katz, Matthew J.
Saban, Rachel
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2022, 101
[10] New bounds on guarding problems for orthogonal polygons in the plane using vertex guards with halfplane vision
Daescu, Ovidiu
Malik, Hemant
THEORETICAL COMPUTER SCIENCE, 2021, 882 : 63 - 76

← 1 2 3 4 5 →