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 条

[31] FIST: Fast industrial-strength triangulation of polygons
Held, M
ALGORITHMICA, 2001, 30 (04) : 563 - 596
[32] Reprint of: 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, 2014, 47 (03): : 469 - 479
[33] Generalizing monotonicity: On recognizing special classes of polygons and polyhedra
Bose, P
Van Kreveld, M
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 2005, 15 (06) : 591 - 608
[34] A counterexample to an algorithm for computing monotone hulls of simple polygons
Toussaint, Godfried T.
El Gindy, Hossam
PATTERN RECOGNITION LETTERS, 1983, 1 (04) : 219 - 222
[35] Triangulating the Self: Identity Processes in a Connected Era
Davis, Jenny L.
SYMBOLIC INTERACTION, 2014, 37 (04) : 500 - 523
[36] Minimum Star Partitions of Simple Polygons in Polynomial Time
Abrahamsen, Mikkel
Blikstad, Joakim
Nusser, Andre
Zhang, Hanwen
PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024, 2024, : 904 - 910
[37] Triangulating input-constrained planar point sets
Held, Martin
Mitchell, Joseph S. B.
INFORMATION PROCESSING LETTERS, 2008, 109 (01) : 54 - 56
[38] BROOD GUARDING IN A BETHYLID WASP
HARDY, ICW
BLACKBURN, TM
ECOLOGICAL ENTOMOLOGY, 1991, 16 (01) : 55 - 62
[39] Exact Algorithms for Terrain Guarding
Ashok, Pradeesha
Fomin, Fedor, V
Kolay, Sudeshna
Saurabh, Saket
Zehavi, Meirav
ACM TRANSACTIONS ON ALGORITHMS, 2018, 14 (02)
[40] On guarding the vertices of rectilinear domains
Katz, Matthew J.
Roisman, Gabriel S.
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2008, 39 (03): : 219 - 228

← 1 2 3 4 5 →