The test is a program, not a rank

The question is one bit: does this set of contacts leave the part anything to do. Everything else in the field depends on getting it right, and there are three ways to get it, none of which resembles the others.

Why not a rank #

The instinct after twenty fields is to take the rank of the contact rows, and it is worth being precise about why that is not merely insufficient but the wrong kind of quantity.

A rank is invariant under multiplying any row by $-1$. The cone $\{t : At \ge 0\}$ is not: negating one row replaces one half-space by its complement, which can turn a trivial cone into a large one. So no function of the row space can decide this, and the rank is a function of the row space.

The evidence is in the ledger. Four contacts placed pinwheel and four placed alternately are the same four edges of the same square at the same distances along, and their matrices have identical singular values — 1.375, 1.375, 0.468 in both cases — because the two matrices differ by the sign of two rows. One arrangement holds and the other turns.

What the rank is good for is a guard, and the third route below needs one.

Route one: enumerate the escape #

The most direct route answers a stronger question than the one asked: not merely is anything left but what.

The cone $\{t : At \ge 0\}$ in the plane lives in $\mathbb{R}^3$. If the rows span all three dimensions, the cone is pointed, and every extreme ray of a pointed polyhedral cone lies on at least $d - 1 = 2$ independent facets. So every extreme ray is parallel to $a_i \times a_j$ for some pair of rows. Take every pair, take the cross product both ways round, and keep the ones that satisfy every row.

That is exact. There is no search, no starting guess and no tolerance except the one deciding whether a dot product is zero — and the margins there are enormous, since a ray on two facets has two dot products at $3 \times 10^{-16}$ of the row scale while the smallest genuinely escaping direction clears zero by $4 \times 10^{-2}$. Ten orders of room either side.

It costs $O(N^2)$ on a field whose largest arrangement has twelve contacts, which is nothing, and it hands back the escape directions themselves — which is what makes the region pictures in this family possible.

And it has one trap, which the field walks into on two of seven rows. If the rows do not span three dimensions, the cone contains a whole line, has no extreme rays at all, and returning an empty list would say held about a part that is free to move both ways along it. So the enumeration reports the rank separately and a rank below three is an answer rather than an edge case. It is what a disc does and what an ellipse in its own bounding box does, and neither of them looks like a degenerate drawing.

Route two: where the origin sits in the hull #

The second route computes a number rather than a set, and the number is the one this field quotes.

A set of rows positively spans the space exactly when the origin is in the interior of the convex hull of those rows taken as unit vectors. So the natural measure of how well an arrangement holds is how far the origin is from the nearest face of that hull: a distance, which falls continuously to nought as an arrangement approaches one that lets go.

It is computed by enumeration too, and by the same argument one dimension up. A facet of the hull is spanned by $d$ of the points; its plane is the one through them, whose normal is the null vector of their $d-1$ difference vectors; and those $d$ points form a facet exactly when every other point is on one side of that plane. So the whole hull is $\binom{N}{d}$ small determinants — 220 for twelve contacts in the plane, 84 for nine in space — and the radius is the smallest distance from the origin to a facet plane.

The margins in the ledger are 0.211 for the square on four and 0.091 for the hexagon on five, and every arrangement that does not hold comes back at exactly nought — not at $10^{-14}$, because a facet plane through the origin gives an offset of zero by construction rather than by rounding.

Route three: a linear program, and where it went wrong #

The third route asks the question as a program, and it is the only one of the three that works in six dimensions without enumerating a hull.

A hold means there is a $\lambda \ge 0$ with $\sum \lambda_i \hat a_i = 0$ and every $\lambda_i$ strictly positive. Write that as an optimisation:

$$\text{maximise } \delta \quad\text{subject to}\quad \sum_i \lambda_i \hat a_i = 0, \;\; \sum_i \lambda_i = 1, \;\; \lambda_i \ge \delta \ge 0 .$$

The optimum is positive exactly when the arrangement holds, and it is a share: the largest fraction of the total that every single contact can be made to carry.

And on its own it is wrong. The case that shows it is the one part in this field that cannot be held at all.

