Touring a sequence of polygons

DOI10.1145/780542.780612zbMath1192.68354OpenAlexW2125334953MaRDI QIDQ3581275

Moshe Dror, Joseph S. B. Mitchell, Anna Lubiw, Alon Efrat

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780612

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (35)

Touring a sequence of disjoint polygons: complexity and extension ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Largest and smallest convex hulls for imprecise points ⋮ A linear-time 2-approximation algorithm for the watchman route problem for simple polygons ⋮ Inspecting a Set of Strips Optimally ⋮ Shortest paths in simple polygons with polygon-meet constraints ⋮ An Improved On-line Strategy for Exploring Unknown Polygons ⋮ The touring rays and related problems ⋮ Connectivity graphs of uncertainty regions ⋮ Online search for a hyperplane in high-dimensional Euclidean space ⋮ Improved exploration of unknown polygons ⋮ Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods ⋮ An improved algorithm for computing a shortest watchman route for lines ⋮ Facility location problems on graphs with non-convex neighborhoods ⋮ Minimum-link \(C\)-oriented paths visiting a sequence of regions in the plane ⋮ \(k\)-Transmitter watchman routes ⋮ Largest convex hulls for constant size, convex-hull disjoint clusters ⋮ Visiting a Polygon on the Optimal Way to a Query Point ⋮ A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane ⋮ Watchman tours for polygons with holes ⋮ Observation routes and external watchman routes ⋮ Shortest Paths in Graphs of Convex Sets ⋮ Shortest paths and convex hulls in 2D complexes with non-positive curvature ⋮ Complexity of minimum corridor guarding problems ⋮ Watchman routes for lines and line segments ⋮ Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems ⋮ Query-point visibility constrained shortest paths in simple polygons ⋮ Polynomial-time algorithms for the touring rays and related problems ⋮ Minimum cost \(b\)-matching problems with neighborhoods ⋮ On Romeo and Juliet problems: minimizing distance-to-sight ⋮ On Romeo and Juliet Problems: Minimizing Distance-to-Sight. ⋮ How to Keep an Eye on Small Things ⋮ Touring Disjoint Polygons Problem Is NP-Hard ⋮ Solving the Watchman Route Problem with Heuristic Search

This page was built for publication: Touring a sequence of polygons