Approximation Algorithms for Tours of Orientation-Varying View Cones

Nikolaos Stefas, Patrick A. Plonski, Volkan Isler

Abstract

This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle α and height H when their apex points lie on a planar surface. This is a novel variant of the 3D Traveling Salesman Problem with intersecting Neighborhoods (TSPN) called Cone-TSPN. When the cones are allowed to tilt by an angle c we have the tilted Cone-TSPN problem, to which we present an algorithm that returns a solution with an approximation ratio of O (1+tan α/1-tan ϵ tan α (1 + log max(H)/min(H)). We demonstrate through simulations that our algorithm can be implemented in a practical way and by exploiting the structure of the cones we can achieve shorter tours. Finally, we present results from covering a reflective surface (lake area) that shows the importance of selecting different view angles under strong sunlight specularities.
BibTeX
@article{stefas2020approximation,
  author = {Nikolaos Stefas and Patrick A. Plonski and Volkan Isler},
  title = {{Approximation Algorithms for Tours of Orientation-Varying View Cones}},
  journal = {Int. J. Robotics Res.},
  year = {2020},
  doi = {10.1177/0278364919893455},
}

Loading related content...

Figure