Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-96-14

August 1996

Angle-Restricted Tours in the Plane

Sándor P. Fekete and Gerhard J. Woeginger


For a given set $A \subseteq (-\pi; +\pi]$ of angles, the problem "Angle-Restricted Tour" (ART) is to decide whether a set P of n points in the Euclidean plane allows a closed directed tour consisting of straight line segments, such that all angles between consecutive line segments are from the set A.

We present a variety of combinatorial and algorithmic results on this problem. In particular, we show that any infinite set of at least five points allows a "pseudoconvex" tour (i.e. a tour where all angles are nonnegative), and we derive a fast algorithm for constructing such a tour. Moreover, we give a complete classification (from the computational complexity point of view) for the special cases where the tour has to be part of the orthogonal grid.

Keywords. Angle-Restrictions, Travelling Salesman Problem, Hamiltonian Cycle, Convexity, Complexity, Geometry, NP-Complete.

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-96-14, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-171-955 7732.
Fax: +44(0)-171-955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html