Minkowski addition Created 2026-10-06 Updated 2026-10-14
The Minkowski sum of subsets of a vector space collects the result of vector addition for every possible pair:
Think of fixing a point of , making a translation of the whole of by , and then taking the union of these copies over every . The points of specify displacement vectors; they need not be the centre of a shape. Minkowski addition applies to nonconvex sets too. It is different from set union: for on the real line, but .
For axis-aligned rectangles in the Euclidean plane, the coordinate intervals add separately:
Every coordinate between and can be split into one coordinate in and another in , and likewise for the vertical coordinate. Thus a rectangle plus a rectangle gives a square of area , although the two input areas total only . The Minkowski sum adds possible displacements, so its area need not be the sum of input areas.
For closed Euclidean disks centred at the origin, the triangle inequality gives . Conversely, if , split any as . Therefore , including the case . Disks of radii and give a disk of radius , with areas . For disks with centres , the resulting centre is . These two examples lead to the root-of-area comparison in the Brunn-Minkowski theorem.
Figure 1.
Minkowski addition of two rectangles and of two closed disks: exact toy shapes, sample displacement arrows, and the square-root-of-area comparison
. Details.
Minkowski addition is commutative and associative because vector addition is. Its identity is the singleton , and . For displacement vectors and , translations and uniform dilations satisfy
where uses scalar multiplication. A Minkowski sum of convex sets is convex: a line segment between and is obtained by adding the corresponding points of the line segments in and . Closure requires care; see sum of two closed sets need not be closed and sum of a compact set and a closed set.
For in a compact Hausdorff space , its quasi-component is the intersection of all clopen sets containing . It is closed and therefore compact. Suppose is a separation of a topological space into two nonempty relatively closed sets, with . The sets are compact and hence closed in . Normality of a compact Hausdorff space gives disjoint open neighborhoods of .
The compact set is disjoint from . For each point of that set choose a clopen containing but not . Finitely many complements cover , so their corresponding intersection is clopen, contains , and is contained in . Now is clopen in , hence clopen in , and contains while missing . This contradicts the definition of . Thus is connected. Any connected set containing lies in every clopen neighborhood of , so the connected component of equals .
For the second assertion, is closed in the ambient Hausdorff space , and is itself compact Hausdorff. Let be a connected component of disjoint from . Choose . By the first assertion is the quasi-component of in . For each choose a clopen subset of containing but not . Compactness of gives a finite intersection of these sets which contains and avoids the whole boundary. Thus . It is closed in , because it is closed in the closed set , and is open in , because it is relatively open in and contained in its interior. It is nonempty and proper, contradicting connectedness of . Hence every connected component of meets its boundary.
Finally suppose a closed subset of the square has the point-separating clopen property specified in the paper. Every nonempty relatively open subset of the square contains a nontrivial line segment: it contains an interior point of the square and a small ball about that point. If such a segment lay in , a clopen subset of separating its endpoints would induce a separation of a topological space of the connected segment. This is impossible. Therefore contains no nonempty relatively open subset of the square. Being closed, it is nowhere dense in the square, and also nowhere dense in .
A convex function satisfies
Thus its value on every line segment lies below the chord joining the endpoint values.
A feasible point is an extreme point solution of a linear program if it cannot be written as a nontrivial convex combination of two distinct feasible points. Explicitly, if
then . Equivalently, lies in no open line segment joining two distinct feasible points. Being an extreme point concerns the feasible region; it does not by itself mean that optimizes the objective function.
By exchanging axes, reversing endpoint order and reflecting coordinate signs where necessary, reduce a general line segment to the first octant:
The vertical case is handled by exchanging axes. In this octant, increasing by one requires increasing by either zero or one. Thus, from the currently plotted pixel the candidates are and .
Use the implicit equation of the line
At a fixed , means that lies below the exact line. The midpoint line decision evaluates , halfway between the two candidate pixel centres. If , the exact line lies below , so choose ; if , choose . At equality either candidate is equally near, but a fixed tie rule is essential. We choose on a tie throughout these solutions:
This chooses the closest vertical-grid pixel centre in each column, with ties rounded upward. Since , the result has one pixel per column and consecutive pixels share an edge or a corner.
Multiply the midpoint line decision by two to remove the fraction. At the current pixel , maintain
At the initial endpoint this is . If is chosen, the next decision midpoint is displaced by and increases by . If is chosen, its displacement is and increases by . Both increments are constant, so the per-pixel work uses only integer arithmetic:
The completed code, using the tie rule of part (b), is:
void midpointLine(int x0, int y0, int x1, int y1)
{
    int dx, dy, incrE, incrNE, d, x, y;
    x = x0; y = y0;
    dx = x1 - x0;
    dy = y1 - y0;
    incrE = 2 * dy;
    incrNE = 2 * (dy - dx);
    d = 2 * dy - dx;
    drawPoint(x, y);

    while (x < x1) {
        if (d < 0) {
            d += incrE;
        } else {
            d += incrNE;
            y++;
        }
        x++;
        drawPoint(x, y);
    }
    return;
}
Thus guard1 is x < x1, and guard2 is d < 0. Multiplication by two is the only multiplication. Signed decision variables are convenient because and incrNE can be negative; this remains an integer arithmetic algorithm. A strictly unsigned hardware representation would need an equivalent biased or separated-sign encoding. As with the printed int skeleton, assume all intermediate values fit the chosen type; integer overflow would invalidate the mathematical decisions.
To verify the geometry, write . The chosen ordinate is
The midpoint line decision selects exactly this nearest integer, rounding halves upward. Its increment between successive columns is zero or one. At and , it gives exactly and , respectively, so both endpoints are included and the line segment has precisely distinct pixels.
Figure 1.
Bresenham pixels for a slope of 3/8, with the upper pixel selected at the midpoint tie
. Details.
For the illustrated endpoints and , the ordinates are . In particular the exact ordinate at is , and the chosen pixel is .
After every proposed pixel has passed part (d), insist on exactly one call in every column of the closed endpoint interval:
void final()
{
    for (int x = x0; x <= x1; x++) {
        if (counter[x] != 1) reject();
    }
    accept();
}
Part (d) already rejected every out-of-range column and every incorrect ordinate. A zero counter now detects an omitted column; a counter greater than one detects a repeated call in that column. Because the residual interval in part (d) allows exactly one integer ordinate in each column, accepted calls in a repeated column must address the same pixel. Conversely, a counter of one in every column forces the complete set of nearest pixels, including both endpoints. Consecutive correct columns differ in ordinate by at most one, which proves that there are no gaps in the resulting thin line segment.
The verifier certifies the final plotted set; it need not require calls to arrive in increasing order. Its final condition is simply
Put and define six closed half-spaces . Their implicit equations and outward normal vectors are:
BoundaryDefining function Outward normal
The six vertices of a polygon traverse the boundary counterclockwise. Each displayed normal vector therefore points to the right of the corresponding directed boundary line segment; it need not be a unit vector. The zero level sets are full straight lines, while the actual boundary retains only the appropriate line segments.
The inward corner at prevents using the set intersection of all six half-spaces: that would incorrectly discard the upper-left part of the seat. Instead take
The last factor permits either or , removing only the upper-right region. Another way to understand the same constructive solid geometry model is as the set union of two convex polygons, obtained by distributing the last set intersection over this set union. Its constructive solid geometry tree has an intersection at the root and a union child for .
Figure 1.
Seat profile, six supporting lines with outward normals, and the right child of the initial bounding box
. Details.
The tight axis-aligned bounding box is . Bisect vertically at , giving a right child . For a scalar implicit function representing the same constructive solid geometry solid, use
With the convention inside, set intersection corresponds to the maximum, and set union to the minimum. These operations encode membership; is not a signed distance function.
Since every is an affine function, its extreme values on occur at corners. Exact real-arithmetic interval arithmetic gives:
FunctionRange on , propagated, propagated
Each leaf range is exact, but combining independent intervals forgets that the expressions share . The final enclosure need not be the exact range of . For example, equality would require both , hence , and , hence on , which is impossible. The enclosure is still sufficient for a reliable three-way decision:
Here the result is unresolved. This is a real mixed box, rather than only a pessimistic test: is strictly inside, whereas is outside. A zero endpoint alone can also mean contact with the boundary, so equality must not be treated as proof of strict interior or strict exterior. In floating-point arithmetic, certified bounds require outward rounding.
Continue splitting unresolved boxes, normally alternating axes or splitting the longest side. Propagate the interval arithmetic results through the constructive solid geometry tree, discard exterior boxes and stop refining strict interior boxes. In sufficiently small boundary boxes, locate crossings of the active implicit equations with box edges and connect them into boundary line segments. Retain corners and resolve ambiguous multiple crossings by further refinement; here every genuine boundary piece is straight, so its supporting implicit equation allows exact intersection rather than a curved approximation. A maximum boundary-box diagonal gives spatial localization at that scale, provided no boundary components are discarded; corner-sign sampling alone provides no such guarantee.
The tight box saves empty-space work, but it is awkward for extracting facets. Entire boundary line segments, notably , and , lie on the initial box boundary, and lies on the first splitting straight line. A sign-change-only method may have no exterior sample on the other side and lose such pieces; exact zeros also persist through refinement. A slightly padded initial axis-aligned bounding box, together with an explicit rule for boundary-coincident pieces, makes the faceting more robust. The tight box is therefore economical for enclosure but not the best unqualified choice for a simple faceting implementation.
Insert the union subtree from part (f) as another child of the original intersection:
Thus the constructive solid geometry tree has one intersection root, four original half-space leaves and two union children. The first union handles the inward corner at ; the second embeds the circular fillet at . The line segments and now end at and start at , with the chosen circular arc between them. All other boundary line segments are retained.
Write , where . For three distinct sites , the left, middle and right firms receive respectively
These follow by counting the two midpoint boundaries, including split ties. Therefore, after two firms occupy , the final entrant compares at , at , and at every available interior site. Omit an unavailable region and retain every maximizing tie. This is the final entrant payoff in a discrete location game.
First suppose opens at the central site . If chooses , the final entrant's best possible payoffs on the left, right and interior are at most , exactly , and at most , respectively. Hence 's unique best response is . The resulting payoff to is , uniquely maximized on that side at . Reflection gives the other optimal choice , followed by . Under either choice, receives only . Any mixture of the tied optimal second-mover choices has the same consequence.
Now let deviate to . If chooses , the unique final best response is , yielding at most . If chooses , the unique final best response is , yielding only two. Both classes will be strictly inferior to an available alternative, independently of how later ties are resolved:
  • If , can choose . The final entrant compares , and , so uniquely chooses . This gives exactly .
  • If , can choose site four after chooses two. All three remaining sites are final-mover best responses; they give payoffs five, four and three. Thus guarantees at least three, exceeding the excluded choices' payoff two.