A disc’s rows all have a zero moment entry, so they lie in a plane through the origin — and inside that plane the origin is comfortably surrounded, so $\sum \lambda_i \hat a_i = 0$ with all eight weights equal is not merely feasible but optimal. The first version of this returned a share of 0.125 for a disc on eight contacts and 0.25 for an ellipse in its own box, which are the two arrangements in the ledger that hold nothing.

Positively spanning a subspace is not positively spanning the space, and nothing in the program’s answer distinguishes the two. The repair is to check the rank first and return nought when it is short — so the rank, useless as a test, is exactly right as a guard.

That defect is worth carrying for its shape rather than its size. It produced a plausible, non-zero, well-conditioned number for an arrangement whose answer is a flat no, on the two rows a reader is most likely to check by intuition, and it would have propagated into every figure and every caption downstream. What caught it was running all three routes and requiring them to agree, which is the only reason there are three.

The share and the distance are different numbers #

Having two quantities that both say how much is an invitation to conflate them, and they do not measure the same thing.

The program’s share is at most $1/N$ and reaches it whenever a symmetric combination cancels. For a square held by four contacts that is true at every placement that holds at all: the share is 0.25 at a placement with room to spare and 0.25 at one a hair away from letting go, and then nought at the placement itself. A quantity that is flat and then discontinuous is a decision wearing a number’s clothes.

The hull radius does what a margin has to do. It falls smoothly: as the four contacts on the square move toward the midpoints of their edges the moments shrink, the four rows flatten into the plane $\omega = 0$, and the radius goes to nought continuously.

So the field quotes the radius as the margin and keeps the program because it is an independent route to the decision and the only one that scales into six dimensions cheaply. Both are printed and the agreement between them is asserted on every arrangement the field builds.

Where the numbers actually come from #

It is worth putting the three routes’ answers next to each other on one arrangement, because the reason they are kept apart is that they disagree about what they are measuring while agreeing about the answer.

Take the hexagon on five contacts. The enumeration returns no extreme rays and a rank of three, so nothing escapes. The hull returns a radius of 0.0914 — the origin’s clearance inside a hull of five unit vectors in three dimensions. The program returns a share of 0.1118, which is 0.56 of the even share $1/5$, and it returns the weights that achieve it.

Three numbers, one verdict, and none of the three is convertible into either of the others. The radius does not determine the share and the share does not determine the radius; what they share is a sign.

And that is the useful discipline rather than a curiosity. A quantity in this field is reported with the routine that produced it attached, because margin has meant two different things in two lines of the same table before now, and a reader comparing 0.0914 against 0.1118 across arrangements would be comparing nothing.

Three routes is not a ritual #

This site has run two routes to a number since the foundation and the habit is stated as a habit. It is worth saying why this rung has three rather than two, since a third route is a third thing to maintain.

The three answer different questions and fail in different ways. The enumeration is exact and reports what escapes, and it fails silently when the rank is short. The hull is exact and reports how much, and it is expensive in high dimensions. The program is cheap in any dimension and reports a decision, and it fails on rank deficiency in the way just described.

Two of the three share a failure mode — rank deficiency — and the two that do are the two that would have been chosen if only two were wanted. Which is exactly the situation three routes exist to catch: agreement between two routes with a common blind spot is worth much less than it looks.

The simplex, and the rule that is not a detail #

A word about the program itself, because a linear program is a new instrument on this site and it has one requirement that looks like a footnote and is not.

The simplex here is two-phase rather than a big-M. A big-M formulation is one pass and it prices an artificial variable against a number somebody has to choose; too small and an infeasible program comes back with an answer, too large and the real objective disappears into rounding. The two-phase form has no such number in it.

And the pivot rule is Bland’s throughout. Every program written from a set of contacts is degenerate, because the normals repeat: a part with two contacts on one face contributes two identical rows, and a box’s six faces give six normals however many contacts there are. A degenerate vertex can send the usual steepest-entering rule around a cycle of bases for ever, returning the same objective value at every step and never terminating. Bland’s rule — lowest index that prices favourably, ties in the ratio test broken by lowest basic index — is slower and provably cannot cycle.

