Observation routes and external watchman routes
From MaRDI portal
Publication:6179428
DOI10.1007/978-3-031-38906-1_26arXiv2306.11522OpenAlexW4385357601MaRDI QIDQ6179428
Csaba D. Tóth, Adrian Dumitrescu
Publication date: 16 January 2024
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2306.11522
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Shortest watchman routes in simple polygons
- On the complexity of approximating TSP with neighborhoods and related problems
- On the geometric dilation of closed curves, graphs, and point sets
- Geometric dilation of closed planar curves: New lower bounds
- Optimum watchman routes
- Watchman routes under limited visibility
- The Euclidean traveling salesman problem is NP-complete
- Watchman routes in the presence of a pair of convex polygons
- Approximation algorithms for the Geometric Covering Salesman Problem
- Fast computation of shortest watchman routes in simple polygons
- Finding the shortest watchman route in a simple polygon
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- A linear-time 2-approximation algorithm for the watchman route problem for simple polygons
- A threshold of ln n for approximating set cover
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Combinatorial Optimization with Explicit Delineation of the Ground Set by a Collection of Subsets
- Touring a sequence of polygons
- APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- On the hardness of approximating minimization problems
- Approximation algorithms for TSP with neighborhoods in the plane
- CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
- How to Keep an Eye on Small Things
- The Art Gallery Problem is ∃ℝ-complete
- Analytical approach to parallel repetition
- TSP with neighborhoods of varying size
- Approximating Watchman Routes
- Parameterized Hardness of Art Gallery Problems
- Inapproximability results for guarding polygons and terrains