Accordingly, in every subgame perfect equilibrium continuation after , the second mover must choose a site . This remains true with mixed strategies: every excluded choice pays strictly less than the displayed guaranteed alternative, under every possible continuation tie policy.
For any such , every legal final site gives at least three. If lies left of , then is the middle firm and receives . If lies right of , then is the left firm and receives . Thus the deviation gives at least , against every subgame-perfect continuation, whereas the central opening gives it .
Figure 1.
Final-mover ties and the second mover's guarantee after the first firm deviates on a nine-building street
. Details.
In this original example, a final-mover tie produces the line segment for : its points are expected payoff pairs from a mixed strategy over two final best responses. The second mover can independently secure eight by choosing , so only the segment to the right of that guarantee can support its optimal choice. Mixing over a tied final response cannot make the first mover's payoff fall below three.
A subgame perfect equilibrium must prescribe optimal continuation play even after the first mover's off-path deviation. Since the deviation is strictly profitable under every such prescription, no subgame perfect equilibrium can have open centrally. The argument does not select favourable ties or assume that off-path players cooperate with the deviator.
Parameterize the two line segments by
Put and abbreviate , , , , and . Minimizing the Euclidean distance is equivalent to minimizing the convex quadratic function
over a closed square. For nonzero nonparallel segment directions, . An interior minimum must satisfy
whose unique solution is
Keep it as a candidate only if both parameters lie in .
Every remaining minimum lies on the boundary. Define . The four edge minima are the point-to-segment orthogonal projections
Evaluate at those four pairs and at the admissible interior pair, and return a pair with the smallest value. This solves closest points on two line segments completely: continuity guarantees a minimum, and every interior or boundary location has been tested. Do not independently clamp and : the mixed term couples them. For example, , , and give the line minimizer . Its independently clamped pair has squared distance , whereas the correct edge minimizer has squared distance .
Without general position, explicitly handle these configurations:
  • If either segment has zero length, solve a point-to-segment projection; if both do, return the two points. This avoids division by or .
  • If the directions are parallel, and the interior linear system is singular. The four edge projections still contain a minimum. Overlapping projected parameter intervals can yield a whole family of closest pairs.
  • Collinear segments may overlap, touch, or be disjoint. Overlap gives zero distance with many choices; disjoint intervals give their nearest endpoints.
  • Coplanar nonparallel segments can intersect, including endpoint contacts. The same candidate tests return zero distance if the line-intersection parameters lie in the square. Coincident endpoints and equal candidate distances need no arbitrary division or uniqueness assumption.
