8 Working set algorithm
The computational approach maintains a list of convex polygons, the working set, with the invariant that every Moser set of area below the threshold contains (a rigid motion of) at least one polygon in the list.
A working set is a list of convex polygons. Intended invariants:
every polygon in the list contains a copy of the initial worm (Definition 28) under some direct isometry;
every Moser set of area strictly less than \(A_*\) contains a copy of some polygon in the list under some direct isometry.
Invariant 1 is currently a convention maintained by construction; Invariant 2 is the core correctness statement the algorithm preserves.
The initial working set contains exactly the initial worm.
The minimum area in a working set is the minimum of the shoelace areas of its polygons (taken as \(0\) on the empty set).
8.1 Pruning operations
Remove every polygon whose area strictly exceeds \(A_*\). This preserves Invariant 2 because any Moser set of area below \(A_*\) cannot have a polygon of strictly larger area as a subset.
If a working set satisfies Invariant 2 of Definition 37, so does the result of big set removal.
Remove every polygon \(p\) in the list for which some distinct polygon \(q\) in the list is a subset of \(p\). The smaller \(q\) already witnesses Invariant 2 whenever \(p\) does.
If a working set satisfies Invariant 2, so does the result of superset removal.
Given an additional worm presented as a convex hull, for each polygon \(p\) in the current working set and for each isometry \(\varphi \) in the discretisation, form the convex hull of \(p\) together with the image under \(\varphi \) of the shrunk hull (to absorb discretisation error). The new working set collects all such unions. This step encodes the requirement that a Moser set must contain this worm in some pose.
If the isometry discretisation is fine enough relative to the shrink amount, then adding a worm preserves Invariant 2 of Definition 37.
cleanup is the composition of big-set removal and superset removal. addWormAndCleanup adds a worm and then cleans up.