The N-line traveling salesman problem
Networks 22 (1992), 91–108, (Zbl 783.90118,
MR #92k:90045). doi:10.1002/net.3230220106
We consider the special case of the Euclidean Traveling Salesman
the given points lie on a
small number (N) of
Such problems arise for example in the fabrication of printed circuit
where the distance traveled by a laser which drills holes in certain
the board should be minimized.
By a dynamic programming algorithm, we can solve
the N-line traveling salesman problem for n points in
for fixed N, i. e.,
in polynomial time. This extends a result of Cutler (1980) for
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
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
of which this paper is a part.
Last update: August 16, 2012.