Overview
Minkowski sums are useful for collision detection, configuration-space obstacles, and geometric offsetting.
ExtendedSource checked
Minkowski Sum
Combines two shapes by adding every point in one shape to every point in the other.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Advanced
- Family
- Shape Operation
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
pointwise additionconfiguration spaceconvex polygonshape offset
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n + m)
Average
O(n + m)
Worst
O(n m)
Space
O(n + m)
When to Use
- Use when collision and intersection tests needs pointwise addition.
- Use when the input matches the assumptions behind shape Operation.
When Not to Use
- Avoid when floating-point robustness is critical and no tolerance strategy is defined.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Combines two shapes by adding every point in one shape to every point in the other
- Uses pointwise addition and configuration space to guide the work.
- Produces geometric relation, simplified shape, or constructed geometry.
Use Cases
- Collision and intersection tests
- Shape analysis
- Geometry processing
Inputs
- Points, segments, polygons, or meshes
- Query shape or tolerance
Outputs
- Geometric relation, simplified shape, or constructed geometry
Key Formulas (1)
Minkowski sum
A + B = {a + b | a in A, b in B}
A + B = {a + b | a in A, b in B}Defines the combined shape from all pairwise point sums.
Pseudocode
- 1.Prepare the inputs and state needed for Minkowski Sum.
- 2.Apply the pointwise addition step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return geometric relation, simplified shape, or constructed geometry.
Canonical Example
- Input
- Minkowski Sum input with a small representative case
- Output
- Geometric relation, simplified shape, or constructed geometry
- Explanation
- Minkowski Sum applies pointwise addition to produce geometric relation, simplified shape, or constructed geometry.
Implementation Notes
- Use robust orientation and tolerance checks for boundary cases.
- Keep the pointwise addition step separate enough to test independently.
Common Pitfalls
- Degenerate cases such as collinear points or shared edges often need explicit handling.
- Forgetting to check edge cases can make Minkowski Sum look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasDraw the input shapes, active tests, and generated geometric result.
Step 1 of 4: Prepare the inputs and state needed for Minkowski Sum.
geometry-mechanismNotes
Minkowski Sum should be used with the assumptions and tradeoffs of shape Operation in mind.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookTextbook support for Minkowski Sum's computational geometry problem family, predicates, structures, or geometric construction.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Minkowski Sum in the computational geometry benchmark area.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byExpanding Polytope Algorithm
Simulation · Specialized
EPA works in Minkowski-difference space after collision is detected.
Compare with thisUsed byGJK Collision Detection
Simulation · Specialized
GJK uses support points of the Minkowski difference.
Compare with thisRelationships
View full relationship pageDepends onConvex Hull
Minkowski operations often use convex polygon or polytope structure.
Used byExpanding Polytope Algorithm
EPA works in Minkowski-difference space after collision is detected.
Used byGJK Collision Detection
GJK uses support points of the Minkowski difference.
Related Algorithms
Tags
Computational GeometryGeometryPolygonsCollision Detection