Angle-restricted tours in the plane

S.P. Fekete, G.J. Woeginger

    Research output: Contribution to journalArticlepeer-review

    36 Citations (Scopus)

    Abstract

    For a given set A (-p; +p] 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 algorithmic and combinatorial results on this problem. In particular, we show that any finite 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.
    Original languageEnglish
    Pages (from-to)195-218
    Number of pages24
    JournalComputational Geometry
    Volume8
    Issue number4
    DOIs
    Publication statusPublished - 1997

    Fingerprint

    Dive into the research topics of 'Angle-restricted tours in the plane'. Together they form a unique fingerprint.

    Cite this