Robust and Efficient Construction of Planar Minkowski Sums.
Eyal Flato, Dan Halperin · 2000
The Minkowski sum (also known as the vector sum) of two sets P and Q in IR 2 is the set fp + q j p 2 P; q 2 Qg. 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