Optimum watchman routes

No abstract is available for this paper.

• Publication year

  1986

• Venue

  SCG '86

• Publication date

  1986-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/10515.10518
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Linear time algorithms for visibility and shortest path problems inside simple polygons

  2011cited by this paper
• Art gallery theorems and algorithms

  1987cited by this paper
• On Gallery Watchmen in Grids

  1986cited by this paper
• Computational complexity of art gallery problems

  1986cited by this paper
• Decomposing polygonal regions into convex quadrilaterals

  1985cited by this paper
• Computing the Extreme Distances Between Two Convex Polygons

  1985cited by this paper
• Stationing guards in rectilinear art galleries

  1984cited by this paper
• Euclidean shortest paths in the presence of rectilinear barriers

  1984influential reference
• Triangulating Simple Polygons and Equivalent Problems

  1984cited by this paper
• Galleries need fewer mobile guards: A variation on Chvátal's theorem

  1983cited by this paper
• An alternate proof of the rectilinear art gallery theorem

  1983influential reference
• Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons

  1983cited by this paper
• Traditional Galleries Require Fewer Watchmen

  1983cited by this paper
• An efficient algorithm for decomposing a polygon into star-shaped polygons

  1981cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper
• Triangulating a Simple Polygon

  1978cited by this paper
• A short proof of Chvátal's Watchman Theorem

  1978cited by this paper
• The Euclidean Traveling Salesman Problem is NP-Complete

  1977cited by this paper
• A combinatorial theorem in plane geometry

  1975cited by this paper

• Shell-based workspace decomposition for rapid multi-goal path planning in up-close fruit tree inspection

  2026cites this paper
• Multi-robot Searching with Limited Sensing Range for Static and Mobile Intruders

  2025cites this paper
• Multiple Watchman Routes in Staircase Polygons

  2025influential citation
• The Contiguous Art Gallery Problem is in Θ(n log n)

  2025cites this paper
• Anytime Metaheuristic Framework for Global Route Optimization in Expected-Time Mobile Search

  2025cites this paper
• A Unified and Scalable Method for Optimization over Graphs of Convex Sets

  2025cites this paper
• Multirobot Watchman Routes in a Simple Polygon

  2024cites this paper
• Facet-Hamiltonicity

  2024cites this paper
• Coverage Path Planning For Minimizing Expected Time to Search For an Object With Continuous Sensing

  2024cites this paper
• Approximation Algorithms for Anchored Multiwatchman Routes

  2024cites this paper
• Optimizing Visibility-based Search in Polygonal Domains

  2024influential citation
• Fixed parameter tractable algorithms for watchman route related problems on line segment arrangements

  2024cites this paper
• Time-optimal ergodic search: Multiscale coverage in minimum time

  2024cites this paper
• Time Optimal Ergodic Search

  2023cites this paper
• Observation Routes and External Watchman Routes

  2023cites this paper
• Approximation Algorithms for the Two-Watchman Route in a Simple Polygon

  2023cites this paper
• Decision-Theoretic Approaches for Robotic Environmental Monitoring - A Survey

  2023cites this paper
• Relay Pursuit for Multirobot Target Tracking on Tile Graphs

  2023cites this paper
• Efficiently Guiding K-Robots Along Pathways with Minimal Turns

  2023cites this paper
• Optimally Solving the Multiple Watchman Route Problem with Heuristic Search (Extended Abstract)

  2022cites this paper
• Occlusion-Aware Motion Planning of Autonomous Robots in Cluttered and Unknown Environments

  2022cites this paper
• Optimal placement of base stations in border surveillance using limited capacity drones

  2022cites this paper
• Improved exploration of unknown polygons

  2022cites this paper
• MASS: Multi-Agent Scheduling System for Intelligent Surveillance

  2022cites this paper
• Perpetual maintenance of machines with different urgency requirements

  2022cites this paper
• Solving the Watchman Route Problem with Heuristic Search

  2022cites this paper
• A Computational Geometry-based Approach for Planar k-Coverage in Wireless Sensor Networks

  2022cites this paper
• Towards a Continuous Solution of the $d$-Visibility Watchman Route Problem in a Polygon With Holes

  2022cites this paper
• A Robust and Fast Occlusion-based Frontier Method for Autonomous Navigation in Unknown Cluttered Environments

  2022cites this paper
• k-Transmitter Watchman Routes

  2022influential citation
• The touring rays and related problems

  2021cites this paper
• Shortest Paths in Graphs of Convex Sets

  2021cites this paper
• Autonomous mobile robots

  2021influential citation
• Feasibility study of urban flood mapping using traffic signs for route optimization

  2021cites this paper
• Using coverage path planning methods for car park exploration

  2021cites this paper
• Roadmap for Visibility-based Target Tracking: Iterative Construction and Motion Strategy

  2021cites this paper
• Suboptimally Solving the Watchman Route Problem on a Grid with Heuristic Search

  2021cites this paper
• Polynomial-Time Algorithms for the Touring Rays and Related Problems

  2020cites this paper
• Solving the Watchman Route Problem on a Grid with Heuristic Search

  2020cites this paper
• Path planning algorithms for single and multiple mobile robot systems

  2020influential citation
