Result: A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

Title:
A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
Authors:
XUEHOU TAN
Source:
Theory and applications of models of computationTheoretical computer science. 384(1):92-103
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 18 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Géométrie, Geometry, Analyse numérique. Calcul scientifique, Numerical analysis. Scientific computation, Analyse numérique, Numerical analysis, Approximation numérique, Numerical approximation, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Divers, Miscellaneous, Algorithme approximation, Approximation algorithm, Algoritmo aproximación, Approximation linéaire, Linear approximation, Aproximación lineal, Calcul automatique, Computing, Cálculo automático, Géométrie algorithmique, Computational geometry, Geometría computacional, Informatique théorique, Computer theory, Informática teórica, Segment droite, Line segment, Segmento recta, Temps linéaire, Linear time, Tiempo lineal, Visibilité, Visibility, Visibilidad, 51E12, 65D18, 68U05, 68W25, 68Wxx, Algorithme linéaire, Algorithme temps linéaire, Polygone simple, Approximation algorithms, Essential cuts, Polygon visibility, Watchman route problem
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
School of High-Technology for Human Welfare, Tokai University, 317 Nishino, Numazu 410-0395, Japan
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19069683
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.19069683
Database:
PASCAL Archive

Further Information

Given a simple polygon P of n vertices, the watchman route problem asks for a shortest (closed) route inside P such that each point in the interior of P can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O (n4 log n) time, which is too complicated to be suitable in practice. This paper also involves an optimal O(n) time algorithm for computing the set of so-called essential cuts, which are the line segments inside the polygon P such that any route visiting them is a watchman route. It solves an intriguing open problem by improving the previous O (n log n) time result, and is thus of interest in its own right.