Math @ Duke

Publications [#235447] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Flato, E; Halperin, D, Polygon decomposition for efficient construction of Minkowski sums,
Computational Geometry, vol. 21 no. 12
(2002),
pp. 3961, ISSN 09257721
(last updated on 2018/02/24)
Abstract: 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 wellknown 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 Minkowskisum computation, but the decomposition itself is expensive to compute  in such cases simple heuristics that approximate the optimal decomposition perform very well. ©2002 Elsevier Science B.V. All rights reserved.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

