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
@inproceedings{icra2018_approximationalg,
title = {Approximation Algorithms for Tours of Orientation-Varying View Cones},
author = {Nikolaos Stefas and Patrick A. Plonski and Volkan Isler},
booktitle = {ICRA 2018},
year = {2018}
}