Polygon decomposition for efficient construction of Minkowski sums.
Several algorithms for computing the Minkowski sum of two polygons in the plane begin by decomposing each polygon into convex subpolygons. We examine different methods for decomposing polygons by their suitability for efficient construction of Minkowski sums. We study and experiment with various well-known decompositions as well as with several new decomposition schemes. We report on our experiments with various decompositions and different input polygons. Among our findings are that in general: (i) triangulations are too costly, (ii) what constitutes a good decomposition for one of the input polygons depends on the other input polygon - consequently, we develop a procedure for simultaneously decomposing the two polygons such that a "mixed" objective function is minimized, (iii) there are optimal decomposition algorithms that significantly expedite the Minkowski-sum computation, but the decomposition itself is expensive to compute - in such cases simple heuristics that approximate the optimal decomposition perform very well.
Introduction
Given two sets P and Q in IR 2 , their Minkowski sum (or vector sum), denoted by P Q,
is the set fp Qg. Minkowski sums are used in a wide range of applications,
including robot motion planning [26], assembly planning [16], computer-aided design and
P.A. is supported by Army Research O-ce MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by
NSF grants EIA{9870724, EIA{997287, and CCR{9732787 and by a grant from the U.S.-Israeli Binational
Science Foundation. D.H. and E.F. have been supported in part by ESPRIT IV LTR Projects No. 21957
(CGAL) and No. 28155 (GALIA), and by a Franco-Israeli research grant (monitored by AFIRST/France
and The Israeli Ministry of Science). D.H. has also been supported by a grant from the U.S.-Israeli Binational
Science Foundation, by The Israel Science Foundation founded by the Israel Academy of Sciences
and Humanities (Center for Geometric Computing and its Applications), and by the Hermann Minkowski {
Minerva Center for Geometry at Tel Aviv University.
A preliminary version of this paper appeared in the proceedings of the 8th European Symposium on Algorithms
| ESA 2000.
y Department of Computer Science, Duke University, Durham, NC 27708-0129. pankaj@cs.duke.edu.
z Department of Computer Science, Tel Aviv University, Tel-Aviv 69978, Israel. flato@post.tau.ac.il.
x Department of Computer Science, Tel Aviv University, Tel-Aviv 69978, Israel. danha@post.tau.ac.il.

Figure

1: Robot and obstacles: a reference point is rigidly attached to the robot on the left-hand
side. The conguration space obstacles and a free translational path for the robot on the
right-hand side.
manufacturing (CAD/CAM) [9], and marker making (cutting parts from stock material)
Consider for example an obstacle P and a robot Q that moves by translation. We can
choose a reference point r rigidly attached to Q and suppose that Q is placed such that the
reference point coincides with the origin. If we let Q 0 denote a copy of Q rotated by 180 - ,
then P  Q 0 is the locus of placements of the point r where P \ Q 6= ;. In the study of
motion planning this sum is called a conguration space obstacle because Q collides with P
when translated along a path  exactly when the point r, moved along , intersects P Q 0 .

Figure

1.
Motivated by these applications, there has been much work on obtaining sharp bounds
on the size of the Minkowski sum of two sets in two and three dimensions, and on developing
fast algorithms for computing Minkowski sums. It is well known that if P is a polygonal set
with m vertices and Q is another polygonal set with n vertices, then P Q is a portion of
the arrangement of O(mn) segments, where each segment is the Minkowski sum of a vertex
of P and an edge of Q, or vice-versa. Therefore the size of P  Q is O(m 2 n 2 ) and it can
be computed within that time; this bound is tight in the worst case [20] (see Figure 2). If
both P and Q are convex, then P Q is a convex polygon with at most m+n vertices, and
it can be computed in O(m only P is convex, then a result of Kedem et
al. [21] implies that P  Q has (mn) vertices (see Figure 3). Such a Minkowski sum can
be computed in O(mn log(mn)) time [28].
Minkowski sums of curved regions have also been studied, (e.g., [4] [19] [27]), as well as
Minkowski sums in three-dimensions (e.g., see a survey paper [2]). Here however we focus
on sums of planar polygonal regions.
We devised and implemented three algorithms for computing the Minkowski sum of
two polygonal sets based on the CGAL software library [1, 11]. Our main goal was to
produce a robust and exact implementation. This goal was achieved by employing the
CGAL planar maps [14] and arrangements [17] packages while using exact number types.
We use rational numbers and ltered geometric predicates from LEDA | the Library of

Figure

2: Fork input: P and Q are polygons with m and n vertices respectively each having
horizontal and vertical teeth. The complexity of P Q is (m

Figure

3: Comb input: P is a convex polygon with m vertices and Q is a comb-like polygon
with n vertices. The complexity of P Q is (mn).
E-cient Data-structures and Algorithms [29, 30].
We are currently using our software to solve translational motion planning problems in
the plane. We are able to compute collision-free paths even in environments cluttered with
obstacles, where the robot could only reach a destination placement by moving through
tight passages, practically moving in contact with the obstacle boundaries. See Figure 4
for an example. This is in contrast with most existing motion planning software for which
tight or narrow passages constitute a signicant hurdle. More applications of our package
are described in [12].
The robustness and exactness of our implementation come at a cost: they slow down the

Figure

4: Tight passage: the desired target placement for the small polygon is inside the inner
room dened by the larger polygon (left-hand side). In the conguration space (right-hand side)
the only possible path to achieve this target passes through the line segment emanating into
the hole in the sum.
running time of the algorithms in comparison with a more standard implementation that
uses
oating point arithmetic. This makes it especially necessary to expedite the algorithms
in other ways. All our algorithms begin with decomposing the input polygons into convex
subpolygons. We discovered that not only the number of subpolygons in the decomposition
of the input polygons but also their shapes had dramatic eect on the running time of the
Minkowski-sum algorithms; see Figure 5 for an example.
In the theoretical study of Minkowski-sum computation (e.g., [21]), the choice of decomposition
is often irrelevant (as long as we decompose the polygons into convex subpolygons)
because it does not aect the worst-case asymptotic running time of the algorithms. In
practice however, dierent decompositions can induce a large dierence in running time
of the Minkowski-sum algorithms. The decomposition can aect the running time of algorithms
for computing Minkowski sums in several ways: some of them are global to all
algorithms that decompose the input polygons into convex polygons, while some others are
specic to certain algorithms or even to specic implementations. The heart of this paper
is an examination of these various factors and a report on our ndings.
Polygon decomposition has been extensively studied in computational geometry; it is
beyond the scope of this paper to give a survey of results in this area and we refer the reader
to the survey papers by Keil [25] and Bern [5], and the references therein. As we proceed,
we will provide details on specic decomposition methods that we will be using.
We apply several optimization criteria to the decompositions that we employ. In the context
of Minkowski sums, it is natural to look for decompositions that minimize the number
of convex subpolygons. As we show in the sequel, we are also interested in decompositions
with minimal maximum vertex degree of the decomposition graph, as well as several other
criteria.
We report on our experiments with various decompositions and dierent input polygons.
As mentioned in the Abstract, among our ndings are that in general: (i) triangulations are
too costly, (ii) what constitutes a good decomposition for one of the input polygons depends
on the other input polygon | consequently, we develop a procedure for simultaneously
decomposing the two polygons such that a \mixed" objective function is minimized, (iii)
there are optimal decomposition algorithms that signicantly expedite the Minkowski-sum
computation, but the decomposition itself is expensive to compute | in such cases simple
heuristics that approximate the optimal decomposition perform very well.
In the next section we survey the Minkowski sum algorithms that we have implemented.
In Section 3 we describe the dierent decomposition algorithms that we have implemented.
We present a rst set of experimental results in Section 4 and lter out the methods that
turn out to be ine-cient. In Section 5 we focus on the decomposition schemes that are
not only fast to compute but also help compute the Minkowski sum e-ciently. We give
concluding remarks and propose directions for further work in Section 6.
nave triang. min d 2
triang. min convex
# of convex subpolygons in P 33 33 6
time (mSec) to compute P Q 2133 1603 120

Figure

5: Dierent decomposition methods applied to the polygon P (leftmost in the gure),
from left to right: nave triangulation, minimum d 2
triangulation and minimum convex decomposition
(the details are given in Section 3). The table illustrates, for each decomposition,
the sum of squares of degrees, the number of convex subpolygons, and the time in milliseconds
to compute the Minkowski sum of P and a convex polygon, Q, with 4 vertices.
Algorithms
Given a collection C of curves in the plane, the arrangement A(C) is the subdivision of
the plane into vertices, edges, and faces induced by the curves in C. Planar maps are arrangements
where the curves are pairwise interior disjoint. Our algorithms for computing
Minkowski sums rely on arrangements, and in the discussion below we assume some familiarity
with these structures, and with a renement thereof called the vertical decomposition;
we refer the reader to [2, 15, 34] for information on arrangements and vertical decomposi-
tion, and to [14, 17] for a detailed description of the planar maps and arrangements packages
in CGAL on which our algorithms are based.
The input to our algorithms are two polygonal sets P and Q, with m and n vertices
respectively. Our algorithms consist of the following three steps:
Step 1: Decompose P into the convex subpolygons P 1
into the convex
subpolygons
Step 2: For each i 2 [1::s] and for each j 2 [1::t], compute the Minkowski subsum
which we denote by R ij . We denote by R the set fR i;j [1::t]g.
Step 3: Construct the union of all the polygons in R, computed in Step 2; the output is
represented as a planar map.
The Minkowski sum of P and Q is the union of the polygons in R. Each R ij is a convex
polygon, and it can easily be computed in time that is linear in the sizes of P i and Q j [26].
Let k denote the overall number of edges of the polygons in R, and let I denote the overall
number of intersections between (edges of) polygons in R
We brie
y present two dierent algorithms for performing Step 3, computing the union
of the polygons in R, which we refer to as the arrangement algorithm and the incremental
union algorithm. A detailed description of these algorithms is given in [12].
Arrangement algorithm. The algorithm constructs the arrangement A(R) induced by
the polygons in R (we refer to this arrangement as the underlying arrangement of the
Minkowski sum) by adding the (boundaries of the) polygons of R one by one in a random
order and by maintaining the vertical decomposition the arrangement of the polygons added
so far; each polygon is chosen with equal probability at each step. Once we have constructed
the arrangement, we e-ciently traverse all its cells (vertices, edges, or faces) and we mark
a cell as belonging to the Minkowski sum if it is contained inside at least one polygon of R.
The construction of the arrangement takes randomized expected time O(I
The traversal stage takes O(I
Incremental union algorithm. In this algorithm we incrementally construct the union of
the polygons in R by adding the polygons one after the other in random order. We maintain
the planar map representing the union of the polygons added so far. For each r 2 R we
insert the edges of r into the map and then remove redundant edges from the map. All
these operations can be carried out e-ciently using the CGAL planar map package. We
can only give a nave bound O(k 2 log 2 k) on the running time of this algorithm, which in
the worst case is higher than the worst-case running time of the arrangement algorithm.
Practically however the incremental union algorithm works much better on most problem
instances.
Remarks. (1) We also implemented a union algorithm using a divide-and-conquer approach
but since it mostly behaves worse than the incremental algorithm we do not describe
it here. The full details are given in [12]. (2) Our planar map package provides full support
for maintaining the vertical decomposition, and for e-cient point location in a map.
However, using simple point location strategies (nave, walk-along-a-line) is often faster in
practice [14]. Therefore we ran the tests reported below without maintaining the vertical
decomposition.
3 The Decomposition Algorithms
We describe here the algorithms that we have implemented for decomposing the input
polygons into convex subpolygons. We use decompositions both with or without Steiner
points. Some of the techniques are optimal and some use heuristics to optimize certain
objective functions. The running time of the decomposition stage is signicant only when we
search for the optimal solution and use dynamic programming; in all other cases the running
time of this stage is negligible even when we implemented a nave solution. Therefore we
only mention the running time for the \heavy" decomposition algorithms.
We use the notation from Section 2. For simplicity of the exposition we assume here
that the input data for the Minkowski algorithm are two simple polygons P and Q. In
practice we use the same decomposition schemes that are presented here for general polygonal
sets, mostly without changing them at all. However this is not always possible. For
example, Keil's optimal minimum convex decomposition algorithm does not work on polygons
with holes 1 . Furthermore, the problem of decomposing a polygon with holes to convex
subpolygons is proven to be NP-Hard irrespective of whether Steiner points are allowed; see
[23]. Other algorithms that we use (e.g., AB algorithm) can be applied to general polygons
without changes. We discuss these decomposition algorithms in the following sections.
In what follows P is a polygon with n vertices r of which are re
ex.
3.1 Triangulation
Nave triangulation. This procedure searches for a pair of vertices such that the
segment is a diagonal, namely it lies inside the polygon. It adds such a diagonal,
splits the polygon into two subpolygons by this diagonal, and triangulates each subpolygon
recursively. The procedure stops when the polygon becomes a triangle. See Figure 5 for an
In some of the following decompositions we are concerned with the degrees of vertices in
the decomposition (namely the number of diagonals incident to a vertex). Our motivation
for considering the degree comes from an observation on the way our planar map structures
perform in practice: we noted that the existence of high degree vertices makes maintaining
the maps slower. The DCEL structure that is used for maintaining the planar map has,
from each vertex, a pointer to one of its incident halfedges. We can traverse the halfedges
around a vertex by using the adjacency pointers of the halfedges. If a vertex v i has d incident
halfedges then nding the location of a new edge around v i will take O(d) traversal steps.
To avoid the overhead of a search structure for each vertex, the planar-maps implementation
does not include such a structure. Therefore, since we build the planar map incrementally,
if the degree of v i in the nal map is d i then we performed  d
steps on this vertex. Trying to minimize this time over all the vertices we can either try
to minimize the maximum degree or the sum of squares of degrees, d 2
. Now, high degree
vertices in the decomposition result in high degree vertices in the underlying arrangement,
and therefore we try to avoid them. We can apply the same minimization criteria to the
vertices of the decomposition.
Optimal triangulation | minimizing the maximum degree. Using dynamic programming
we compute a triangulation of the polygon where the maximum degree of a vertex
minimal. The algorithm is described in [18], and runs in O(n 3 ) time.
Optimal triangulation | minimizing d 2
i . We adapted the minimal-maximum-degree
algorithm to nd the triangulation with minimum d 2
is the degree of vertex v i
1 In such cases we can apply a rst decomposition step that connects the holes to the outer boundary and
then use the algorithm on the simple subpolygons. This is a practical heuristic that does not guarantee an
optimal solution.

Figure

From left to right: Slab decomposition, angle \bisector" (AB) decomposition, and
KD decomposition
of the polygon. (See Figure 5 for an illustration.) The adaptation is straightforward. Since
both d 2
are global properties of the decomposition that can be updated in
constant time at each step of the dynamic programming algorithm | most of the algorithm
and the entire analysis remain the same.
3.2 Convex Decomposition without Steiner Points
Greedy convex decomposition. The same as the nave triangulation algorithm except
that it stops as soon as the polygon does not have a re
ex vertex.
Minimum number of convex subpolygons (min-convex). We apply the algorithm
of Keil [22], which computes a decomposition of a polygon into the minimum number of
convex subpolygons without introducing new vertices (Steiner points). The running time
of the algorithm is O(r 2 n log n). This algorithm uses dynamic programming. See Figure 5.
This result was recently improved to O(n
Minimum d 2
modied Keil's algorithm so that it will
compute decompositions that minimize d 2
i , the sum of squares of vertex degree. Like the
modication of the min-max degree triangulation, in this case we also modify the dynamic
programming scheme by simply replacing the cost function of the decomposition. Instead
of computing the number of polygons (as the original min-convex decomposition algorithm
does) we compute a dierent global property, namely the sum of squares of degrees. We
can compute d 2
i in constant time given the values d 2
i of the decompositions of two sub-
polygons.
3.3 Convex Decomposition with Steiner Points
Slab decomposition. Given a direction ~e, from each re
ex vertex of the polygon we extend
a segment in directions ~e and ~e inside the polygon until it hits the polygon boundary. The
result is a decomposition of the polygon into convex slabs. If ~e is vertical then this is the
well-known vertical decomposition of the polygon. See Figure 6. This decomposition gives
a 4-approximation to the optimal convex decomposition as it partitions the polygon into at
most 2r subpolygons and one needs at least dr=2e subpolygons. The obvious advantage
of this decomposition is its simplicity.
Angle \bisector" decomposition (AB). In this algorithm we extend the internal angle
\bisector" from each re
ex vertex until we rst hit the polygon's boundary or a diagonal
that we have already extended from another vertex 2 . See Figure 6. This decomposition
(suggested by Chazelle and Dobkin [6]) gives a 2-approximation to the optimal convex
If P has r re
ex vertices then every decomposition of P must include at
least dr=2e since every re
ex vertex should be eliminated by at least one
diagonal incident to it and each diagonal can eliminate at most 2 re
ex vertices. The AB
decomposition method extends one diagonal from each re
ex vertex until P is decomposed
into at most r subpolygons.
KD decomposition. This algorithm is inspired by the KD-tree method to partition a set
of points in the plane [8]. First we divide the polygon by extending vertical rays inside the
polygon from a re
ex vertex horizontally in the middle (the number of vertices to the left
of a vertex v, namely having smaller x-coordinate than v's, is denoted v l and the number of
vertices to the right of v is denoted v r . We look for a re
ex vertex v for which maxfv l
is minimal). Then we divide each of the subpolygons by extending an horizontal line from a
vertex vertically in the middle. We continue dividing the subpolygons that way (alternating
between horizontal and vertical division) until no re
ex vertices remain. See Figure 6. By
this method we try to lower the stabbing number of the subdivision (namely, the maximum
number of subpolygons in the subdivision intersected by any line) | see the discussion
in Section 5.2 below. The decomposition is similar to the quad-tree based approximation
algorithms for computing the minimum-length Steiner triangulations [10].
4 A First Round of Experiments
We present experimental results of applying the decompositions described in the previous
section to a collection of input pairs of polygons. We summarize the results and draw
conclusions that lead us to focus on a smaller set of decomposition methods (which we
study further in the next section).
4.1 Test Platform and Frame Program
Our implementation of the Minkowski sum package is based on the CGAL (version 2.0) and
LEDA (version 4.0) libraries. Our package works with Linux (g++ compiler) as well as with
(Visual C++ 6.0 compiler). The tests were performed under WinNT workstation
on a 500 MHz PentiumIII machine with 128 Mb of RAM.
2 It is not necessary to compute exactly the direction of the angle bisector, it su-ce to nd a segment
that will eliminate the re
ex vertex from which it is extended. Let v be a re
ex vertex and let u (w) be
the previous (resp. next) vertex on the boundary of the polygon then a segment at the direction !
divides the angle \uvw into two angles with less than 180 - each.

Figure

7: Star input: The input (on the left-hand side) consists of two star-shaped polygons.
The underlying arrangement of the Minkowski sum is shown in the middle. Running times in
seconds for dierent decomposition methods (for two star polygons with 20 vertices are
presented in the graph on the right-hand side.

Figure

8: Border input: The input (an example on the left-hand side) consists of a border of
a country and a star shaped polygon. The Minkowski sum is shown in the middle, and running
times in seconds for dierent decomposition methods (for the border of Israel with 50 vertices
and a star shaped polygon with 15 vertices) are shown in the graph on the right-hand side.
We implemented an interactive program that constructs Minkowski sums, computes
conguration space obstacles, and solves polygon containment and polygon separation prob-
lems. The software lets the user choose the decomposition method and the union algorithm.
It than presents the resulting Minkowski sum and underlying arrangement. The software
is available from http://www.math.tau.ac.il/~flato/.
4.2 Results
We ran the union algorithms (arrangement and incremental-union) with all nine decomposition
methods on various input sets. The running times for the computation of the
Minkowski sum for four input examples are summarized in Figures 7{10.
It is obvious from the experimental results that using triangulations causes the union

Figure

9: Random polygons input: The input (an example on the left-hand side) consists of
two random looking polygons. The Minkowski sum is shown in the middle, and running times in
seconds for dierent decomposition methods (for two random looking polygons with vertices
are shown in the graph on the right-hand side.

Figure

10: Fork input: The input consists of two orthogonal fork polygons. The Minkowski
sum is shown in the middle, and running times in seconds for dierent decomposition methods
(for two fork polygons with 8 teeth each) are shown in the graph on the right-hand side.

Figure

11: An example of a case where when using the min-convex decomposition the union
computation time is the smallest but it becomes ine-cient when considering the decomposition
time as well. The graph on the right-hand side shows the running times in seconds for computing
the Minkowski sum of two polygons (left-hand side) representing the borders of India and Israel
with 478 and 50 vertices respectively. Note that while constructing the Minkowski sum of these
two polygons the incremental union algorithm handles more than 40000 possibly intersecting
segments.
algorithms to run much slower (the left three pairs of columns in the histograms of Figures 7{
10). By triangulating the polygons, we create (n 1)(m 1) hexagons in R with potentially
intersections between the edges of these polygons. We get those poor results
since the performance of the union algorithms strongly depends on the number of vertices
in the arrangement of the hexagon edges. Minimizing the maximum degree or the sum
of squares of degrees in a triangulation is a slow computation that results in better union
performance (compared to the nave triangulation) but is still much worse than other simple
convex-decomposition techniques.
In most cases the arrangement algorithm runs much slower than the incremental union
approach. By removing redundant edges from the partial sum during the insertion of
polygons, we reduce the number of intersections of new polygons and the current planar
map features. The fork input is an exception since the complexity of the union is roughly
the same as the complexity of the underlying arrangement and the edges that we remove
in the incremental algorithm do not signicantly reduce the complexity of the planar map;
see

Figure

10. More details on the comparison between the arrangement union algorithm
and the incremental union algorithm are given in [13].
Although the min-convex algorithm is almost always the fastest in computing the union,
constructing this optimal decomposition may be expensive. For some inputs running with
the min-convex decomposition becomes ine-cient | see for example Figure 11. Minimizing
the sum of squares of degrees in a convex decomposition rarely results in a decomposition
that is dierent from the min-convex decomposition.
This rst round of experiments helped us to lter out ine-cient methods. In the next
section we focus on the better decomposition algorithms, i.e., minimum convex, slab, angle
\bisector", KD. We further study them and attempt to improve their performance.
5 Revisiting the More E-cient Algorithms
In this section we focus our attention on the algorithms that were found to be e-cient in
the rst round of experiments. As already mentioned, we measure e-ciency by combining
the running times of the decomposition step together with that of the union step. We
present an experiment showing that minimizing the number of convex subpolygons in the
decomposition does not always lead to better Minkowski-sum computation time; this is in
contrast with the impression that the rst round of results may give.
We also show in this section that in certain instances the decision how to decompose
the input polygon P may change depending on the other polygon Q, namely for the same
P and dierent Q's we should decompose P dierently based on properties of the other
polygon. This leads us to propose a \mixed" objective function for the simultaneous optimal
decomposition of the two input polygons. We present an optimization procedure for this
mixed function. Finally, we take the two most eective decomposition algorithms (AB and
KD) | not only are they e-cient, they are also very simple and therefore easy to modify
| and we try to improve them by adding various heuristics.
5.1 Nonoptimality of Min-Convex Decompositions
Minimizing the number of convex parts of P and Q can be not only expensive to compute,
but it does not always yield the best running time of the Minkowski-sum construction. In
some cases other factors are important as well. Consider for example the knife input data.
P is a long triangle with j teeth along its base and Q is composed of horizontal and vertical
teeth. See Figure 12. P can be decomposed into parts by extending diagonals
from the teeth in the base to the apex of the polygon. Alternatively, we can decompose
it into subpolygons with short diagonals (this is the \minimal length AB"
decomposition described below in Section 5.3). If we x the decomposition of Q, the latter
decomposition of P results in considerably faster Minkowski-sum running time, despite
having more subpolygons, because the Minkowski sum of the long subpolygons in the rst
decomposition with the subpolygons of Q results in many intersections between the edges
of polygons in R. In the rst decomposition we have long subpolygons while in the
latter we have subpolygons when only one of them is a \long" subpolygon and the
rest are subpolygons.
We can also see a similar behavior in real-life data. Computing the Minkowski sum of
the (polygonal representation of) countries with star polygons mostly worked faster while
using the KD-decomposition than with the AB technique; with the exception of degenerate
number of vertices 23448 9379
running time (sec) 71.7 25.6

Figure

12: Knife input: The input polygons are on the left-hand side. Two types of decompositions
of P (enlarged) are shown second left: on top, subpolygons with short diagonals
length, and below minimum convex decomposition with subpolygons with long diagonals.
Third from the left is the Minkowski sum of P and Q. The underlying arrangement (using
the short decomposition of P ) is shown on the right-hand side. The table below presents the
number of vertices in the underlying arrangement and the running time for both decompositions
(P has 20 teeth and 42 vertices and Q has 34 vertices).
polygons (i.e., with some re
ex vertices that share the same x or y coordinates), the KD
decomposition always generates at least as many subpolygons as the AB decomposition.
5.2 Mixed Objective Functions
Good decomposition techniques that handle P and Q separately might not be su-cient
because what constitutes a good decomposition of P depends on Q. We measured the
running time for computing the Minkowski sum of a knife polygon P (Figure 12 | the
knife polygon is second left) and a random polygon Q (Figure 9). We scaled Q dierently
in each test. We xed the decomposition of Q and decomposed the knife polygon P once
with the short length AB" decomposition and then with the long
minimum convex decomposition. The results are presented in Figure 13. We can see that
for small Q's the short decomposition of the knife P with more subpolygons performs better,
but as Q grows the long decomposition of P with fewer subpolygons wins.
These experiments imply that a more careful strategy would be to simultaneously decompose
the two input polygons, or at least take into consideration properties of one polygon
when decomposing the other.
The running time of the arrangement union algorithm is O(I is the
number of edges of the polygons in R and I is the overall number of intersections between
(edges of) polygons in R (see Section 2). The value of k depends on the complexity of the
convex decompositions of P and Q. Hence, we want to keep this complexity small. It is
harder to optimize the value of I . Intuitively, we want each edge of R to intersect as few
polygons of R as possible. If we consider the standard rigid-motion invariant measure  on
lines in the plane [33] and use L(C) to denote the set of lines intersecting a set C, then for any

Figure

13: Minkowski sum of a knife, P , with 22 vertices and a random polygon, Q, with 40
vertices using the arrangement union algorithm. On the left-hand side the underlying arrangement
of the sum with the smallest random polygon and on the right-hand side the underlying
arrangement of the sum with the largest random polygon. As Q grows, the number of vertices
I in the underlying arrangement is dropping from (about) 15000 to 5000 for the \long"
decomposition of P , and from 10000 to 8000 for the \short" decomposition.
is the perimeter of R ij . This suggests that we want to minimize the
total lengths of the diagonals in the convex decompositions of P and Q (Aronov and Fortune
[3] use this approach to show that minimizing the length of a triangulation can decrease
the complexity of the average-case ray-shooting query). But we want to minimize the two
criteria simultaneously, and let the decomposition of one polygon govern the decomposition
of the other.
We can see supporting experimental results for segments in Figure 14. In these experiments
we randomly chose a set T of points inside a square in R 2 and connected pairs of
them by a set S of random segments (for each segment we randomly chose its two endpoints
from T ). Then we measured the average number of intersections per segment as a function
of the average length of a segment. To get dierent average length of the segments, at each
round we chose each segment by taking the longest (or shortest) segment out of l randomly
chosen segments, where l is a small integer varying between 1 and 15. The average number
of intersections is I
where I is the total number of intersections in the arrangement A(S).
We performed 5 experiments for each value of l between 1 and 15, each plotted point in
the graph in Figure 14 represents such an experiment. The values of l are not shown in
the graph | they were used to generate sets of segments with dierent average lengths.
For the presented results, we took (this is a typical ratio between points and
segments in the set R for which we compute the arrangement A(R)). As the results show,
the intersection count per segment grows linearly (or close to linearly) with the average
length of a segment.
Therefore, we assume that the expected number of intersection of a segment in the

Figure

14: Average number of intersections per segment as a function of the average segment
length. Each point in the graph represent a conguration containing 125 randomly chosen points
in a square [0; 1000]  [0; 1000] in R 2 and 500 randomly chosen segments connecting pairs of
these points.
arrangement A(R) of the polygons of R is proportional to the total length of edges of A(R),
which we denote by  A(R) . The intuition behind the mixed objective function, which we
propose next, is that minimizing  A(R) will lead to minimizing I .
be the convex subpolygons into which P is decomposed. Let  P i
be
the perimeter of P i . Similarly dene . If R ij is the perimeter of R ij
(the Minkowski sum of P i and
Summing over all (i; j) we get
Let  P denote the perimeter of P and  P the sum of the lengths of the diagonals in P .
subpolygons and Q has kQ subpolygons. Let D P;Q
be the decomposition of P and Q. Then
The function c(D P;Q ) is a cost function of a simultaneous convex decomposition of P and
Q. Our empirical results showed that this cost function approximates the running time. We
want to nd a decomposition that minimizes this cost function. Let c
If we do not allow Steiner points, we can modify the dynamic-programming algorithm
by Keil [22] to compute c  in O(n 2 r 4
an auxiliary cost
which is the minimum total length of diagonals in a convex decomposition
of P into at most i convex polygons. Then
Since the number of convex subpolygons in any minimal convex decomposition of a simple
polygon is at most twice the number of the re
ex vertices in it, the values i and j are
at most 2r P and 2r Q , respectively, where r P (resp. r Q ) is the number of re
ex vertices in
Q). One can compute ^ c(P; i) by modifying Keil's algorithm [22] | the modied
algorithm as well as the algorithm for computing c  are described in detail in Appendix A.
Since the running time of this procedure is too high to be practical, we neither implemented
it, nor did we make any serious attempt to improve the running time. We regard this
algorithm as a rst step towards developing e-cient algorithms for approximating mixed
objective functions.
If we allow Steiner points, then it is an open question whether an optimal decomposition
can be computed in polynomial time. Currently, we do not even have a constant-factor
approximation algorithm. The di-culty arises because no constant-factor approximation is
known for minimum-length convex decomposition of a simple polygon if Steiner points are
allowed [23].
5.3 Improving the AB and KD methods
It seems from most of the tests that in general the AB and KD decomposition algorithms
work better than the other heuristics. We next describe our attempts to improve these
algorithms.
Minimal length angle \bisector" decomposition. In each step we handle one re
ex
vertex. A re
ex vertex can always be eliminated by at most two diagonals. For any three
diagonals that eliminate a re
ex vertex, at least one of them can be removed while the
vertex is still eliminated. In this algorithm, for each re
ex vertex we look for the shortest
one or two diagonals that eliminate it. As we can see in Figure 16, the minimal length AB
decomposition performs better than the nave AB even though it generally creates more
subpolygons.
While the AB decomposition performs very well, in some cases (concave chains, countries
borders) the KD algorithm performs better. We developed the KD-decomposition technique
aiming to minimize the stabbing number of the decomposition of the input polygons (which
in turn, as discussed above, we expect to reduce the overall number I of intersections in the
underlying arrangement A(R) of the polygons of R). This method however often generates
too many convex parts. We tried to combine these two algorithms as follows.
Angle \bisector" and KD decomposition (AB+KD). In this algorithm we check the
two neighbors vertices of each re
ex vertex v; if v 1 and v 2 are convex, we extend a
\bisector" from v. We apply the KD decomposition algorithm for the remaining non-convex
polygons. By this method we aim to lower the stabbing number without creating redundant
convex polygons in the sections of the polygons that are not bounded by concave chains).
We tested these algorithms on polygons with dierent number of convex vertices, vertices
in concave chains and \tooth vertices". The results in Figure 15 suggest that AB+KD
performs best when the numbers of vertices in concave chains and of tooth vertices are
roughly the same. If there are more tooth vertices than vertices in concave chains, then the
AB decomposition performs better.
Next, we tried to further decrease the number of convex subpolygons generated by the
decomposition algorithm. Instead of emanating a diagonal from any re
ex vertex, we rst
tested whether we can eliminate two re
ex vertices with one diagonal (let's call such a
diagonal a 2-re
ex eliminator). All the methods listed below generate at most the same
number of subpolygons generated by the AB algorithm but practically the number is likely
to be smaller.
Improved angle \bisector" decomposition. For a re
ex vertex, we look for 2-re
ex
eliminators. If we cannot nd such a diagonal we continue as in the standard AB algorithm.
Re
ex angle \bisector" decomposition. In this method we work harder trying to nd
2-re
ex eliminator diagonals. In each step we go over all re
ex vertices trying to nd an
eliminator. If there are no more 2-re
ex eliminators, we continue with the standard AB
algorithm on the rest of the re
ex vertices.
Small side angle \bisector" decomposition. As in the re
ex AB decomposition, we
are looking for 2-re
ex eliminators. Such an eliminator decomposes the polygon into two
parts, one on each of its side. Among the candidate eliminators we choose the one that has
the minimal number of re
ex vertices on one of its sides. Vertices on dierent sides of the
added diagonal cannot be connected by another diagonal because it will intersect the added
diagonal. By choosing this diagonal we are trying to \block" the minimal number of re
ex
vertices from being connected (and eliminated) by another 2-re
ex eliminator diagonal.
Experimental results are shown in Figure 16. These latter improvements to the AB
decomposition seem to have the largest eect on the union running time, while keeping
the decomposition method very simple to understand and implement. Note that the small
side AB heuristic results in 20% faster union time than the improved AB and re
ex AB
decompositions, and 50% faster than the standard angle \bisector" method. When we use
the small side AB with the input set used in Figure 11 the overall running time is about
376 seconds which is at least three times faster than the results achieved by using other
decomposition methods.
6 Conclusions
We presented a general scheme for computing the Minkowski sum of polygons. We implemented
union algorithms which overcome all possible degeneracies. Using exact number
types and special handling for geometric degeneracies we obtained a robust and exact im-
Figure

15: Running times for computing the chain input using AB, KD, and AB+KD decomposition

Figure

Union running times for countries borders input (Chile with 368 vertices on the left-hand
side and Norway with 360 vertices on the right-hand side) with the improved decomposition
algorithms.
plementation that could handle all kinds of polygonal inputs. The emphasis of this paper
is on the eect of the decomposition method on the e-ciency of the overall process.
We implemented over a dozen of decomposition algorithms, among them triangulations,
optimal decompositions for dierent criteria, approximations and heuristics. We examined
several criteria that aect the running time of the Minkowski-sum algorithm. The most effective
optimization is minimizing the number of convex subpolygons. Thus, triangulations
which are widely used in the theoretical literature are not practical for the Minkowski-sum
algorithms. We further found that minimizing the number of subpolygons is not always
su-cient. Since we deal with two polygonal sets that are participating in the algorithm we
found that it is smarter to decompose the polygons simultaneously minimizing a cost function
which takes into account the decomposition of both input set. Optimal decompositions
for this function and also simpler cost functions like the overall number of convex sub-
polygons were practically too slow. In some cases the decomposition step of the Minkowski
algorithm took more time than the union step. Therefore, we developed some heuristics that
approximate very well a cost function and run much faster than their exact counterparts.
Allowing Steiner points, the angle \bisector" decomposition gives a 2-approximation for
the minimal number of convex subpolygons. The AB decomposition with simple practical
modications (small-side AB decomposition) is a decomposition that is easy to implement,
very fast to execute and gives excellent results in the Minkowski-sum algorithm.
We propose several direction for further research:
1. Use the presented scheme and the practical improvement that we proposed with real-life
applications such as motion planning and GIS and examine the eect of dierent
decompositions for those special types of input data.
2. Further improve the AB decomposition algorithms to give better theoretical approximation
and better running times.
3. We tested the e-ciency of the Minkowski-sum algorithm with dierent convex decomposition
methods, but the algorithm will still give a correct answer if we will have
a covering of the input polygons by convex polygons. Can one further improve the
e-ciency of the Minkowski sum program using coverings instead of decompositions.



--R

The CGAL User Manual

Approximating minimum-weight triangulations in three dimensions
Kim Generation of con

Optimal convex decompositions.
Limited gaps.
Computational Ge- ometry: Algorithms and Applications

Approximating the minimum weight Steiner triangulation.

Robust and e-cient construction of planar Minkowski sums
Robust and e-cient construction of planar Minkowski sums
The design and implementation of planar maps in CGAL.

A general framework for assembly planning: The motion space approach.
The design and implementation of planar arrangements of curves in CGAL.
Triangulating planar graphs while minimizing the maximum degree.
Computing Minkowski sums of plane curves.
Computing Minkowski sums of regular polygons.
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
Decomposing a polygon into simpler components.
Minimum decompositions of polygonal objects.
On the time bound for convex decomposition of simple polygons.
Polygon decomposition.
Robot Motion Planning.
Polynomial/rational approximation of minkowski sum boundary curves.
Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams


Placement and compaction of nonconvex polygons for clothing manufacture.
Computational Geometry: An Introduction Through Randomized Algo- rithms



--TR
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
Davenport-Schinzel sequences and their geometric applications
Computational geometry
Arrangements
Triangulations
Polynomial/rational approximation of Minkowski sum boundary curves
LEDA
On the design of CGAL a computational geometry algorithms library
The design and implementation of panar maps in CGAL
Robot Motion Planning
Triangulating Planar Graphs While Minimizing the Maximum Degree

--CTR
Hayim Shaul , Dan Halperin, Improved construction of vertical decompositions of three-dimensional arrangements, Proceedings of the eighteenth annual symposium on Computational geometry, p.283-292, June 05-07, 2002, Barcelona, Spain
Ron Wein, Exact and approximate construction of offset polygons, Computer-Aided Design, v.39 n.6, p.518-527, June, 2007
Eyal Flato , Efi Fogel , Dan Halperin , Eran Leiserowitz, Exact minkowski sums and applications, Proceedings of the eighteenth annual symposium on Computational geometry, p.273-274, June 05-07, 2002, Barcelona, Spain
Fogel , Dan Halperin , Christophe Weibel, On the exact maximum complexity of Minkowski sums of convex polyhedra, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
Goce Trajcevski , Peter Scheuermann , Herv Brnnimann , Agns Voisard, Dynamic topological predicates and notifications in moving objects databases, Proceedings of the 6th international conference on Mobile data management, May 09-13, 2005, Ayia Napa, Cyprus
Goce Trajcevski , Peter Scheuermann , Herve Brnnimann, Mission-critical management of mobile sensors: or, how to guide a flock of sensors, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada
Ron Wein , Jur P. van den Berg , Dan Halperin, The visibility--voronoi complex and its applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
Ron Wein , Jur P. van den Berg , Dan Halperin, The visibility-Voronoi complex and its applications, Computational Geometry: Theory and Applications, v.36 n.1, p.66-87, January 2007
Vladlen Koltun, Pianos are not flat: rigid motion planning in three dimensions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Goce Trajcevski , Ouri Wolfson , Klaus Hinrichs , Sam Chamberlain, Managing uncertainty in moving objects databases, ACM Transactions on Database Systems (TODS), v.29 n.3, p.463-507, September 2004
Julia A Bennell , Xiang Song, A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums, Computers and Operations Research, v.35 n.1, p.267-281, January, 2008
minkowski sum;experimental results;convex decomposition;polygon decomposition