A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
From MaRDI portal
Publication:6126717
DOI10.1016/j.dam.2024.02.004MaRDI QIDQ6126717
Subhadeep Ranjan Dev, Swami Sarvottamananda, Sandip Das
Publication date: 10 April 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Mixed volumes and related topics in convex geometry (52A39) Combinatorial complexity of geometric structures (52C45)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The maximum number of faces of the Minkowski sum of two convex polytopes
- Maximal f-vectors of Minkowski sums of large numbers of polytopes
- Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
- A worst-case optimal algorithm to compute the Minkowski sum of convex polytopes
- An optimal convex hull algorithm in any fixed dimension
- From the zonotope construction to the Minkowski addition of convex polytopes
- Finding the convex hull facet by facet
- A generalization of the fast LUP matrix decomposition algorithm and applications
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
- Linear Optimization Queries
- 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
- Polygon decomposition for efficient construction of Minkowski sums
