Collision detection between two convex shapes can be reframed as a question about one derived shape: does their Minkowski difference contain the origin? The Gilbert–Johnson–Keerthi procedure, usually called GJK, does not build that difference explicitly. It asks each original shape for its farthest point in selected directions, forms support points of the difference, and maintains a small simplex—point, segment, triangle or tetrahedron—near the origin. Mathematics matters because vectors, dot products, convexity and closest-point geometry turn a potentially huge pair of meshes into repeated directional queries with a compact certificate of separation or intersection.
The practical search question is not simply “what is this named method?” but “which mathematical structure makes the method work, what does it guarantee, and what evidence would show that it is a poor choice?” This article keeps those questions together so students can connect mathematics education with computing, engineering, data reasoning and careful everyday decisions without turning one technique into a career promise.
Quick navigation: Why it matters · Mechanism · Worked example · Deeper ideas · Investigations · Limits · Learning route · Parent guidance · FAQs · Sources
Why this mathematics matters
Mathematics is important here because it turns an apparently visual or computational trick into a chain of reasons. The representation tells us what information is kept. The equation or invariant explains each legal step. The complexity analysis describes the work. The boundary conditions say when a conclusion should not be trusted. That combination is a practical form of problem-solving literacy.
A strong learner should be able to move in both directions: from a real task to a mathematical model, and from a formal guarantee back to its real meaning. Naming an algorithm is not enough. The useful achievement is to explain why the next operation is valid, check a small instance independently, and notice which assumptions the implementation has added.
Source: Gilbert, Johnson and Keerthi’s 1988 IEEE paper.
Primary or implementation reference: Bullet Physics maintained GJK/EPA collision test source and examples.
How the mechanism works
For a convex set A, the support mapping s_A(d) returns a point maximising d·a. For the Minkowski difference A−B, use s_{A−B}(d)=s_A(d)−s_B(−d), so no full difference polytope is constructed. Start with a search direction and one support point. Build a simplex from new support points in directions aimed toward the origin. After each addition, keep only the simplex feature whose Voronoi region can contain the nearest point to the origin, and choose a new direction from that nearest point. If the origin is enclosed, the convex shapes intersect. If the support plane cannot pass the origin in the search direction, the shapes are separated. Distance variants iterate toward the closest simplex point and track witnesses on A and B.
Two convex sets A and B intersect exactly when 0 belongs to A−B={a−b:a in A,b in B}. If a=b at a shared point, their difference is zero; conversely zero difference implies a common point. A support mapping supplies an extreme point without listing every point in the convex body. Carathéodory’s theorem explains why a small simplex suffices: in d dimensions, membership in a convex hull needs at most d+1 points. Dot products select half-spaces and barycentric coordinates locate the closest point on a simplex. Numerical tolerances and termination rules convert this exact geometry into software.
Keep a four-column notebook labelled object, rule, guarantee and caveat. In the first column name the inputs and stored state. In the second write one update precisely. In the third state what remains true after the update. In the fourth record a tie, approximation, domain restriction or hardware assumption. This routine prevents symbols from drifting away from their meaning.
Worked example and core calculations
Let rectangle A=[−1,1]×[−1,1] and rectangle B=[2,4]×[−1,1]. Their Minkowski difference has x-range [−1−4,1−2]=[−5,−1] and y-range [−1−1,1−(−1)]=[−2,2]. The origin is not inside because every x-coordinate is at most −1; the Euclidean separation is 1, matching the gap between A’s right edge x=1 and B’s left edge x=2. Move B left to [0.5,2.5]×[−1,1]. Then A−B has x-range [−3.5,0.5] and y-range [−2,2], which contains (0,0), so the rectangles overlap. GJK obtains this conclusion through support directions rather than explicitly constructing these boxes.
How to audit the calculation
- Recompute every intermediate value directly from the definition.
- Keep labels, indices, signs, units and normalisation visible.
- Test a case with a known exact answer.
- State tie rules, random seeds, tolerances and boundary conventions.
- Compare with a slower transparent baseline or trusted implementation.
- Separate agreement of numbers from suitability of the real-world model.
Small examples are not childish; they are diagnostic instruments. A five-line trace can reveal a reversed inequality, a missing scale factor or an inconsistent label convention before a large dataset hides the same error behind plausible output.
Four deeper ideas
Collision becomes origin containment
The Minkowski difference replaces two moving shapes with one convex set and a fixed query point.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Support mappings are compact interfaces
A sphere, box or hull can answer extreme-point queries directly, so the algorithm need not enumerate a dense surface.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
The simplex records only relevant extremes
Closest-point tests discard vertices whose convex region cannot contain the origin, keeping state small in two or three dimensions.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Witness points make distance interpretable
Distance variants retain the corresponding points on A and B, not only a scalar gap, which supports contact and debugging.
To transfer this idea, ask what would remain true if labels, scale or input order changed. Then identify the step whose justification would fail if the stated assumption were removed. This turns the paragraph into a reusable reasoning pattern rather than a fact to memorise.
Twelve practical investigations
1. Separated rectangles
Use the worked ranges. Confirm a unit gap.
What the mathematics reveals: Origin exclusion certifies separation. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Axis alignment makes this a baseline. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
2. Overlapping rectangles
Shift B left. Check origin containment.
What the mathematics reveals: The same model flips the result. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Touch and overlap need a convention. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
3. Touching faces
Set B left edge to x=1. Compare strict and tolerant decisions.
What the mathematics reveals: Boundary membership is exact geometry. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Software may add margins. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
4. Circle support
Use s(d)=c+r d/||d||. Verify extreme points.
What the mathematics reveals: Smooth shapes have analytic mappings. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Handle d=0. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
5. Triangle simplex
Choose three support points around the origin. Compute barycentric coordinates.
What the mathematics reveals: Convex combinations test containment. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Orientation signs must agree. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
6. Duplicate support
Repeat a direction on a flat face. Detect no progress.
What the mathematics reveals: Termination requires progress rules. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not loop forever. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
7. Rotated box
Transform d into local coordinates. Return support in world space.
What the mathematics reveals: Linear algebra separates shape and pose. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Transform normals correctly. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
8. Nonconvex crescent
Attempt one support mapping. Show the convex hull ambiguity.
What the mathematics reveals: Convexity is structural. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Decompose or change method. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
9. EPA follow-up
Start from an intersecting simplex. Expand a polytope toward the nearest face.
What the mathematics reveals: Penetration is a second problem. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: EPA has its own degeneracies. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
10. Continuous motion
Move a shape rapidly between frames. Compare sampled and swept tests.
What the mathematics reveals: Static checks can tunnel. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Time of impact needs extra mathematics. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
11. Broad phase
Wrap shapes in AABBs. Reject obviously separate pairs first.
What the mathematics reveals: Hierarchy saves queries. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: AABB overlap is not final collision. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
12. Engine audit
Run maintained Bullet examples. Record margin, tolerance and iterations.
What the mathematics reveals: Implementations embody policies. Evidence to collect: write the input, predict the next state, carry out the calculation, and compare the result with an independently produced reference. Explain the exact invariant, equation, inequality or counting rule that supports the conclusion. Then vary one assumption and record whether the result changes smoothly, discontinuously or not at all.
Limit to keep visible: Do not generalise one benchmark. A useful report places this boundary beside the result rather than hiding it in a final disclaimer.
Limits and misconceptions
Classical GJK assumes convex shapes. Nonconvex models need convex decomposition, compound handling or another narrow-phase method, normally after a broad phase has rejected distant pairs. Intersection does not by itself give penetration depth or a stable contact manifold; engines often follow with EPA or another contact algorithm. Touching, nearly parallel faces, duplicate support points and very thin features can cause slow convergence or ambiguous tolerance decisions. Finite precision means “contains the origin” becomes a policy involving margins and stopping criteria. Continuous collision over time is a different problem from one static pose. A fast game-physics result is not automatically suitable for safety certification or robotics without a full error and dynamics analysis.
Five misconceptions to challenge
- GJK tests arbitrary meshes directly: Its core guarantee is for convex sets or convex pieces.
- It constructs the whole Minkowski difference: It samples support points on demand.
- An intersection result gives penetration depth: A follow-up method is usually needed.
- Zero numerical distance always means true overlap: Tolerance, margin and degeneracy policies matter.
- A narrow-phase test replaces broad-phase culling: Large systems normally use both at different scales.
Another broad misconception is that advanced mathematics automatically creates intelligence, admission, income or employment. It does not. Deliberate study can strengthen modelling, abstraction, calculation and explanation, while real pathways also depend on interests, communication, domain knowledge, opportunities and circumstances outside one topic.
A learning route for students
Move from a visible trace to a symbolic rule, then to code and critique. For every step below, prepare three pieces of evidence: a correct hand example, a boundary or failure case, and a short explanation using the relevant invariant. Do not advance merely because software returned a number.
Step 1: Calculate a minkowski difference
Begin with the smallest non-trivial instance that lets you calculate a Minkowski difference. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 2: Derive a support mapping
Begin with the smallest non-trivial instance that lets you derive a support mapping. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 3: Use dot products for extreme points
Begin with the smallest non-trivial instance that lets you use dot products for extreme points. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 4: Trace a simplex update
Begin with the smallest non-trivial instance that lets you trace a simplex update. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 5: Test origin containment
Begin with the smallest non-trivial instance that lets you test origin containment. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 6: Calculate closest points
Begin with the smallest non-trivial instance that lets you calculate closest points. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 7: Retain witness points
Begin with the smallest non-trivial instance that lets you retain witness points. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 8: Choose termination tolerances
Begin with the smallest non-trivial instance that lets you choose termination tolerances. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 9: Separate broad and narrow phases
Begin with the smallest non-trivial instance that lets you separate broad and narrow phases. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
Step 10: Identify nonconvex limitations
Begin with the smallest non-trivial instance that lets you identify nonconvex limitations. Predict the result before calculating. Write each state change clearly enough that another student can reproduce it. Compare with a trusted implementation only after the hand trace is complete.
Next, change one feature—size, ordering, sign, tolerance, labelling or data distribution—and explain which part of the reasoning changes. Finish by teaching the step without code and by naming one input for which the method is unhelpful. This predict–calculate–vary–explain cycle is a strong test of transferable understanding.
A four-week practice plan
- Week 1 — vocabulary and diagrams: define each object, redraw the mechanism and reproduce the worked example.
- Week 2 — equations and manufactured tests: derive the key relation and test inputs with known answers.
- Week 3 — implementation and evidence: use a trusted library, record parameters and compare with a transparent baseline.
- Week 4 — transfer and critique: apply the method to a new context, report limits and identify when a different method is better.
Guidance for parents and educators
Ask “what stays true?” and “what could make this conclusion fail?” before asking for speed. Invite the student to draw the input and output, estimate the result and locate the first step that disagrees with a reference. These prompts reveal conceptual understanding more clearly than memorised terminology.
Advanced enrichment should sit beside secure school foundations in algebra, functions, geometry, statistics and computational thinking. It need not accelerate a student into a fixed career identity. A healthy goal is curiosity with discipline: the learner becomes comfortable reading unfamiliar notation, checking an example, revising a model and communicating uncertainty.
Evidence prompts for a useful conversation
- Which quantity is observed and which is inferred?
- Which step saves work, and why is it allowed?
- Is the claim exact, approximate, probabilistic or empirical?
- What units and conventions are in use?
- Which input makes the method struggle?
- What simple baseline could check the answer?
- What would count as evidence that the parameters are poor?
Mini-project assessment
A strong mini-project contains the original question, a small reproducible dataset, a hand-worked example, code or a spreadsheet trace, at least one boundary test, a comparison with a baseline, and a paragraph on limits. Assess the reasoning trail as well as the final output. Repairing a model after a surprising result is valuable mathematical progress.
Six evidence checks for a finished project
Check 1: Calculate a minkowski difference
Ask the student to demonstrate how to calculate a Minkowski difference without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 2: Derive a support mapping
Ask the student to demonstrate how to derive a support mapping without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 3: Use dot products for extreme points
Ask the student to demonstrate how to use dot products for extreme points without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 4: Trace a simplex update
Ask the student to demonstrate how to trace a simplex update without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 5: Test origin containment
Ask the student to demonstrate how to test origin containment without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Check 6: Calculate closest points
Ask the student to demonstrate how to calculate closest points without relying on a hidden software step. The evidence should include a labelled input, the exact rule used, one intermediate state and a result that can be checked independently. If the answer changes after labels or order change, the student should say whether that reflects the mathematics or only a convention.
Then request one deliberately awkward example. The learner should predict the difficulty before running the method, explain what the output does and does not establish, and name a reasonable alternative or safeguard. This check joins correctness with judgement: a technically valid calculation is useful only when its assumptions and interpretation remain visible.
Frequently asked questions
What does GJK stand for?
Gilbert–Johnson–Keerthi, after the authors of the 1988 distance procedure.
What is the key transformation?
A and B intersect exactly when their Minkowski difference contains the origin.
What is a support mapping?
A function returning an extreme point in a requested direction.
Does GJK build the full Minkowski difference?
No; it queries support points as needed.
What is the simplex?
A small convex hull of sampled support points used to approach or enclose the origin.
Can it handle nonconvex shapes?
Not directly as one core convex query.
Does it return penetration depth?
Not by the basic intersection test; EPA or another follow-up is common.
Why are tolerances important?
Finite precision makes touching and stalled progress numerically delicate.
Is it continuous collision detection?
No; a static GJK query tests one pose.
What should students know first?
Vectors, dot products, convex hulls, coordinates and closest-point geometry.
Useful next reading and sources
Source: Gilbert, Johnson and Keerthi’s 1988 IEEE paper.
Source: Bullet Physics maintained GJK/EPA collision test source and examples.
Related eduKateSG reading: Graham scan, orientation tests and convex hulls.
Related eduKateSG reading: Vose’s alias method and probability tables.
Related eduKateSG reading: Numerical stability, conditioning and cancellation.
Read sources with a question in mind: which definition, theorem, default or limitation is being supported? An authoritative link is useful evidence, but it does not replace a worked calculation or a clear statement of how the source applies to the example.
A cheerful final thought
Mathematics becomes friendlier when every symbol has a job and every claim has a boundary. Start small, make the state visible, test the awkward case, and celebrate the moment when a pattern becomes explainable. That is the practical benefit of learning mathematics: not certainty about every future, but a growing ability to ask better questions and build trustworthy answers.