9 Convex hull growth
Given an areaThreshold and a nontrivial convex polygon of area below the threshold, there is a limited set of points such that if we take the hull of such a point with the polygon, the area of resulting polygon is less than the area threshhold. In fact, this set of points
Given a convex polygon \(P\) and an area threshold \(A_*\), and an ordered pair of vertices \(V_i, V_j\) (not necessarily adjacent) of \(P\), the growable distance to the left of the directed line \(V_i \to V_j\) is a distance \(d\) such that the sum of the area of \(P\) to the right of the line \(V_i \to V_j\) and the area of the triangle formed by \(V_i, V_j\) and a point at distance \(d\) to the left of the line is at least \(A_*\) (and is within a tolerance of the exact such distance).
The growth half space to the left of a pair of vertices \(V_i, V_j\) of a convex polygon \(P\) and tolerance \(\tau \) is the half-space to the left of the line parallel to \(V_i \to V_j\) at distance \(d\) from it, where \(d\) is the growable distance to the left of the pair.
If we add a point outside the growth half-space to the left of a pair of vertices \(V_i, V_j\) of a convex polygon \(P\) and tolerance \(\tau \), then the area of the convex hull of \(P\) and that point is greater than \(A_*\).
The growth half-space intersection of a convex polygon \(P\) and tolerance \(\tau \) is the intersection of the growth half-spaces to the left of all pairs of vertices of \(P\) and tolerance \(\tau \).
If we add a point outside the growth half-space intersection of a convex polygon \(P\) and tolerance \(\tau \), then the area of the convex hull of \(P\) and that point is greater than \(A_*\).
9.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.