Optimal covering tours with turn costs.
We give the first algorithmic study of a class of covering tour problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a specified region (pocket), in order to minimize a cost that depends not only on the length of the tour but also on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing (postman) problems with turn penalties. We prove lower bounds (NP-completeness of minimum-turn milling) and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method.
Introduction
An important algorithmic problem in manufacturing is to
compute effective paths and tours for covering ("milling")
a given region ("pocket") with a cutting tool: Find a path
or tour along which to move a prescribed cutter in order
that the sweep of the cutter (exactly) covers the re-
gion, removing all of the material from the pocket, while
not "gouging" the material that lies outside of the pocket.
This covering tour problem and its variants arise not only
in NC machining applications but also in several other
applications, including automatic inspection, spray paint-
ing/coating operations, robotic exploration, arc routing,
and even mathematical origami. While we will often
speak of the problem as "milling" with a "cutter", many of
its important applications arise in various contexts outside
of machining.
Department of Applied Mathematics and Statistics, State University
of New York, Stony Brook, NY 11794-3600, festie, jsbmg
@ams.sunysb.edu.
y Department of Computer Science, State University of New York,
Stony Brook, NY 11794-4400, fbender, saurabhg@cs.sunysb
.edu.
z Department of Computer Science, University of Waterloo, Water-
loo, Ontario N2L 3G1, Canada, eddemaine@uwaterloo.ca.
x Fachbereich Mathematik, Technische Universitat Berlin, 10623
Berlin, Germany, fekete@math.tu-berlin.de.
The majority of research on these geometric covering
tour problems as well as on the underlying arc routing
problems in networks has focused on cost functions based
on the lengths of edges. However, in many actual routing
problems, this cost is dominated by the cost of switching
paths or direction at a junction. A drastic example is
given by fiber-optical networks, where the time to follow
an edge is negligible compared to the cost of changing
to a different frequency at a router. In the context of NC
machining, turns represent an important component of the
objective function, as the cutter may have to be slowed in
anticipation of a turn. The number of turns (or the "link
naturally as an objective function in
robotic exploration (minimum-link watchman tours) and
in various arc routing problems (snow plowing or street
sweeping with turn penalties).
In this paper, we address the problem of minimizing
the cost of turns in a covering tour. This important aspect
of the problem has been left unexplored so far in the
algorithmic community; the arc routing community has
examined only heuristics or exact algorithms that do not
have performance guarantees. We provide several new
results:
(1) We prove that the covering tour problem with turn
costs is NP-complete, even if the objective is purely
to minimize the number of turns, the pocket is orthogonal
(rectilinear), and the cutter must move axis-
parallel. The hardness of the problem is not apparent,
as our problem seemingly bears a close resemblance
to the polynomially-solvable Chinese postman prob-
lem; see the discussion below.
(2) We provide a variety of constant-factor approximation
algorithms that efficiently compute covering
tours that are nearly optimal with respect to turn costs
in various versions of the problem. While getting
some O(1)-approximation is not difficult for most
problems in this class, through a careful study of the
structure of the problem, we have developed tools
and techniques that enable significantly stronger approximation
results. One of our main results is a
3.75-approximation for minimum-turn axis-parallel
tours for a unit square cutter that covers an integral
orthogonal polygon (with holes). Another main
result gives a 4/3-approximation for minimum-turn
tours in a "thin" pocket, as arises in the arc routing
version of our problem.

Table

summarizes our various results.
Cycle Cover Tour Simultaneous Maximum
Milling problem APX APX Length APX Coverage
Restricted-direction
geometric 5d 5d
Orthogonal
2.5 3.75 4 4
Integral orthogonal 4 6 4 4
Orthogonal thin 1 4=3 4 4

Table

1: Approximation factors achieved by our algorithms. (See Section 2 for the definitions of , , , d.)
(3) We devise a polynomial-time approximation scheme
(PTAS) for the covering tour problem in which the
cost is given as a weighted combination of length
and number of turns; e.g., the Euclidean length plus a
constant C times the number of turns. For a polygon
with h holes, the running time is O(2 h  N O(C) ).
The PTAS involves an extension of the m-guillotine
method, which has previously been applied to obtain
PTAS's in problems involving only length.
Related Work. In the CAD community, there is a vast
literature on the subject of automatic tool path genera-
tion; we refer the reader to Held [21] for a survey and
for applications of computational geometry to the prob-
lem. The algorithmic study of the problem has focussed
on the problem of minimizing the length of a milling
tour: Arkin et al. [5, 6] show that the problem is NP-hard
in general. Constant-factor approximation algorithms
are given in [5, 6, 23], with the best current factor
being a 2.5-approximation for min-length milling (11/5-
approximation for orthogonal simple polygons). For the
closely related lawn mowing problem (also known as the
"traveling cameraman problem" [23]), in which the covering
tour is not constrained to stay within P , the best
current approximation factor is (3 (utilizing PTAS
results for TSP). Also closely related is the watchman
route problem with limited visibility (or "d-sweeper prob-
lem"), as studied by Ntafos [31], who provides a 4/3-
approximation, which is improved to a 6/5-approximation
by [6]. The problem is also closely related to the Hamiltonicity
problem in grid graphs; the recent results of [32]
suggest that in simple polygons, minimum-length milling
may in fact have a polynomial-time algorithm.
Covering tour problems are related to watchman
route problems in polygons, which have had considerable
study in terms of both exact algorithms (for the simple
polygon case) and approximation algorithms (in gen-
see [29] for a recent survey. Most relevant to our
problem is the prior work on minimum-link watchman
tours: see [2, 3, 8] for hardness and approximation re-
sults, and [14, 25] for combinatorial bounds. However, in
these problems the watchman is assumed to see arbitrarily
far, making them distinct from our tour cover problems.
Other algorithmic results on milling include a recent
study of multiple tool milling by Arya, Cheng, and
Mount [9], who give an approximation algorithm for
minimum-length tours that use different size cutters, and
a recent paper of Arkin et al. [7], who examine the problem
of minimizing the number of retractions for "zig-zag"
machining without "re-milling", showing that the problem
is NP-complete and giving an O(1)-approximation algorithm

Geometric tour problems with turn costs have been
studied by Aggarwal et al. [1], who prove NP-complete
the angular-metric TSP, in which one is to compute a
tour on a set of points in order to minimize the sum
of the direction changes at each vertex. Fekete [17]
and Fekete and Woeginger [18] have studied a variety of
angle-restricted tour (ART) problems.
In the operations research literature, there has been an
extensive literature on arc routing problems, which arise
in snow removal, street cleaning, road gritting, trash col-
lection, meter reading, mail delivery, etc.; see the surveys
of [10, 15, 16]. Arc routing with turn costs has
had considerable attention recently, as it enables a more
accurate modeling of the true routing costs in many sit-
uations. Most recently, Clossey et al. [13] present six
heuristic methods of attacking arc routing with turn penal-
ties, without resorting to the usual transformation to a TSP
problem; however, their results are purely based on experiments
and provide no provable performance guarantees.
The directed postman problem with turn penalties has
been studied recently by Benavent and Soler [11], who
prove the problem to be (strongly) NP-hard and provide
heuristics (without performance guarantees) and computational
results. (See also Soler's thesis [19] and [30] for
computational experience with worst-case exponential-time
exact methods.)
Our covering tour problem is related to the Chinese
postman problem, which is readily solved exactly in
polynomial time. However, the turn-weighted Chinese
postman problem is readily seen to be NP-complete:
Hamiltonian cycle in line graphs is NP-complete (contrary
to what is reported in [20]; see page 246, West [33]),
implying that TSP in line graphs is also NP-complete. The
Chinese postman problem on graph G with turn costs at
nodes (and zero costs on edges) is equivalent to TSP on
the corresponding line graph, L(G), where the cost of an
edge in L(G) is given by the corresponding turn cost in
G. Thus, the turn-weighted Chinese postman problem is
also NP-complete.
Summary of Results. As we show in Section 3, all of
the variants of our problem mentioned so far are NP-
thus, our main interest is in approximation al-
gorithms. It turns out that all of these problems have
essentially constant-factor approximations. Table 1 summarizes
our best approximation factors for each problem.
The term "coverage" indicates the number of times a point
is visited, which is of interest in several practical applica-
tions. This parameter also provides an upper bound on the
total length.
Preliminaries
Problem Definitions. The general geometric milling
problem is to find a closed curve (not necessarily sim-
ple) whose Minkowski sum with a given tool (cutter) is
precisely a given region (pocket), P . Subject to this con-
straint, we may wish to optimize a variety of objective
functions, such as the length of the tour, or the number of
turns in the tour. We call these problems minimum-length
and minimum-turn milling, respectively. While the latter
problem is the main focus of this paper, we are also interested
in bicriteria versions of the problem in which both
length and number of turns must be small, or some linear
combination of the two (see Section 5.8).
In addition to choices in the objective function, the
problem version depends on the constraints on the tour.
In the orthogonal milling problem, the region P is an
orthogonal polygonal domain (with holes) and the tool is
an (axis-parallel) unit-square cutter constrained to axis-parallel
motion, with links of the tour alternating between
horizontal and vertical. All turns are 90  ; a "U-turn" has
cost of 2.
Instead of dealing directly with a geometric milling
problem, we often find it helpful to consider a more
combinatorial problem, and then adapt the solution back
to the geometric problem. The integral orthogonal milling
problem is a specialization of the orthogonal milling
problem in which the region P has integral vertices. In
this case, an optimal tour can be assumed to have its
vertex coordinates of the form k
milling in an integral orthogonal polygon (with holes) is
equivalent to finding a tour of all the vertices ("pixels") of
a grid graph; see Figure 1.
A more general combinatorial model than integral
orthogonal milling is the discrete milling problem, in
which we discretize the set of possible links into a finite
collection of "channels" which are connected together at

Figure

1: An instance of the integral orthogonal milling
problem (left), and the grid graph model (right).
"vertices." More precisely, the channels have unit "width"
so that there is only one way to traverse them with the
given unit-size tool. At a vertex, the tour has a choice
of (1) turning onto another channel connected at that end
(costing one turn), (2) going straight if there is an incident
channel collinear with the source channel (costing no
turns), or (3) "U-turning" back onto the source edge
(costing two turns). Hence, this problem can be modeled
by a graph with certain pairs of incident edges marked as
"collinear," in such a way that the set of collinear pairs
at each vertex is a (not necessarily perfect) matching.
The discrete milling problem is to find a tour in such
a graph that visits every vertex. (The vertices represent
the "pixels" to be covered.) Integral orthogonal milling
is the special case of discrete milling in a grid graph.
Let  (resp., ) denote the average (resp., maximum)
degree of a vertex and let  denote the average number
of distinct "directions" coming together at a vertex, that
is, the average over each vertex of the cardinality of the
matching plus the number of unmatched edges at that
vertex.
The thin milling problem is to find a tour in such a
graph that traverses every edge (and visits every vertex).
Thus, the minimum-length version of thin milling is
exactly the Chinese postman problem. As we have already
noted, the minimum-turn version is NP-complete. The
orthogonal thin milling problem is the special case in
which the graph comes from an instance of orthogonal
milling.
A generalization of orthogonal milling is the geometric
milling problem with a constant number d of allowed
directions, which we call restricted-direction geometric
milling. In particular, the region P can only have edges
with the d allowed directions. This problem is not a sub-problem
of discrete milling, since it does not decompose
into a collection of nonoverlapping "vertices;" however, it
turns out that the same results apply.
Other Issues. It should be stressed that using turn cost
instead of (or in addition to) edge length changes several
characteristics of distances. One fundamental problem
is illustrated by the example in Figure 2: the triangle
inequality does not have to hold when using turn cost.
This implies that many classical algorithmic approaches
for graphs with nonnegative edge weights (such as using
optimal 2-factors or the Christofides method for the TSP)
cannot be applied without developing additional tools.
a
c

Figure

2: The triangle inequality may not hold when using
turn cost as distance measure: d(a; c)
In fact, in the presence of turn costs we distinguish
between the terms 2-factor and cycle cover. While the
terms are interchangeable when referring to the set of
edges that they constitute, we make a distinction between
their respective costs: a "2-factor" has a cost consisting of
the sum of edge costs, while the cost of a "cycle cover"
includes also the turn costs at vertices.
It is often useful in designing approximation algorithms
for optimal tours to begin with the problem of
computing an optimal cycle cover, minimizing the total
number of turns in a set of cycles that covers P . Specif-
ically, we can decompose the problem of finding an optimal
tour into two tasks: finding an optimal
cycle cover, and merging the components. Of course,
these two processes may influence each other: there may
be several optimal cycle covers, some of which are easier
to merge than others. (In particular, we say that a cycle
cover is connected, if the graph induced by the set
of cycles and their intersections is connected.) As we
will show, even the problem of optimally merging a connected
cycle cover is NP-complete. This is in contrast to
minimum-length milling, where an optimal connected cycle
cover can trivially be converted into an optimal tour
that has the same cost.
Another important issue is the encoding of the input
and output. In integral orthogonal milling, one might
think that it is most natural to encode the grid graph,
since the tour will be embedded on this graph and will,
in general, have complexity proportional to the number of
pixels. But the input to any geometric milling problem
has a natural encoding by specifying the vertices of the
polygon P . In particular, long edges are encoded in
binary (or with one real number, depending on the model)
instead of unary. It is possible to get a running time
depending only on this size, but of course we need to
allow for the output to be encoded implicitly. That is, we
cannot explicitly encode each vertex of the tour, because
there are too many (it can be arbitrarily large even for a
succinctly encodable rectangle). Instead, we encode an
abstract description of the tour that is easily decoded.
Algorithms whose running time is polynomial in
the explicit encoding size (pixel count) are pseudo-poly-
nomial. Algorithms whose running time is polynomial
in the implicit encoding size are polynomial. For our
purposes it will not matter whether lengths are encoded
with a single real number or in binary.
Finally, we mention that many of our results carry
over from the tour (or cycle) version to the path version,
in which the cutter need not return to its original position.
We omit discussion here of the changes necessary to
compute optimal paths. We also omit in this abstract
discussions of how our results apply also to the case of
lawn mowing, in which the sweep of the cutter is allowing
to go outside P during its motion.
With so many problems of interest, we specify in
every lemma, theorem, and corollary to which class of
problems it applies. The default subproblem is to find a
tour; if this is not the case (e.g., it is to find a cycle cover),
we state it explicitly.
3 NP-Completeness
Arkin et al. [6] have proved that the problem of optimizing
the length of a milling is NP-hard. This implies that
it is NP-hard to find a tour of minimum total length that
visits all vertices. If, on the other hand, we are given a
connected cycle cover of a graph that has minimum total
length, then it is trivial to convert it into a tour of the same
length by merging the cycles into one tour.
In this section we show that if the quality of a tour
is measured by counting turns, then even this last step of
turning an optimal connected cycle cover into an optimal
tour is NP-complete. This implies NP-hardness of finding
a milling tour that optimizes the number of turns for a
polygon with holes.
THEOREM 3.1. Minimum-turn milling is NP-complete,
even when we are restricted to the orthogonal thin case,
and assume that we know an optimal (minimum-turn)
connected cycle cover.
See the full version [4] of this paper for proofs of
this and most other theorems and lemmas. Because
orthogonal thin milling is a special case of thin milling
as well as orthogonal milling, and it is easy to convert
an instance of thin orthogonal milling into an instance of
integral orthogonal milling, we have
COROLLARY 3.1. Discrete milling, restricted-direction
geometric milling, orthogonal milling, and integral orthogonal
milling are NP-complete.
Approximation Tools
There are three main tools that we use to develop approximation
algorithms: computing optimal cycle covers for
milling the "boundary" of P (Section 4.1), converting cycle
covers into tours (Section 4.2), and utilizing optimal
(or nearly-optimal) "strip covers" (Section 4.3).
4.1 Boundary Cycle Covers
We consider first the problem of finding a minimum-turn
cycle cover for covering a certain subset, P , of P that is
along its boundary. Specifically, in orthogonal milling
we define the boundary links to be orthogonal offsets,
towards the interior of P , by 0:5 of each boundary edge.
(In the nonorthogonal case, the notion of boundary link
can be generalized; we defer the details to the full paper.)
The region P is defined, then, to be the Minkowski sum
of the boundary links and the tool, and we say that a cycle
cover or tour mills the boundary if it covers P . (P is
the union of pixels having at least one edge against the
boundary of P .) We exploit the property that a cycle
cover that mills the boundary (or a cycle cover that mills
the entire region) can be assumed to include the boundary
links in their entirety (without turns):
LEMMA 4.1. Any cycle cover that mills the boundary can
be converted into one that includes each boundary link as
a portion of a link, without changing the number of turns.
(a) (b)

Figure

3: By performing local modifications, an optimal
cycle cover can be assumed to cover each piece of the
boundary in one connected link.
This property allows us to apply methods similar to
those used in solving the Chinese postman problem: we
know portions of links that must be in the cycle cover, and
furthermore these links mill the boundary. What remains
is to connect these links into cycles, while minimizing the
number of additional turns.
We can compute the "turn distance" (which is one
less than the link distance) between an endpoint of one
boundary link and an endpoint of another boundary link.
The crucial knowledge that we are using is the orientation
of the boundary links, so, for example, we correctly
compute that the turn distance is zero when two boundary
links are collinear. Now we can find a minimum-weight
perfect matching in the complete graph on boundary-
link endpoints, with each edge weighted according to the
corresponding turn distance. This connects the boundary
links optimally into a set of cycles. This proves
THEOREM 4.1. A min-turn cycle cover of the boundary
of a region can be computed in polynomial time.
Remark. Note that the definition of the "boundary"
region P used here does not include all pixels that touch
the boundary of P ; in particular, it omits the "reflex
pixels" that share a corner, but no edge, with the boundary
of P . It seems difficult to require that the cycle cover
mill reflex pixels, since Lemma 4.1 does not extend to
this case, and an optimal cycle cover of the boundary
(as defined above) may have fewer turns than an optimal
cycle cover that mills the boundary P plus the reflex
pixels; see Figure 4.

Figure

4: Optimally covering pixels that have an edge
against the boundary can leave reflex pixels uncovered.
4.2 Merging Cycles
It is often easier to find a minimum-turn cycle cover
(or constant-factor approximation thereof) than to find
a minimum-turn tour. Here, we show that an exact
or approximate minimum-turn cycle cover implies an
approximation for minimum-turn tours.
THEOREM 4.2. A cycle cover with t turns can be converted
into a tour with at most t + 2c turns, where c is the
number of cycles.
COROLLARY 4.1. A cycle cover of a connected rectilinear
polygon with t turns can be converted into a single
milling tour with at most 3
turns.
Proof: Follows immediately from Theorem 4.2 and the
fact that each cycle has at least four turns. 2
COROLLARY 4.2. If we could find an optimal cycle cover
in polynomial time, we would have a 3-approximation
algorithm for the number of turns.
Unfortunately, general merging is difficult (as illustrated
by the NP-hardness proof), so we cannot hope to
improve these general merging results by more than a constant
factor.
4.3 Strip and Star Covers
A key tool for approximation algorithms is a covering of
the region by a collection of "strips." In general, a strip
is a maximal link whose Minkowski sum with the tool
is contained in the region. A strip cover is a collection
of strips whose Minkowski sums with the tool cover the
region. A minimum strip cover is a strip cover with
the fewest strips.
LEMMA 4.2. The size of a minimum strip cover is a
lower bound on the number of turns in a cycle cover (or
tour) of the region.
In the discrete milling problem, a related notion is a
"queen placement." A queen is just a vertex, which can
attack every vertex to which it is connected via a single
link. A queen placement is a collection of queens no two
of which can attack each other.
LEMMA 4.3. The size of a maximum queen placement is
a lower bound on the number of turns in a cycle cover (or
tour) for discrete milling.
In the integral orthogonal milling problem, the notions
of strip cover and queen placement are dual, and efficient
to compute:
LEMMA 4.4. For integral orthogonal milling, a minimum
strip cover and a maximum queen (rook) placement
have equal size, and furthermore can be computed in time
O(n 2:5 ).
For general discrete milling, it is possible to approximate
an optimal strip cover as follows. Greedily place
queens until you cannot place anymore, in other words,
until there is no unattackable vertex. This means that every
vertex is attackable by some queen, so by replacing
each queen with all possible strips through that vertex, we
obtain a strip cover of size  times the number of queens.
(We call this type of strip cover a star cover.) But each
strip in a minimum strip cover can only cover a single
queen, so this is a -approximation to the minimum strip
cover. We have thus proved
LEMMA 4.5. In discrete milling, the number of stars in
a greedy star cover is a lower bound on the number of
strips, and hence serves as an -approximation algorithm
for minimum strip covers.
LEMMA 4.6. A greedy star cover can be found in linear
time.
5 Approximation Algorithms
5.1 Discrete Milling
Our most general approximation algorithm for the discrete
milling problem has the additional feature of running
in linear time. First we take a star cover according
to Lemma 4.5 which approximates an optimal strip cover
within a factor of . Then we tour the stars using an efficient
method described below. Finally we merge these
tours using Theorem 4.2.
THEOREM 5.1. For min-turn cycle covers in discrete
milling, there is a linear-time (
Furthermore, the maximum coverage of a vertex (i.e., the
maximum number of times a vertex is swept) is , and the
cycle cover is an -approximation on length.
COROLLARY 5.1. For min-turn discrete milling, there is
a linear-time
the maximum coverage of a vertex is , and the tour is an
-approximation on length.
Note that, in particular, these algorithms give a 6-
approximation on length if the discrete milling problem
comes from a planar graph, since the average degree of a
planar graph is bounded by 6.
COROLLARY 5.2. For minimum-turn integral orthogonal
milling, there is a linear-time 12-approximation that
covers each pixel at most 4 times and hence is also a 4-
approximation on length.
Proof: In this case,
5.2 Restricted-Direction Geometric Milling
As we already mentioned above, restricted-direction geometric
milling is not a special case of discrete milling, but
the same method and result applies:
THEOREM 5.2. In restricted-direction geometric milling,
there is a 5d-approximation on minimum-turn cycle covers
that is linear in the number N of pixels, and a (5d+2)-
approximation on minimum-turn tours of same complex-
ity. In both cases, the maximum coverage of a point is at
most 2d, so the algorithms are also 2d-approximations on
length.
Proof: Lemma 4.6 still holds, and each strip in a star (as
described in the previous section) will be a full strip. The
claim follows. 2
Note that this approximation algorithm applies to geometric
milling problems in arbitrary dimensions provided
that the number of directions is bounded, e.g., or-
thohedral milling.
As mentioned in the preliminaries, just the pixel
count N may not be a satisfactory measure for the complexity
of an algorithm, as the original region may be encoded
more efficiently by its boundary, and a tour may be
encoded by structuring it into a small number of pieces
that have a short description. It is possible to use the
above ideas for approximation algorithms in this extended
framework. For simplicity, we describe how this can be
done for the integral orthogonal case, where the set of pixels
is bounded by n boundary edges.
THEOREM 5.3. There is a 10-approximation of (strongly
polynomial) complexity O(n log n) on minimum-turn cycle
cover for a region of pixels bounded by n integral axis-parallel
segments, and a 12-approximation on minimum-
turn tours of same complexity. In both cases, the maximum
coverage of a point is at most 4, so the algorithms
are also 4-approximations on length.
For the special case where the boundary is connected
(i.e., the region does not have any holes), the complexities
drop to O(n).
5.3 Integral Orthogonal
We have already shown a 12-approximation for min-turn
integral orthogonal milling, using a star cover, with a
running time of O(N) or O(n log n). If we are willing to
invest more time for computation, we can find an optimal
rook cover (instead of a greedy one). As discussed in the
proof of Lemma 4.4, this yields an optimal strip cover.
This can be used to get a 6-approximation, with a running
time of O(n 1:5 ).
THEOREM 5.4. There is an O(n 2:5 )-time algorithm that
computes a milling tour with number of turns within 6
times the optimal, and with length within 4 times the
optimal.
By more sophisticated merging procedures, it may be
possible to reduce this approximation factor to something
between 4 and 6. However, our best approximation
algorithm uses a different strategy.
THEOREM 5.5. There is an O(n 2:5 ) 2:5-approximation
algorithm for minimum-turn cycle covers, and hence a
polynomial-time 3:75-approximation for minimum-turn
tours, for integral orthogonal milling.
Proof: As described in Lemma 4.4, find an optimal strip
cover S. Let s be its cardinality, then OPT s.
Now consider the end vertices of the strip cover. By
construction, they are part of the boundary. Any end point
of a strip is either crossed orthogonally, or the tour turns
at the boundary segment. In any case, a tour must have
a link that crosses an end vertex orthogonally to the strip.
(Note that this link has zero length in case of a u-turn.)
Next consider the following distance function between
end points of strips: For any pair of end points u
and v (possibly of different strips s u and s v ), let w(u; v)
be the smallest number of links from u to v when leaving
u in a direction orthogonal to s u , and arriving at v in
a direction orthogonal to s v . By a standard argument, an
optimal matching M satisfies w(M)  OPT=2.
By construction, the edges of M and the strips of S
induce a 2-factor of the end points. Since any matching
edges leaves a strip orthogonally, we get at most 2 additional
turns at each strip for turning each 2-factor into a
cycle. The total number of turns is 2s+w(M)  2:5OPT.
Since the strips cover the whole region, we get a feasible
cycle cover.
Finally, we can use Corollary 4.1 to turn the cycle
cover into a tour. By the corollary, this tour does not have
more than 3.75OPT turns. 2
A simple class of examples in [4] shows that the
cycle cover algorithm may use 2OPT turns, and the tour
algorithm may use 3OPT turns, assuming that no special
algorithms are used for matching and merging. Moreover,
the same example shows that this 3:75-approximation
algorithm does not give an immediate length bound on the
resulting tour. However, we can use a local modification
argument to show the following:
THEOREM 5.6. For any given feasible tour of an integral
orthogonal region, there is a feasible tour of equal length
that covers each pixel at most four times. This implies a
performance ratio of 4 on the total length.
5.4 Nonintegral Orthogonal Polygons
Nonintegral orthogonal polygons present a difficulty in
that no polynomial-time algorithm is known to compute
a minimum strip cover for such polygons. Fortunately,
however, we can use the boundary tours from Section 4.1
to get a better approximation algorithm than the 12 from
Corollary 5.2.
THEOREM 5.7. In nonintegral orthogonal milling, there
is a polynomial-time 6:25-approximation for minimum-
turn cycle covers and 6-approximation for minimum-turn
tours. The running time is O(n 2:5 ).
Milling Thin Pockets
In this section we consider the special case of milling thin
pockets. Intuitively, a pocket is thin if it is composed of a
network of width-1 corridors, where each pixel is adjacent
to some part of the boundary of the region. A width-1
polygon is defined more formally as follows:
DEFINITION 1. An orthogonal polygon has width-1 if
no axis-aligned 2x2 square fits into the feasible region.
Equivalently, a width-1 polygon is such that each pixel
has all four of its corners on the boundary of the polygon.
A width-1 pocket has a natural graph representation,
described as follows. We associate vertices with some of
the squares that comprise the pocket. Specifically, a vertex
is associated with each square that is adjacent to more
than two squares or only one square. Squares that have
exactly two neighbors are converted into edges as follows:
Vertices u and v are connected by an edge iff there is
path in the pocket from u to v for which all other pixels
visited have two neighbors. The weight of edge (u; v) is
the number of turns in this path from u to v. In other
words: Pixels with one, three, or four neighbors can be
considered vertices of degree one, three, or four. Chains
(possibly of length zero) of adjacent pixels of degree two
can be considered edges between other vertices, if there
are any. (Clearly, the problem is trivial if there are no
pixels of degree three or higher; moreover, it is not hard
to see that all pixels adjacent to a pixel of degree four can
have at most degree two, and each pixel of degree three
must have at least one neighbor of degree not exceeding
two.) In the following, we will refer to this interpretation
whenever we speak of the "induced graph" of a region.
This interpretation illustrates that the problem is
closely related to the Chinese Postman Problem (CPP),
where the objective is to find a cheapest round trip in a
graph with nonnegative edge weights, such that all edges
are traversed. It is well-known that the CPP can be solved
optimally in polynomial time by finding a minimum-cost
matching of the odd-degree vertices in the graph. For thin
milling, however, this reduction does not work: While it
is possible to find a minimum-cost matching of the odd-
degree vertices, the cost of traversing the resulting Eulerian
graph is more than just the sum of edge weights, since
we may have to add a cost for turning at the vertices where
the matching is merged with the other edges in the graph.
As we noted in the introduction, this implies that triangle
inequality does not hold in general, and standard combinatorial
algorithms based on edge weights only may fail
to achieve a reasonable guaranteed performance. The difficulty
of having turn costs at vertices is also illustrated by
the proof in Section 3: Even in an Eulerian graph, where
all pixels have degree 2 or 4, it is NP-complete to find a
minimum cost roundtrip.
In this section we describe how refined combinatorial
arguments can achieve efficient constant-factor approxi-
mations. Without loss of generality, we assume that there
are no pixels of degree one: They force a doubled path to
and from them, which can be merged with any tour of the
remaining region at no extra cost.
We already know from Theorem 4.1 that a minimum-
turn cycle cover of a thin region can be found in polynomial
time, because any cycle cover of the boundary can
be turned into a cycle cover of the entire thin region. By
also applying Theorem 4.2, we immediately obtain
COROLLARY 5.3. In thin milling, there is a polynomial-time
algorithm for computing a min-turn cycle cover, and
a polynomial-time 1.5-approximation for min-turn tours.
More interesting is that we can do much better than
general merging in the case of thin milling. The idea is
to decompose the induced graph into a number of cheap
cycles, and a number of paths.
5.6 Milling Thin Eulerian Pockets We first solve the
special case of milling Eulerian pockets, that is, pocket
that can be milled without retractions, so that each edge
in the corresponding graph is traversed by the cutting tool
exactly once. In an Eulerian pocket, all nodes have either
two or four neighbors, and so all vertices in the graph have
exactly four neighbors.
Although one might expect that the optimal milling
is one of the possible Eulerian tours of the graph, in fact,
this is not always true; see the full version [4] for a class
of examples with this property.
However, we can achieve the following approximation

THEOREM 5.8. There is a linear-time algorithm that
finds a tour of length at most 6=5OPT.
5.7 Milling Arbitrary Thin Pockets Now we consider
the case of general width-1 pockets, where vertices
may have degree one or three. (As above, we can continue
to disregard vertices of degree one.) For any odd-degree
vertex, and any feasible solution, some edges must be traversed
multiple times.
As motivation for this more general milling problem,
recall the solution to the Chinese Postman Problem. Find
a minimum-cost perfect matching in the complete graph
on the odd-degree vertices, where the weight of an edge is
the length of the shortest path between the two endpoints.
Double the edges along the paths chosen in the perfect
matching. (No edge will be doubled more than once by a
simple local-modification argument.) Now take an Euler
tour of this graph with doubled edges.
This idea can be applied to our turn-minimization
problem. Consider a degree three vertex, and for naming
convenience give it a canonical orientation of the letter
"T". We will need to visit and leave this vertex twice
in order to cover it; that is, two paths through the T are
required in order to mill it.
There are several possibilities, which depend on
which edge of the T is covered twice by the cutting tool.
(See

Figure

5.)
(a) (b) (c)

Figure

5: Ways of covering a degree three node, which we
call a "T".
(a) If one of the top edges is milled twice then there is
only a single turn at the T. Said more concisely, if
the stalk is milled i times then exactly i turns are
required to mill the T.
If the stalk of the T is milled twice then there are two
ways to mill the T:
(b) One path mills the top of the T, and the other enters
on the stalk makes a "U" turn and exits the T on the
same path that it entered.
(c) Both paths mill the stalk and one of the top edges of
the T.
In both cases, if the stalk of the T is milled twice, then
there are 2 turns at the T.
We find a minimum weight cycle cover by having
as few turns at vertices as possible. Specifically, the
tool starts traveling along any edge and proceeds straight
through each intersection without making any additional
turns. Whenever the tool would retraverse an edge, a cycle
is obtained, and the tool continues the process setting out
from another edge. Whenever the tool enters a T from
the stalk it stops. Thus, we obtain a disjoint collection of
cycles and paths.
Now we connect the odd degree vertices together as
in a Chinese postman problem. Thus, we define the length
of a path between two degree three vertices to be the
number of turns along the path, plus a penalty of 1 for
each time the path ends at the bottom leg of a T.
Next, we find a minimum weight perfect matching on
paths that connect odd degree vertices. When we combine
the paths of the matching with the disjoint collection of
paths and cycles we obtain an Eulerian graph. We connect
the ends of the paths with the ends of the matching paths
to form cycles.
CLAIM 1. The above strategy yields a minimum cost
cycle cover.
Observe that this cycle cover is different from the cycle
cover in the Eulerian case because the cycles are not
disjoint sets of edges of the graphs. Some edges may
appear multiple times.
We now describe a 4=3-approximation algorithm for
connecting the cycles together.
1. Find an optimal cycle cover as described in Claim 1.
2. Repeat until there is only one cycle in the cycle
cover:
If there are any two cycles that can be merged
without any extra cost, perform the merge.
Find a vertex at which two cycles cross each
other.
Modify the vertex to incorporate at most two
additional turns, thereby connecting the two
cycles.
THEOREM 5.9. The algorithm described above finds a
tour of length at most 4=3OPT.
An example (shown in the full version [4] of this
paper) proves that the estimate for the performance ratio
is tight.
5.8 PTAS
Here we outline a PTAS for the problem of minimizing
a weighted average of the two cost criteria: length and
number of turns. Our technique is based on using the theory
of m-guillotine subdivisions [28], properly extended
to handle turn costs. We prove the following result:
THEOREM 5.10. For any fixed " > 0, there is a (1
")-approximation algorithm with running time O(2 h
that computes a milling tour for an integral
orthogonal polygon P with h holes, where the cost of the
tour is its length plus C times the number of (90-degree)
turns, and N is the number of pixels in P .
Proof: (sketch) Let T  be a minimum-cost tour. Following
the notation of [28], we first use the main structure
theorem to show that there exists an m-guillotine subdivi-
sion, obtained from T  , with length at most (1
times the length of T  . (Note that part of TG may lie
outside the pocket P , since we added m-spans to make
it m-guillotine.) We then convert TG into a new graph,
G , which has the added properties
(since we keep only those portions of the m-span that lie
inside P ), (2) the number of edges of T  incident on each
component of the m-span is even (since T  is a tour), and
(3) the total cost of T 0
G is at most (1
times the
cost of T  . We then use dynamic programming to obtain
a min-cost (modified) m-guillotine subdivision, T
G ,
which has certain specified properties, including connect-
edness, coverage, "bridge-doubling", and an even number
of edges incident on each connected component of each
m-span (this is the source of the 2 h term in the running
time, as we need to be able to require a given parity at
each sub-bridge, in order to have a connected Eulerian
graph in the end, from which we can extract a tour). The
techniques of [27] can be applied to reduce the exponent
on N to a term independent of ". 2
We expect to be able to use the same methods to
obtain a PTAS that is polynomial in n (versus N ), with
a careful consideration of implicit encodings of tours. We
have not yet been able to give a PTAS for minimizing only
the number of turns in a covering tour; this remains an
intriguing open problem.
6 Conclusion
Many open problems remain:
1. Can we find a minimum-turn cycle cover in polynomial
time? This would immediately lead to a 1.5-
approximation for the orthogonal case, and a (1+ 2
approximation for the general case.
Note that finding a minimum-cost cycle cover for a
planar set of points was shown to be NP-complete by
Aggarwal et al. [1].
2. Is there a polynomial-time algorithm for exactly
computing a minimum-turn covering tour for simple
orthogonal polygons?
The related problem for cost corresponding to distances
is still open, but there is some evidence that it
is indeed polynomial.
3. Is the analysis of the 3.75-approximation algorithm
There may be some redundancy in the combination
of all the estimates; however, our example shows that
even one of the basic simplifications (considering
only maximal strips with endpoints on the boundary)
may lead to a factor 2 or 3, depending on how the
merging is done.
4. What is the complexity of computing a minimum
strip cover in nonintegral orthogonal polygons?
5. What is the complexity of computing minimum strip
covers in nonorthogonal polygons?
6. Is there a strip cover approximation algorithm for d
directions whose performance is independent of d?
7. Can one obtain approximation algorithms for unrestricted
directions in an arbitrary polygonal domain?

Acknowledgments

We thank Regina Estkowski for helpful discussions.
This research is partially supported by NSF grant CCR-
9732221, and by several grants from Bridgeport Ma-
chines, Hughes Research Labs, ISX Corporation, Sandia
National Labs, Seagull Technology, and Sun Microsystems




--R

The angular-metric traveling salesman problem
Minimal link visibility paths inside a simple polygon.
Finding an approximate minimum-link visibility path inside a simple polygon
Optimal covering tours with turn costs.
The lawnmower problem.
Approximation algorithms for lawn mowing and milling.
Optimization problems related to zigzag pocket machining.

Approximation algorithms for multiple-tool milling
Arc routing methods and applications.
The directed rural postman problem with turn penalties.
Triangulating a simple polygon in linear time.
Solving arc routing problems with turn penalties.
Improved lower bounds for the link length of rectilinear spanning paths in grids.
Arc routing problems
Arc routing problems
Geometry and the Travelling Salesman Problem.


Computers and In- tractability: A Guide to the Theory of NP-Completeness
On the Computational Geometry of Pocket Machining
Hamilton paths in grid graphs.
The traveling cameraman problem
Computational complexity and the traveling salesman problem.
Link length of rectilinear Hamiltonian tours on grids.
Combinatorial Optimization: Networks and Matroids.
Guillotine subdivisions approximate polygonal subdivisions: Part III - Faster polynomial-time approximation schemes for geometric network optimiza- tion
Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP
Geometric shortest paths and network optimization.

Watchman routes under limited visibility.
Hamiltonian cycles in solid grid graphs.
An Introduction to Graph Theory.
--TR
On the computational geometry of pocket machining
Triangulating a simple polygon in linear time
Watchman routes under limited visibility
Minimal link visibility paths inside a simple polygon
Finding an approximate minimum-link visibility path inside a simple polygon
Angle-restricted tours in the plane
Approximation algorithms for multiple-tool miling
Improved lower bounds for the link length of rectilinear spanning paths in grids
Guillotine Subdivisions Approximate Polygonal Subdivisions
The angular-metric traveling salesman problem
Approximation algorithms for lawn mowing and milling
Computers and Intractability
The Traveling Cameraman Problem, with Applications to Automatic Optical Inspection
The Directed Rural Postman Problem with Turn Penalties
Hamiltonian Cycles in Solid Grid Graphs

--CTR
D. Demaine , Sndor P. Fekete , Shmuel Gal, Online searching with turn cost, Theoretical Computer Science, v.361 n.2, p.342-355, 1 September 2006
Sndor P. Fekete , Marco E. Lbbecke , Henk Meijer, Minimizing the stabbing number of matchings, trees, and triangulations, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
lawn mowing;approximation algorithms;manufacturing;traveling salesman problem TSP;NP-completeness;NC machining;turn costs;milling;covering;m-guillotine subdivisions;polynomial-time approximation scheme PTAS