Three arcs, cut in the right places

A swept-region interference test sweeps each part of a machine over its whole drive and asks whether the two regions share ground. Against a fixed obstacle that question is exact. Between two moving parts it can raise a false alarm: the regions overlap and the parts never meet found Chebyshev’s two arms sharing 4.66 square units of ground though they never come within 0.38 of each other, because one passes over the shared patch early in the drive and the other late.

Four arcs and the false alarm is gone took two pairs of parts from the classical straight-line linkages, the crossing arms of Chebyshev’s approximate one and a long arm and rhombus bar from Peaucellier’s exact cell. It cut the drive into equal arcs, swept each part over each arc on its own, and compared regions only arc against the same arc. Four equal arcs cleared Chebyshev’s arms and eight cleared a pair from Peaucellier’s cell. That essay ended by noticing that equal arcs spend their cuts without regard to the motion. A flagged cell belongs to a particular arc, so the cuts could go where the flags are. It proposed cutting only the arcs that still flag something, and asked whether three arcs might be enough on Chebyshev’s arms if the cuts fell where the two visits separate.

They are, and the right cuts do not need to be searched for. Each shared cell of ground asks for one cut somewhere in a stretch of the drive, and the fewest cuts that answer every cell can be read off a single sweep and proved to be the fewest.

What a partition has to do #

The arc-wise test flags a cell of the grid when some arc holds a configuration at which one part covers it and a configuration at which the other part covers it. So a partition of the drive clears a pair exactly when, for every cell both parts ever cover, no arc holds a visit by each. Put another way: between every visit by one part and every visit by the other, there must be a cut.

That condition simplifies once the visits are looked at. For each shared cell, list the configurations at which each part covers it, in order of drive angle. A cut is needed only between neighbouring visits by different parts, because any other pair of opposite visits has such a neighbouring pair inside it, and a cut that separates the inner pair separates the outer one too.

The measurement then finds something stronger. On both pairs every shared cell is visited by each part in one unbroken stretch of the drive, and the two stretches do not overlap. Chebyshev’s arms share 5,510 cells of the grid and give 5,510 intervals, Peaucellier’s long arm and rhombus bar share 7,496 and give 7,496. Each cell’s interval runs from the end of one part’s stretch to the start of the other’s, and the partition clears the pair exactly when every interval has a cut inside it.

This one-stretch structure is a measured fact about these two pairs, not a theorem. A part that swung back over a cell later in its drive would visit it in two stretches, and the cell would give two or three intervals instead of one. Nothing below would change except the count of intervals, since the rule only ever asks for a cut between neighbouring opposite visits. What the structure does say is that on these machines each crossing of shared ground is a single event in the drive, with one part arriving after the other has left.

A cell visited by both parts at the same configuration would give an interval of length nought, which no cut can fall inside. That is not a false alarm. It is a collision, found by the same sweep: the arms made 0.5 wide, wide enough to overlap by 0.535 at their closest, give 6,133 such zero-length intervals. No partition clears them, at any number of arcs, and none may if the test is to be sound.

The fewest cuts, and why no fewer will do #

Placing the fewest points so that every one of a set of intervals contains at least one is a classical problem with a greedy answer. Take the intervals in order of where they end. Put a cut just inside the end of the first one. Skip every interval that cut already falls inside, and put the next cut just inside the end of the first interval it misses. Repeat to the end of the drive.

The greedy rule also proves itself. The intervals at which it placed its cuts do not overlap one another: each begins after the previous cut, or it would have been skipped. Disjoint intervals need a cut each, so no partition can manage with fewer cuts than the rule used. The thick intervals in the figure are those witnesses.

On Chebyshev’s arms the rule places two cuts, at 1.072 and 1.428 radians of a drive that runs from 0.712 to 1.702. Three arcs, of 0.360, 0.356 and 0.274 radians, clear the pair. The two witnesses run from 0.712 to 1.073 and from 1.073 to 1.429, and they do not overlap, so two cuts is the least any partition can use. Two of the three arcs are longer than the 0.306 radians that the earlier essay found every equal arc must stay under, which is the whole saving: a placed arc may be long wherever no crossing needs it to be short. Handed back to the grid test as a partition, the three arcs flag nothing. Remove either cut and the two arcs left flag 1.25 or 1.67 square units.

