Securing Pathways with Orthogonal Robots
Hamid Hoorfar Faraneh Fathi Sara Moshtaghi Largani Alireza Bagheri
The protection of pathways holds immense significance across various domains,
including urban planning, transportation, surveillance, and security. This
article introduces a groundbreaking approach to safeguarding pathways by
employing orthogonal robots. The study specifically addresses the challenge of
efficiently guarding orthogonal areas with the minimum number of orthogonal
robots. The primary focus is on orthogonal pathways, characterized by a
path-like dual graph of vertical decomposition. It is demonstrated that
determining the minimum number of orthogonal robots for pathways can be
achieved in linear time. However, it is essential to note that the general
problem of finding the minimum number of robots for simple polygons with
general visibility, even in the orthogonal case, is known to be NP-hard.
Emphasis is placed on the flexibility of placing robots anywhere within the
polygon, whether on the boundary or in the interior.