# 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

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.