A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes

DOI10.1007/978-3-030-67899-9_14MaRDI QIDQ831714zbMATH OpenOpenAlexFDO

Authors Sandip Das, Swami Sarvottamananda, S. Dev

Publication date 24 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-67899-9_14

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
• scientific article; zbMATH DE number 1728309
• Exact and efficient construction of Minkowski sums of convex polyhedra with applications
• Exact and efficient construction of Minkowski sums of convex polyhedra with applications
• Contributing vertices-based Minkowski sum computation of convex polyhedra

Cites work

• scientific article; zbMATH DE number 1728309 (Why is no real title available?)
• scientific article; zbMATH DE number 3986641 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• An optimal convex hull algorithm in any fixed dimension
• Computational geometry. Algorithms and applications.
• Convex Polytopes
• Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method
• From the zonotope construction to the Minkowski addition of convex polytopes
• Maximal f-vectors of Minkowski sums of large numbers of polytopes
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Output-sensitive results on convex hulls, extreme points, and related problems
• Polygon decomposition for efficient construction of Minkowski sums
• Powers of tensors and fast matrix multiplication
• Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions
• Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums

Cited in

(5)

• The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
• Contributing vertices-based Minkowski sum computation of convex polyhedra
• A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums
• The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential
• A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes

This page was built for publication: A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831714)