That answers the earlier essay’s question exactly as it was put: three arcs, with boundaries where the two visits separate, and the right partition read off the sweep rather than searched for.

Where the cuts fall on the machine #

The two cuts divide the shared ground into two patches. The first cut, at 1.072 radians, separates 2.98 square units; the second, at 1.428, separates the remaining 1.67. The patches are where two bars that have to cross cross, in the middle of the drawing, well away from the arms’ closest approach at the start of the drive. The earlier essay found the same thing about the false alarm as a whole: the ground that causes it has nothing to do with where the parts come near each other.

Read on the machine, each cut is a moment in the drive that falls between the arms’ two passes over every cell of its patch. Every cell in the first patch has one arm’s pass before 1.072 radians and the other’s after it. Every cell in the second has both passes on the same side of 1.072 and on opposite sides of 1.428. No single moment lies between the two passes of every cell, because the two witnesses do not overlap, and two moments do. That is all the drive’s timing has to say, and the intervals say it cell by cell.

Peaucellier’s pair needs five, and one of them is for a sliver #

Peaucellier’s long arm and rhombus bar drive over 3.15 radians and share nearly ten square units, and they are the harder case.

The greedy rule places four cuts, at −1.150, −0.325, 0.632 and 1.474 radians, and the four witnesses do not overlap, so five arcs is the least. The arcs are far from equal: 0.426, 0.825, 0.957, 0.842 and 0.101 radians. The first witness, from −1.575 to −1.145, is 0.430 radians long, the shortest separation between two visits anywhere in the drive. It is the number the earlier essay used to bound the equal arcs needed: π over 0.430 is 7.3, so eight. With the cuts placed, that shortest interval costs one cut, like any other.

The four patches are very unequal. The first three cuts separate 3.55, 4.40 and 1.98 square units. The fourth separates 0.04, a sliver at the tip of the shared ground that the long arm and the rhombus bar both reach near the end of the drive, 0.834 radians apart. Without that cut the other three leave 29 cells flagged, and the last arc, only a tenth of a radian long, exists for them. The grid’s cells are 0.028 by 0.048 here, so the sliver is 29 cells of ground, not an artefact of a single one. Whether a finer grid would keep it, merge it or lose it was not measured.

The earlier essay also found that four equal arcs clear this pair if the boundaries are moved half an arc along. On a drive that stops at both ends, as this one does, that placement cuts the first and last arcs in half, so it is five arcs in all. It is one of the partitions the stabbing count allows, found there by luck and here by construction.

Three ways to cut, and what each costs #

The adaptive rule the earlier essay proposed, halving every arc that still flags something and leaving the rest, lands between the other two. On Chebyshev’s arms it starts with the whole drive, halves it, halves both halves because both still flag, and stops at four arcs. That is no better than equal arcs, because the halving points are the equal-arc boundaries and neither of the first two falls where a single cut would do both jobs. On Peaucellier’s pair it halves to two, then to four, then halves the one arc that still flags 178 cells, and stops at five. There it matches the least, because the equal quarter points happen to fall inside three of the four witnesses.

The cost is where they separate. A region test’s expensive step is rasterising each part at each sampled configuration, 360 frames per part here. Equal arcs rasterise each frame once, into its arc’s grid, for each number of arcs tried. The fewest cuts need the same single pass, provided each frame’s cells are kept rather than merged straight into a region. The intervals are read off the kept cells, and the cuts off the intervals. Halving re-sweeps every flagged arc’s frames at every round: 1,080 frames on Chebyshev’s arms and 1,440 on Peaucellier’s pair, three and four times the single pass. The certificate from the earlier essay needs no grid at all and asks for twelve and twenty-four equal arcs.

