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 条

[41] A τ-Conjecture for Newton Polygons
Koiran, Pascal
Portier, Natacha
Tavenas, Sebastien
Thomasse, Stephan
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2015, 15 (01) : 185 - 197
[42] A mimetic method for polygons
Perot, J. Blair
Chartrand, Chris
JOURNAL OF COMPUTATIONAL PHYSICS, 2021, 424
[43] Guarding Strategic Points of a Gallery
Moghaddam, Mohammad Hosseinzadeh
Bagheri, Alireza
Mamaghani, Ali Safari
Afshord, Saied Taghavi
PROCEEDINGS OF THE 2009 INTERNATIONAL CONFERENCE ON COMPUTER TECHNOLOGY AND DEVELOPMENT, VOL 1, 2009, : 121 - +
[44] On polygons in Lorentzian plane
Desideri, Graciela. M.
COMPTES RENDUS DE L ACADEMIE BULGARE DES SCIENCES, 2007, 60 (10): : 1039 - 1046
[45] METRIC INEQUALITIES FOR POLYGONS
Durnitreseir, Adrian
JOURNAL OF COMPUTATIONAL GEOMETRY, 2013, 4 (01) : 79 - 93
[46] Extended Formulations for Polygons
Samuel Fiorini
Thomas Rothvoß
Hans Raj Tiwary
Discrete & Computational Geometry, 2012, 48 : 658 - 668
[47] Extended Formulations for Polygons
Fiorini, Samuel
Rothvoss, Thomas
Tiwary, Hans Raj
DISCRETE & COMPUTATIONAL GEOMETRY, 2012, 48 (03) : 658 - 668
[48] Triangulating graphs with few P4's
Babel, L
DISCRETE APPLIED MATHEMATICS, 1998, 89 (1-3) : 45 - 57
[49] Guarding disjoint triangles and claws in the plane
Tóth, CD
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2003, 25 (1-2): : 51 - 65
[50] Meta-Meshing and Triangulating Lattice Structures at a Large Scale
Zou, Qiang
Gao, Yunzhu
Luo, Guoyue
Chen, Sifan
COMPUTER-AIDED DESIGN, 2024, 174

← 1 2 3 4 5 →