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

DOI10.1007/978-3-030-67899-9_14OpenAlexW3128098595MaRDI QIDQ831714FDOQ831714

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Powers of tensors and fast matrix multiplication
• An optimal convex hull algorithm in any fixed dimension
• Convex Polytopes
• From the zonotope construction to the Minkowski addition of convex polytopes
• The maximum number of faces of the Minkowski sum of two 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
• Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
• Output-sensitive results on convex hulls, extreme points, and related problems
• Polygon decomposition for efficient construction of Minkowski sums
• Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method
• Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions

Cited In (5)

• 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
• 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)