Computing a shortest watchman path in a simple polygon in polynomial-time

DOI10.1007/3-540-60220-8_56MaRDI QIDQ5057427zbMATH OpenOpenAlexFDO

Authors Svante Carlsson, Håkan Jonsson

Publication date 16 December 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60220-8_56

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Finding the shortest watchman route in a simple polygon
• Shortest watchman routes in simple polygons
• Approximating a shortest watchman route
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• Optimum watchman routes

Cites work

• An optimal algorithm for detecting weak visibility of a polygon
• Computational complexity of art gallery problems
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Finding all weakly-visible chords of a polygon in linear time
• Finding the shortest watchman route in a simple polygon
• scientific article; zbMATH DE number 432849 (Why is no real title available?)
• scientific article; zbMATH DE number 437529 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 177566 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimum watchman routes
• Shortest watchman routes in simple polygons
• The zookeeper route problem

Cited in

(10)

• Watchman routes in the presence of a pair of convex polygons
• Fast computation of shortest watchman routes in simple polygons
• Optimally computing a shortest weakly visible line segment inside a simple polygon
• Shortest watchman tours in simple polygons under rotated monotone visibility
• Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
• Watchman routes for lines and line segments
• Complexity of minimum corridor guarding problems
• Moving an angle around a region
• Finding an approximate minimum-link visibility path inside a simple polygon
• Performance bounds for planning in unknown terrain

This page was built for publication: Computing a shortest watchman path in a simple polygon in polynomial-time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5057427)