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 条

[21] Covering points with orthogonally convex polygons
Genc, Burkay
Evrendilek, Cem
Hnich, Brahim
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2011, 44 (05): : 249 - 264
[22] Diffuse reflection diameter in simple polygons
Barequet, Gill
Cannon, Sarah M.
Fox-Epstein, Eli
Hescott, Benjamin
Souvaine, Diane L.
Toth, Csaba D.
Winslow, Andrew
DISCRETE APPLIED MATHEMATICS, 2016, 210 : 123 - 132
[23] GUARDING RECTANGULAR PARTITIONS
Dinitz, Yefim
Katz, Matthew J.
Krakovski, Roi
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2009, 19 (06) : 579 - 594
[24] An Approach To Triangulate Area Bounded Simple Polygons
Tereshchenko, Vasyl
Kolianova, Tania
Tereshchenko, Yaroslav
2017 IEEE FIRST UKRAINE CONFERENCE ON ELECTRICAL AND COMPUTER ENGINEERING (UKRCON), 2017, : 655 - 658
[25] DYADIC POLYGONS
Matczak, K.
Romanowska, A. B.
Smith, J. D. H.
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2011, 21 (03) : 387 - 408
[26] The σ-visibility of polygons
Qin, ZP
Zhang, HG
FIFTH INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS, VOLS 1 AND 2, 1997, : 297 - 302
[27] Counting triangulations of almost-convex polygons
Hurtado, F
Noy, M
ARS COMBINATORIA, 1997, 45 : 169 - 179
[28] Memory-constrained algorithms for simple polygons
Asano, Tetsuo
Buchin, Kevin
Buchin, Maike
Korman, Matias
Mulzer, Wolfgang
Rote, Guenter
Schulz, Andre
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2013, 46 (08): : 959 - 969
[29] CERTAIN CLASSES OF POLYGONS IN R-2 AND AREAS OF POLYGONS
Radic, Mirko
Susanj, Rene
Trinajstic, Nenad
RAD HRVATSKE AKADEMIJE ZNANOSTI I UMJETNOSTI-MATEMATICKE ZNANOSTI, 2009, 16 (503): : 7 - 12
[30] Triangulating Unknown Environments using Robot Swarms
Becker, Aaron
Fekete, Sandor P.
Kroeller, Alexander
Lee, Seoung Kyou
McLurkin, James
Schmidt, Christiane
PROCEEDINGS OF THE TWENTY-NINETH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SOCG'13), 2013, : 345 - 346

← 1 2 3 4 5 →