In floating-point arithmetic, almost-parallel directions require a condition-aware or higher-precision solve; they must not be declared exactly parallel solely because the computed determinant is small. The returned distance is , and the returned points are obtained by substitution into .
The same relative coordinates give the proximity time of translating line segments as
This is a convex norm-constrained problem, rather than the linear feasibility problem for contact. One can solve it as a small second-order cone problem. If the distance between the initial line segments is at most , the answer is zero; if no feasible point exists, the threshold is never reached.
For an elementary analytic algorithm, consider the nine combinations in which each of is either free, fixed at zero or fixed at one. In each case, minimize the squared distance over the free parameters. Writing for plus the fixed endpoint contributions, and for the columns belonging to free parameters, stationarity is
If the Gram matrix is nonsingular, is affine in time. Retain only the time interval on which its entries lie in . The residual is then , and feasibility reduces to
Intersect its solution interval with and the free-parameter validity interval, and record the first point. Include the four endpoint–endpoint cases, where there are no unfixed segment parameters. Take the earliest valid candidate among all cases. The actual closest pair belongs to one of these faces of the parameter square, so this enumeration cannot miss the first approach.
The complications are the quadratic threshold equation, changes of the active closest-point feature and singular Gram matrices for parallel or degenerate segments. In a singular case, keep the affine family of minimizers and its feasibility bounds, or use the original convex problem; a pseudoinverse answer alone can fall outside the segment even when another minimizer is feasible. Constant-distance cases and tangential threshold contact must also be retained. Merely checking moving endpoints misses approaches between interior points.
Use closest points on two line segments as a small constrained convex optimization problem. Write the two line segments as
and put . Minimize the squared Euclidean distance ; minimizing its square also minimizes the distance. Compute the dot products
For nonzero, nonparallel directions, an interior minimum must satisfy the two derivative equations
Their determinant is , so the stationary candidate is
Retain this candidate only when both parameters lie in the unit interval.
The other possibilities are on the boundary. Define . Minimizing the same quadratic on each of the four edges gives these candidates by orthogonal projection onto a line segment:
Evaluate at every retained candidate and choose the smallest. The resulting are the required closest points. The quadratic is convex because it is the squared norm of an affine map. A minimum in the interior is stationary, and a minimum on the boundary minimizes one of these edge restrictions, so the list is exhaustive. Ties correspond to multiple equally valid answers.
Handle degenerate line segments before dividing: if and , set and ; if and , set and ; if both vanish, use the two endpoints. For exactly parallel directions, . The distance depends on a single linear combination of ; any interior minimizing level line reaches the boundary, so the four edge candidates still include a minimum.
For nearly parallel directions, compare with the scale , and solve the interior least-squares problem using QR decomposition or singular value decomposition if necessary. A small determinant should trigger a stable solve, not arbitrary rejection of a possibly valid interior solution. In particular, do not merely clip both coordinates of the infinite-line solution: the dot product couples the two parameters, and changing one changes the optimum for the other.
For fixed endpoints, the Euler-Lagrange equation is . Since has no explicit dependence on , differentiating gives
Thus , the Beltrami identity.
With , the arc length element and the prescribed speed give the travel-time functional
For the circular road , this is .
For the integrand , the Beltrami identity simplifies to
The candidate has and the required endpoints. To prove it really minimizes the travel time, rather than merely satisfies a first integral, put . Then
This is the Euclidean arc length integrand for the inverted curve , whose endpoints are and . Every connecting curve has length at least their Euclidean distance , by the triangle inequality. Equality is attained by the straight line segment . In polar form it gives , hence the proposed . It stays strictly positive throughout the interval. Consequently
This travel-time minimization with speed proportional to squared radius is globally solved by the inversion: its minimum is strictly less than .
Let the triangles have vertices and . Work initially with nonzero-area triangles. A triangle-triangle intersection algorithm begins with the unnormalized normal vector and the three signed plane evaluations . If all are strictly positive, or all strictly negative, the second triangle lies strictly on one side of the first one's plane, so the triangles are disjoint. Otherwise compute and and apply the symmetric rejection test. Strict inequalities are important: contact on a vertex or edge counts as intersection.
If the planes are not parallel, put . Each triangle meets the other one's plane in an empty set, a point or a line segment. Its endpoints are obtained from zero-valued vertices and the edges whose endpoint plane evaluations have opposite signs. For example, an edge contributes
All these points lie on the common line of the two planes. Choose a coordinate for which and form the coordinate intervals , of the two slices. This coordinate is one-to-one along the common line, so the exact final test is
Only that coordinate of each slice endpoint needs to be evaluated; no full three-dimensional line parameterization is necessary.
Parallel planes which have survived the strict plane tests are coplanar. Drop the coordinate corresponding to the largest component of and test the two projected planar triangles. For each edge of either projected triangle, project both vertex sets onto the perpendicular direction. A strictly disjoint pair of projection intervals certifies separation. If none of the six edge directions separates them, the planar convex sets overlap: a separating line for two disjoint convex polygons can be chosen parallel to an edge of one of them. This includes containment and boundary contact.
A zero normal vector signifies a degenerate triangle; reduce its convex hull to a point or its extreme line segment and use point containment or segment intersection instead. For floating-point input, reliable sign predicates and scale-aware error bounds are preferable to treating a tiny signed distance as an arbitrary exact zero. Plane rejection followed by interval overlap, with a planar test for coplanar input, determines all nondegenerate cases.
Use the limit subdivision surface and limit subdivision curve, rather than treating their initial control meshes as the reflecting geometry. Build adaptive refinement hierarchies for both. Each surface cell supplies a limit-position evaluator, local tangent vectors and a normal vector; each curve interval supplies a limit-position evaluator and tangent. Regular regions may be evaluated as local splines, while extraordinary neighborhoods require the evaluation machinery of the specified subdivision rules. A piecewise smooth surface is handled patch by patch, with explicit boundary or crease joins.
A useful initial polygonal construction refines the surface to small triangles and the source curve to small line segments. For a candidate mirror triangle in a plane , reflect the eye across that plane:
For a source edge , a physical reflection point is the plane intersection of the line :
Keep only , , points inside the mirror triangle, and eye/source points on the appropriate reflecting side. Unfolding the reflected path across the mirror proves the specular reflection condition. As moves along a straight edge, lies on the intersection of the mirror plane with the plane through , so the retained locus is a straight segment, a point or the empty set. Plane and triangle clipping computes its endpoints. If these defining points are collinear, or a denominator vanishes, use the corresponding limiting geometric case rather than a generic plane formula. A bounding volume hierarchy accelerates candidate search where geometric bounds exclude pairs; refined facet segments provide seeds and approximate connectivity.
To obtain the reflection curve of the actual limits, correct these seeds. In a local surface chart write , and on a source interval write . Set
The exact limit reflection locus is together with the front-side conditions. For a two-sided mirror, orient locally so that and require ; for a one-sided mirror use its prescribed orientation and discard the wrong side. At grazing incidence this orientation condition ceases to be strict and the case needs separate handling. Unlike the eye-facing assumption in the parametric question, no global orientation condition is supplied here.
Apply a continuation method: at a rank-two root of , predict in a nullspace tangent direction and correct by the Newton method on a transverse section. Map corrected parameters to , crossing patch and curve-interval boundaries through their hierarchy adjacency. Trace all branches, recognizing closed components and endpoints. Supplement facet seeds by recursive searches of the surface-cell/source-interval product, with interval arithmetic or other certified enclosures of ; otherwise a small loop absent from the initial polygonal approximation could be missed. Split singular neighborhoods where the Jacobian matrix loses rank, and test the open source-to-mirror and mirror-to-eye segments for occlusion when selecting actually visible components.
Allocate a geometric error budget to limit evaluation, root correction and polygonal chords. For example, require combined position-evaluation and corrected-root error at most and, on every regular arc, require the chord error bound . Use subdivision position and normal bounds for evaluations: a tiny position error alone is insufficient, since a wrong normal vector changes the reflected ray. Away from singularities an inverse transverse Jacobian matrix bound converts reflection residual into parameter error and a bound on converts this to space error. Refine until these bounds hold, or use validated enclosures of entire arcs and their distances to the chords.
Near a caustic the inverse bound can become large, so the hierarchy must refine more strongly or isolate the singular branch geometry. Mesh flatness alone does not certify a reflection tolerance. With regular convergent evaluators and finite resolvable components, the resulting ordered vertices and chords satisfy
The problem supplies no particular subdivision rules or smoothness guarantees, so this construction specifies what their evaluators and bounds must provide; an arbitrary nonsmooth or degenerate limit need not have an ordinary finite reflection curve. Refine for seeds, enforce reflection on the actual limit geometry, then refine the traced arcs to the required spatial tolerance.
Restrict to an arbitrary line segment by defining for . The chain rule and the assumed positive semidefinite matrix condition on the Hessian matrix give
Thus is non-decreasing. For , integrating on the two subintervals gives
Rearranging, and including the immediate endpoint cases, yields
This is precisely the definition of a convex function.
Fix a number of colors. For a two-point set whose points are distance apart, take the vertices of a regular simplex with vertices and side length . The pigeonhole principle gives two vertices of one color, and they form the required congruent copy. Thus every two-point set, equivalently every line segment, is a Euclidean Ramsey set.
For an equilateral triangle of side length , take a regular simplex with vertices and side length . The pigeonhole principle gives three vertices of one color, and every three vertices of a regular simplex form an equilateral triangle. Hence every equilateral triangle is Euclidean Ramsey.
To prove the product theorem for Euclidean Ramsey sets, let be a finite Ramsey witness for under colors. There are at most possible color patterns on . Choose a finite Ramsey witness for under that many colors. Given a -coloring of , color each by the complete pattern
There is a copy on which this pattern is constant. The common pattern on contains a monochromatic copy . Every point of then has the same original color, and the orthogonal product is congruent to .
A rectangle is the Cartesian product of two line segments, so it is Euclidean Ramsey. Three suitable vertices of a rectangle form a right triangle; any subset of a monochromatic set is monochromatic. Thus every right triangle is Euclidean Ramsey.
It remains to show that the collinear set behaves differently. In every , use the finite coloring
A congruent copy has the form with for the Euclidean norm. The parallelogram law gives
Put , , and . The errors introduced by the three floor functions show that
If all three points had one color, the integer in the middle would be divisible by ten, which is impossible. This proves the three-term unit arithmetic progression is not Euclidean Ramsey assertion.
False. Join, at one common endpoint , a line segment of length for every positive integer , and use the intrinsic path metric. This is a real tree. It is totally bounded, because outside the first finitely many arms every point lies arbitrarily close to , and it is complete; hence it is compact. Removing leaves one connected component for every arm, so has countably infinite multiplicity of a point in a real tree.