The iteration cap in the code is therefore a bug detector rather than a stopping rule. Reaching it means the tableau is not what the routine thinks it is, and it throws rather than returning whatever it has.

What the program answers that nothing else could #

It is worth naming what the simplex buys beyond a second opinion, because it is the reason the instrument is in the shared kit rather than in this site’s own library.

Every solver this fleet has had — Newton, bisection, Gauss, damped least squares — answers where is the point that satisfies these equations. A linear program answers a different question: is there any point at all that satisfies these inequalities, and if so which one is furthest in a stated direction. There was no way to ask it.

The workaround a site reaches for without one is to sample: take a few thousand directions, keep the best, quote the number. That returns an answer for a program that has none, quotes an optimum that is whatever the sampling happened to find, and gets worse as the dimension rises — which is precisely where the question stops being answerable by looking. A simplex either returns a vertex, or reports the program unbounded, or reports it infeasible, and those are three different facts.

Three of the field’s rungs depend on that distinction. Whether a part goes in at all is a feasibility question. How large a clearance’s pose set is is an unboundedness question, and the answer unbounded is the interesting one. And closing three jaws on a bar until they all touch is a minimisation whose optimum has every constraint tight, which is the statement that all three jaws touch.

The cost, which is small and worth saying #

None of this is expensive, and it is worth putting numbers on because every figure in the field recomputes the whole of it rather than quoting a stored answer.

The enumeration is $\binom{N}{2}$ cross products and $N$ dot products each — for twelve contacts, 66 candidates and 792 dot products. The hull is $\binom{N}{3}$ tiny singular value decompositions — 220 of them on a $2 \times 3$ matrix. The program is a simplex on a tableau with $2d + 1 + N$ rows, which for a planar arrangement is under a dozen pivots.

The census is where it adds up: twenty thousand arrangements, each one a hull enumeration in six dimensions at $\binom{9}{6} = 84$ facets. That is the only computation in the field that takes a noticeable moment, and it is the only one whose answer could not have been guessed.

For comparison, the algebra field’s homotopy continuation tracks hundreds of paths through a polynomial system to answer a related question — how many configurations a mechanism has — and it takes orders of magnitude longer. The reason this field’s central question is cheap is that everything in it is linear. There is no root finding anywhere: a contact is a linear inequality, a hold is a statement about a polyhedral cone, and the whole subject is convex.

That is unusual for this site and worth flagging as a property of the field rather than of the code. It is also why the field’s hard rungs are the ones that leave convexity behind — second order, and caging.

What still cannot be asked #

The three routes settle whether a part is held at one configuration and nothing else, and it is worth marking the boundary while the instruments are fresh.

They say nothing about whether the part can get from here to there, which is a global question with a different answer. They say nothing about what happens at second order, where a rank-deficient arrangement can behave in opposite ways. And they say nothing about how a part fails to be held beyond naming the directions — a part with a large escape cone and a part with a sliver of one are both simply not held, and the margin is nought for both.

That last one is a genuine limitation rather than an omission. There is no continuous measure of how badly an arrangement fails, because failure is a set being non-empty and non-emptiness has no size. The margin measures the distance to failure from the inside and stops at the boundary, and the field has no quantity that continues past it.

Three routes to one yes-or-no is worth defending as an arrangement rather than as a ritual, and the defence is in what each of them can fail at. The enumeration fails by missing an extreme ray, which is a combinatorial error and shows up as a cone reported smaller than it is. The hull test fails by a degeneracy in the convex hull, which shows up on arrangements with coincident or opposed rows. The program fails by a formulation error — the normalisation, which is what caught the disc — and shows up on parts with a symmetry. Three failure modes with almost nothing in common, and the arrangement’s value is exactly that: an agreement between three routes is worth what their failure modes are worth being different. Two routes with the same weakness agree on every case where both are wrong, which is the arrangement that looks like verification and is not. That is why the third route was worth writing after two already agreed, and why the disc — the case that broke it — was the one that mattered.