Close this search box.

Minkowski Sums


Minkowski Sums
Minkowski sum used for Robot Motion Planning The Minkowski sum of the robot (yellow, upper third) and the obstacles in an environment (green) described as polygons is the forbidden area for the robot with respect to some point within it. In the above example, the robot can just barely find its way out to the left of the rightmost column of obstacles

The Minkowski sum (also known as the vector sum) of two sets \(P\) and \(Q\) in \(\mathbb{R}^2\) is the set \(\{p+q | p \in P, q \in Q\}\). Minkowski sums are useful in robot motion planning computer-aided design and manufacturing (CAD/CAM) and many other areas. We present a software package for robust and efficient construction of Minkowski sums of planar polygonal sets. We describe the different algorithms that we implemented and an experimental comparison between them. A distinctive feature of our implementation is that it can accurately handle degenerate input and in particular it can identify degenerate “holes” in the Minkowski sum which consist of a line segment or a singular point. 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 the various decompositions and different input polygons. Among our findings are that in general: (i) triangulations are too costly (although they can be produced quickly, they considerably slow down the Minkowski-sum computation), (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.

Movie & Links

  • Eyal Flato, Efi Fogel, Dan Halperin, and Eran Leiserowitz
    Exact Minkowski Sums and Applications
    In Proceedings of the 18th ACM Symposium on Computational Geometry (SoCG), pages 273-274, Barcelona, 2002 [mp4 (11 MB)] [bibtex]
  • Eyal Flato and Dan Halperin
    Robust and Efficient Construction of Planar Minkowski Sums
    In Abstracts 16th European Workshop Computational Geometry (EuroCG), pages 85-88, Eilat, Ben-Gurion University of the Negev, 2000 [pdf] [bibtex]
  • Eyal Flato
    M.Sc. thesis [pdf]
  • Pankaj AgarwalDan Halperin, and Eyal Flato
    Polygon Decomposition for Efficient Construction of Minkowski Sums
    Computational Geometry: Theory and Applications, 21(1-2): 39-61, 2002 [link] [bibTex]
    In Proceedings of the 8th European Symposium on Algorithms (ESA), 1879: 20-31, Springer, LNCS, Saarbrucken, 2000 [link] [bibtex]


Eyal Flato

Yair Oz - Webcreator


Skip to content