Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-96-14 August 1996

Abstract

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.

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