## 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 paper 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 PostScript and PDF file links above), and in my
dissertation,
of which this paper is a part.

Last update: August 16, 2012.