Computing a shortest watchman path in a simple polygon in polynomial-time
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)
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
IdentifiersURN: 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: oai:DiVA.org:ltu-38926DiVA: diva2:1012433
International Workshop on Algorithms and Data Structures : 16/08/1995 - 18/08/1995
Godkänd; 1995; 20070110 (ysko)2016-10-032016-10-03Bibliographically approved