Approximation Algorithms for Tours of Orientation-varying View Cones

Date of Submission: 
February 16, 2018
Report Number: 
18-005
Report PDF: 
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 ε we have the tilted Cone-TSPN problem, to which we present a polynomial time approximation algorithm. 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.