Polygon decomposition for efficient construction of Minkowski sums

DOI10.1016/S0925-7721(01)00041-4zbMath0991.68124MaRDI QIDQ5959553

Eyal Flato, Dan Halperin, Pankaj K. Agarwal

Publication date: 14 March 2002

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

Minkowski sumspolygon decomposition

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Exact Minkowski sums of polygons with holes, A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes, Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces, Advanced programming techniques applied to CGAL's arrangement package, A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums, The geometry of nesting problems: a tutorial, Complete and robust no-fit polygon generation for the irregular stock cutting problem, Aircraft parking stand allocation problem with safety consideration for independent hangar maintenance service providers, The visibility-Voronoi complex and its applications, An emergent computation approach to the problem of polygon layout with performance constraints, Mixed-Integer programming models for irregular strip packing based on vertical slices and feasibility cuts, A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes, A parallel biased random-key genetic algorithm with multiple populations applied to irregular strip packing problems, Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions, Capturing points with a rotating polygon (and a 3D extension), A general method for decomposing self-intersecting polygon to normal based on self-intersection points, Mathematical model and efficient algorithms for object packing problem, Irregular packing problems: a review of mathematical models, Closed-form characterization of the Minkowski sum and difference of two ellipsoids, On the exact maximum complexity of Minkowski sums of polytopes, A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering

Uses Software

• CGAL
• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• Generation of configuration space obstacles: The case of moving algebraic curves
• Approximating minimum-weight triangulations in three dimensions
• Approximating the minimum weight Steiner triangulation
• A general framework for assembly planning: The motion space approach
• Decomposing a Polygon into Simpler Components
• On the design of CGAL a computational geometry algorithms library
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• COMPUTING MINKOWSKI SUMS OF PLANE CURVES
• Triangulating planar graphs while minimizing the maximum degree