• Combining Geometric and Information-Theoretic Approaches for Multi-Robot Exploration

  2020cites this paper
• Dynamic Guard Patrol in Stealth Games

  2020cites this paper
• Deep-Learning-Aided Path Planning and Map Construction for Expediting Indoor Mapping

  2020cites this paper
• Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility

  2020influential citation
• Techniques in Multi-Robot Area Coverage

  2020cites this paper
• Building two communication towers over a terrain

  2020cites this paper
• On competitive strategies for external exploration of a convex polygon

  2020cites this paper
• Stochastic Multi-Robot Patrolling with Limited Visibility

  2019cites this paper
• An Integrated Approach to Goal Selection in Mobile Robot Exploration

  2019cites this paper
• On the optimal placement of cameras for surveillance and the underlying set cover problem

  2019cites this paper
• Path planning with Incremental Roadmap Update for Visibility-based Target Tracking

  2019cites this paper
• Review: Using Unmanned Aerial Vehicles (UAVs) as Mobile Sensing Platforms (MSPs) for Disaster Response, Civil Security and Public Safety

  2019cites this paper
• On Romeo and Juliet Problems: Minimizing Distance-to-Sight

  2019cites this paper
• Fixed-Parameter Tractable Algorithms for Corridor Guarding Problems

  2019cites this paper
• Patrolling on Dynamic Ring Networks

  2018cites this paper
• Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes

  2018cites this paper
• Visibility-Based Monitoring of a Path Using a Heterogeneous Robot Team

  2018influential citation
• Persistent Monitoring with Refueling on a Terrain Using a Team of Aerial and Ground Robots

  2018influential citation
• A Dynamical System Approach for Resource-Constrained Mobile Robotics

  2018cites this paper
• An improved algorithm for computing a shortest watchman route for lines

  2018cites this paper
• A Minimax Tree Based Approach for Minimizing Detectability and Maximizing Visibility

  2018cites this paper
• An Integrated Exploration and Observation Planning for an Efficient Indoor 3 D Mapping Diar

  2017cites this paper
• An efficient algorithm for touring a sequence of given convex polygons in the plane

  2017cites this paper
• A GRASP Metaheuristic for the Coverage of Grid Environments with Limited-Footprint Tools

  2017cites this paper
• Monotone Paths with Visibility Properties

  2017influential citation
• Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems

  2017cites this paper
• 31 SHORTEST PATHS AND NETWORKS

  2017cites this paper
• Evolutionary algorithm for positioning cameras networks mounted on UAV

  2017influential citation
• Intelligent robotic system for autonomous exploration and active SLAM in unknown environments

  2017cites this paper
• Algorithms for Persistent Autonomy and Surveillance by Cenk Baykal

  2017cites this paper
• An integrated exploration and observation planning for an efficient indoor 3D mapping

  2017cites this paper
• Discrete Surveillance Tours in Polygonal Domains

  2017cites this paper
• Multi-vehicle patrolling with limited visibility and communication constraints

  2017cites this paper
• View Point Planning for Inspecting Static and Dynamic Scenes with Multi-Robot Teams

  2017influential citation
• Visibility-Based Pursuit-Evasion in the Plane

  2016cites this paper
• Algorithms for Visibility-Based Monitoring with Robot Teams

  2016cites this paper
• A Geometric Approach for Multi-Robot Exploration in Orthogonal Polygons

  2016cites this paper
• Persistent Surveillance of Events with Unknown Rate Statistics

  2016cites this paper
• Exhaustive Exploration Strategies for NPCs

  2016cites this paper
• Techniques in Multi-Robot Area Coverage: A Comparative Survey

  2016cites this paper
• Algorithms for Monotone Paths with Visibility Properties

  2016cites this paper
• On The Watchman Route Problem and Its Related Problems

  2015cites this paper
• Exploration and observation planning for 3D indoor mapping

  2015cites this paper
• Persistent Monitoring of Events With Stochastic Arrivals at Multiple Stations

  2015cites this paper
• Barrier Resilience of Visibility Polygons

  2015cites this paper
• An Improved On-line Strategy for Exploring Unknown Polygons

  2015cites this paper
• Information-Theoretic Active Perception for Multi-Robot Teams

  2015cites this paper
• Visibility-based persistent monitoring with robot teams

  2015influential citation
• The multi-robot forest coverage for weighted terrain

  2015cites this paper
• A linear time algorithm for the -neighbour Travelling Salesman Problem on a Halin graph and extensions

  2015cites this paper
• Path optimization with limited sensing ability

  2015influential citation
• Mission Planning for Unmanned Aircraft with Genetic Algorithms

  2014cites this paper
• Scheduling And Resource Allocation In Wireless Sensor Networks

  2014cites this paper
• Connected wireless camera network deployment with visibility coverage

  2014cites this paper
• Information-Seeking Control Under Visibility-Based Uncertainty

  2014cites this paper
• Watchman routes for lines and line segments

  2014cites this paper
• The Visibility Freeze-Tag Problem

  2014influential citation
• Scheduling And Resource Allocation In Wireless Sensor Networks

  2014cites this paper
• A Survey of Computational Geometry

  2014cites this paper
• Correlated Orienteering Problem and its application to informative path planning for persistent monitoring tasks

  2014cites this paper