## Günter Rote:

# The *N*-line traveling salesman problem

*Networks* **22** (1992), 91–108, (Zbl 783.90118,
MR #92k:90045). doi:10.1002/net.3230220106
### Abstract

We consider the special case of the Euclidean Traveling Salesman
Problem where
the given points lie on a
small number (*N*) of
parallel lines.
Such problems arise for example in the fabrication of printed circuit
boards,
where the distance traveled by a laser which drills holes in certain
places of
the board should be minimized.
By a dynamic programming algorithm, we can solve
the *N*-line traveling salesman problem for *n* points in
time *n*^{N},
for fixed *N*, i. e.,
in polynomial time. This extends a result of Cutler (1980) for
3 lines.
The parallelity condition can be relaxed to point sets which
lie on *N* "almost parallel" line segments. We give a
characterization of the allowed segment configurations by a set of
forbidden subconfigurations.
### Erratum

The version that appears in *Networks* has an
incorrect version of the corollary in Section 6, which characterizes
the allowed segment configurations by forbidden subconfigurations:
one case is missing in Figure 3. This is corrected in the
technical report (see the links above), and in my
dissertation,
of which this paper is a part.

Last update: August 16, 2012.