Change search
ReferencesLink to record
Permanent link

Direct link
Computing a shortest watchman path in a simple polygon in polynomial-time
Luleå tekniska universitet.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
1995 (English)In: Algorithms and Data Structures 4th International Workshop, WADS '95, Proceedings / [ed] Selim G. Akl, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1995, 122-134 p.Conference paper (Refereed)
Abstract [en]

In this paper we present the first polynomial-time algorithm for finding the shortest polygonal chain in a simple polygon such that each point of the polygon is visible from some point on the chain. This chain is called the shortest watchman path, or equivalently, the shortest weakly visible curve of the polygon. In proving this result we also give polynomial time algorithms for finding the shortest aquarium-keeper's path that visits all edges of the polygon, and for finding the shortest postman path that visits all vertices of a polygon.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1995. 122-134 p.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 995
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-38926DOI: 10.1007/3-540-60220-8Local ID: d7be0810-a0e2-11db-8975-000ea68e967bISBN: 978-3-540-60220-0 (print)OAI: diva2:1012433
International Workshop on Algorithms and Data Structures : 16/08/1995 - 18/08/1995
Godkänd; 1995; 20070110 (ysko)Available from: 2016-10-03 Created: 2016-10-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Håkan
By organisation
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 2 hits
ReferencesLink to record
Permanent link

Direct link