So the fewest cuts are the cheapest partition as well as the smallest. What they need that the others do not is memory: a list of cells per frame instead of one grid per arc. On a 200-cell grid that is at most a few hundred cells for each of 360 frames, less than the grids the equal arcs keep.

A stabbing number, not a separation #

The earlier essay found a third route to its equal-arc counts. It measured the shortest separation in drive angle between two visits to any shared cell, 0.306 radians on Chebyshev’s arms and 0.430 on Peaucellier’s pair. Arcs shorter than that cannot hold both visits to any cell, so the drive’s length over that separation, rounded up, is enough equal arcs: four and eight, the numbers the grid found.

That quotient is the right number for equal arcs, and the wrong one once the cuts can move. A separation is the length of the shortest interval, and equal arcs have to be shorter than it everywhere because they do not know where it is. Placed cuts are limited by something else, how many of the intervals are disjoint. On Chebyshev’s arms the shortest interval is 0.306 radians long, but every interval contains one of two points, so two cuts do. On Peaucellier’s pair the shortest interval is one of four disjoint witnesses, and it costs one cut, no more.

The distinction is between a length and a count, and it matters for what a designer can conclude from one sweep. The separation says how finely to cut when the cuts are spaced blind. The stabbing number says how many cuts the pair needs at all and where they go. That is closer to a statement about the machine: how many distinct times in the drive the two parts take turns over the same ground.

What the grid and the samples still decide #

Two instruments stand between the intervals and the machine, and both are the earlier essays’ instruments, unchanged. The grid is 200 cells on a side over the pair’s whole sweep, and the room a machine sweeps calibrated its areas against a shape with a closed form. The drive is sampled at 360 configurations, and a sweep that missed nothing showed that a sampled check can pass a collision that falls between two samples.

The placed cuts inherit both limits and add nothing to them. A cut falls halfway between two sampled configurations, so it cannot land on a sample and blur which arc a visit belongs to. An interval shorter than one sample spacing would still be stabbed, since the rule puts its cut half a spacing inside the interval’s end. The worry that remains is the one that was always there: two visits within a single sample spacing of each other might be a collision the samples straddle. The earlier essay’s certificate, the least gap in an arc less the fastest point’s travel across it, is the tool for that, and it applies to placed arcs exactly as to equal ones.

What the placed cuts leave open #

One driven input. The drive here is an interval of one angle, and the intervals between visits are intervals of it. A machine with two inputs has a configuration surface, and the question becomes how few curves on it separate every pair of visits, which is a harder problem than stabbing intervals and not attempted.

More than two parts. Every pair of parts in an assembly has its own intervals. The fewest cuts for the whole assembly stab the union of every pair’s intervals, and the same greedy rule applies. It was run here on one pair at a time. An assembly of many parts might need many more cuts than any one pair, or nearly the same few if the machine’s crossings happen at a few shared moments.

The grid’s resolution. A shared cell is a cell of a 200-by-200 grid, and a visit is a sampled configuration. The sliver that costs Peaucellier’s pair its fifth arc is about thirty cells, and its reality at a finer grid is not established. The soundness of the test does not depend on it, since the refusal comes from zero-length intervals and those are collisions at any resolution.

Still open: cuts shared across an assembly #

The cuts here were placed for one pair of parts at a time. A real clearance check covers every pair of an assembly, and each pair’s intervals sit on the same drive. Free space comes in pieces and a pin is not a point both found that a machine’s clearance problems are local in the drive, which suggests the crossings of different pairs may cluster at a few moments.

The distinct argument there would be the fewest cuts for a whole machine: the union of every pair’s intervals, stabbed by one greedy pass, on Peaucellier’s full cell with its seven links. The measurement would be how many cuts the whole cell needs against the most any single pair needs, and against the sum. If it is close to the single-pair maximum, a machine takes turns over shared ground at a few moments and one partition serves every pair. If it is close to the sum, each pair crosses on its own schedule, and an assembly-wide region test costs a partition per pair after all.