Minimum-link watchman tours

Esther M. Arkin; Joseph S.B. Mitchell; Christine D. Piatko

doi:10.1016/S0020-0190(02)00502-1

Minimum-link watchman tours

Esther M. Arkin
, Joseph S.B. Mitchell
, Christine D. Piatko

Applied Mathematics and Statistics

APL

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

40 Scopus citations

Abstract

We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of O(logn).

Original language	English
Pages (from-to)	203-207
Number of pages	5
Journal	Information Processing Letters
Volume	86
Issue number	4
DOIs	https://doi.org/10.1016/S0020-0190(02)00502-1
State	Published - May 31 2003

Keywords

Approximation algorithms
Computational geometry
Link distance
NP -complete
Polygons
Watchman route

Access to Document

10.1016/S0020-0190(02)00502-1

Cite this

@article{a79eddc8ca864034aa22cf3bd5af4074,

title = "Minimum-link watchman tours",

abstract = "We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of O(logn).",

keywords = "Approximation algorithms, Computational geometry, Link distance, NP -complete, Polygons, Watchman route",

author = "Arkin, \{Esther M.\} and Mitchell, \{Joseph S.B.\} and Piatko, \{Christine D.\}",

year = "2003",

month = may,

day = "31",

doi = "10.1016/S0020-0190(02)00502-1",

language = "English",

volume = "86",

pages = "203--207",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "4",

}

TY - JOUR

T1 - Minimum-link watchman tours

AU - Arkin, Esther M.

AU - Mitchell, Joseph S.B.

AU - Piatko, Christine D.

PY - 2003/5/31

Y1 - 2003/5/31

N2 - We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of O(logn).

AB - We consider the problem of computing a watchman route in a polygon with holes. We show that the problem of finding a minimum-link watchman route is NP-complete, even if the holes are all convex. The proof is based on showing that the related problem of finding a minimum-link tour on a set of points in the plane is NP-complete. We provide a provably good approximation algorithm that achieves an approximation factor of O(logn).

KW - Approximation algorithms

KW - Computational geometry

KW - Link distance

KW - NP -complete

KW - Polygons

KW - Watchman route

UR - https://www.scopus.com/pages/publications/0037475189

U2 - 10.1016/S0020-0190(02)00502-1

DO - 10.1016/S0020-0190(02)00502-1

M3 - Article

AN - SCOPUS:0037475189

SN - 0020-0190

VL - 86

SP - 203

EP - 207

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

Minimum-link watchman tours

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this