Skip to content

Coverage audit — algorithm derivations (frahan_algorithm_derivations.tex)

Goal: confirm nothing is left out. Method: enumerate every distinct [Algorithm("...")] title in frahan-stonepack/src (249 distinct, from 280 attributes), then assign each to one of: COVERED (a section of the .tex), GAP (real math that was missing — now being added), or NO-DERIVATION (format I/O, parsing, dispatch, UI, or a trivial numeric utility — no theorem to state).

A. COVERED by existing sections (§1–§19)

  • §1 kriging / §3 clip / §4 hull: Fracture-bounded slabs by height-field stitch (94), GPR-to-bedrock deepest-reflector + IDW (102), GPR reflector drape (100), Descriptive stats (partly → see GAP Tukey).
  • §2,§6 2D nesting: Exact NFP-BLF (85/86/87), NFP construction / orbital boundary slide (158/159/160/154), No-fit/inner-fit via Minkowski (160), Clipper2 Minkowski + Boolean (49), Bottom-left (29/30), Contact-adaptive rotations + holes-first (61), NFP-assisted irregular nesting (155), Irregular-shape / Nesting tutorials (125/157), Polygon vertex cleanup (188), Boundary-loop extraction signed-area (32).
  • §7 3D packing: 24-orientation SO(3) + greedy AABB (1), DLBF 3D / mixed (76/77), Chehrazad2025DLBF (48), Heightmap-greedy / mesh heightmap (115/116/145), Full 3D rotation grid (97), Greedy FFD 3D bin-pack (109 → also GAP bound), Tree-packing irregular containers / Park2024TreePack (227/177), Bounding-extents containment + max-scale (37), OBB containment + best-fit / yield-ratio (161/162), Best-fit rubble (22), Mesh-containment box filter (146).
  • §8 guillotine + BCSdbBV: BCSdbBV cost (16), Jalalian BCSdbBV (126), Axis-parallel kerf slab sub-div (15), Orthogonal-grid slab decomposition (167), Tree-forest guillotine pack (226), Per-cell AABB candidate (181).
  • §9 masonry equilibrium: Rigid-Block Equilibrium QP (203), Convex QP managed solver (62), Coulomb friction cone (67), COM-over-support / gate / limit-state (43/44/138), Heyman 1966 limit-state (118), Ashlar coursed / running-bond / staggered (12/205/206/207), Cyclopean Cannibalism (74/75), 3D / polygonal masonry install sequence (3/189 → topo order GAP), Support-DAG install order (221 → GAP topo-sort).
  • §10 decomposition: CoACD (52/53), CGAL PMP corefinement / mesh-mesh CSG / mesh corefinement boolean (42/88/143/65), Convex polygon partition (63), Convex polyhedron half-space clipping / half-space intersection (64/113), 3D Alpha Shapes (2), Constrained Delaunay tetrahedralisation / Geogram tet (57/107), Density-watershed (78), CGAL/Geogram mesh repair + hole filling (41/105/106/149/144/148), Geogram CVT backend (104), Min-volume mesh trim via CGAL boolean (150), Triangle-AABB BVH pruning (232 → note).
  • §11 edge-matching: Absolute orientation Horn 1987 / Horn QAO (5/50), Constrained ICP 2D/3D (58/59/36), Coarse-to-fine angular search (51), Beam-search assembly (20), Agglomerative pair-graph / smallest-first (10/110), Bipartite assignment / Hungarian / Kuhn1955 (24/119/135), Block/Adaptive Pair Match 3D (25/7), Boundary-rail affinity (34/35), Bidirectional rail walker (23), Segment hash index (213), Tomczak2023 / PolytopeSolutions / MatchMeshTransformation ref (225/190), Fragment/shape descriptor (95/218/38/141/cf).
  • §12 reconstruction: Screened Poisson (210 → note: screened variant), Advancing-front (9), Barycentric 2D-to-3D (19), Conformal chart-scale (55), Centroidal Voronoi / Lloyd / CVD-Lloyd / remeshing (45/46/47/140), Geogram hole filling (105), BFF (17), Heat-method geodesic (114 → GAP), PCA normal + MST (169 → GAP).
  • §13 discontinuity/DFN: Baecher (18), Joint-set DFN / clustering / authoring (127/128/129), DFN block extraction (82), Synthetic joint-set DFN (222), Fisher scatter / robustness (90/91), Block theory key-block (26), CrackGraph→BlockGraph (69), In-situ block size (122), orthogonal/parallel/radial/running-bond/vertical fracture sets (166/173/195/206/239/240/241), Equal-area stereonet (84 → GAP projection), Crack-graph DTO (68), Planar-facet extraction / FACETS (186 → also GAP VSA family).
  • §14 GPR: f-k Stolt + Hilbert + USGS (99/101), GPR survey-grid ingest (101), amplitude viz (98).
  • §15 quarry/yield: Cost/volume guillotine catalogue (66), RecoveryCascade, BlockCutOpt brute / omni / AMRR / Pareto / NSGA-II (27/28/4/175/176/156 → NSGA-II GAP), Density-watershed I5 (78), Cut-and-fill TIN prisms (70), Per-block slab-plan yield (180), Weighted-sum greedy extraction sort (246), Heterogeneous quarry pipeline (117), Fisher-robust BCO (90).
  • §16 robotics: CutPath→tool-axis frame (71), CutSegmentKind→KUKAprc / visose Robots (72/73), Arc Step (11), Moult2018 wire bandsaw / Zhang2024 robot diamond wire (152/249), Staged offset-shell roughing (217), Kerf-compensated curve offset (132 → GAP offset/skeleton).
  • §17 physics: Bullet rigid-body + convex-decomp (40), Concave-aware Z-up settle (54), Rigid-body settle of piles (204), Rigid depenetration / contact settle (202), Penetration hinge (179 → note), Kangaroo 2 dynamic settle / goal-based (130/131 → note projective dynamics), Trencadis dynamic settle (229).
  • §18 Kintsugi: Kintsugi 3D joiner (133), Breaking-Bad loader (38), verifier (172), Soft-ICP/CPD (216 → GAP), Weighted Kabsch SVD (245 → GAP), Trimmed ICP (233 → GAP), Phase correlator FFT (183/184 → GAP).
  • §19 surface packing: face-corner UV table, chart-scale, Trencadis catalog / greedy / EdgeMatch pack (228/230/231/83), GVF orientation, Per-face area-ratio distortion (182), Restricted Voronoi (198/199 → GAP).

B. GAPS — real math that was missing (added in §20–§27, this pass)

  1. PCA / covariance eigendecomposition; PCA-OBB; PCA normal estimation + MST orientation (Hoppe) — 192,170,161,163,169.
  2. QuickHull convex hull (vs monotone chain) — 194.
  3. Largest inscribed convex polygon / potato-peeling; Largest 4-sided inscribed — 137 (the slab-trim EXACT target, promised in the research dossier).
  4. Straight skeleton; kerf-compensated offset (Minkowski-with-disk) — 219,132.
  5. Restricted Voronoi diagram; power diagram; Voronoi perpendicular-bisector / shatter — 198,199,240,241.
  6. Quadric edge-collapse (Garland–Heckbert QEM); vertex-clustering decimation — 193,238.
  7. Variational Shape Approximation (Cohen–Steiner); SDF segmentation (Shapira); sharp-edge dihedral; planar-facet — 236,208,215,186.
  8. Heat-method geodesic distance (Crane) — 114.
  9. Weighted Kabsch via SVD; Soft-ICP / CPD (coherent point drift, EM); Trimmed ICP — 245,216,233.
  10. Phase-correlation FFT registration (2D/3D) — 183,184.
  11. Greedy LPT list scheduling (4/3 bound); FFD 3D bin-pack (11/9 bound) — 108,109.
  12. Welsh–Powell graph coloring — 247.
  13. Kahn topological sort / support-DAG install order / reversed-Kahn — 200,221,3,189.
  14. NSGA-II fast non-dominated sort + crowding distance — 156.
  15. Stereotomy: Monge lines-of-curvature; Frézier/Monge; voussoir principal-curvature cells (PendentiveDome / RadialVoussoir / VoussoirCellFactory) — 151,96,178,196,242.
  16. Equal-area (Lambert / Schmidt) stereonet projection — 84.
  17. Tukey-fence (IQR) outlier rule, vs the §3 2σ clip — 79.
  18. Connected-components labelling (union-find) — 56; BVH/Triangle-AABB pruning correctness — 232,146; projective / position-based dynamics (Kangaroo) note — 130,131,179.

C. NO-DERIVATION (format I/O, parse, dispatch, UI, trivial numeric — excused, no theorem)

GSSI DZT (103), MALA RD3+RAD (142), SEG-Y (209), IDS GeoRadar .dt (120), Sensors&Software DT1+HD (214), LASzip LAS/LAZ (136), OBJ/STL (164), PLY (171), VRML IFS (234), E57 worker read (168), XML+nested-zip .psx walk (248), Multi-format GPR dispatcher (153), File-extension recognition (89), Variant dispatcher (235), Vector fracture import (237), Discontinuity ingest (81), Load PLY fragments (141), On-demand fetch + SHA-256 (165), Folder enumeration + bucket (92), ISO 6983 G-code tokenizer (121), RhinoCAM NC dialect (201), Construct GPR preset (60), Crack-graph DTO builder (68), GPR amplitude visualisation (98), Interactive reflector picking (123), Auto interface detect / detector (13/124), Known-distance scale calibration (134), Parametric enlargement (174), Power-of-10 hardening (191), Voxel-grid downsample on read (243/244), Streaming cloud read + voxel (220), Dimension-stone review context (80), Fracture roughen fractal field (93), Synthetic stone-block / Voronoi-shatter test-bed generators (223/241 procedural), Mesh quality diagnostics/metrics/recipe (144/148/149), Auto-agglomerative outer loop (14).

D. Math / LaTeX quality audit

  • \ref/\label: all 16 referenced labels resolve (checked); 3 labels (thm:trim, thm:guillotine, thm:surfpack) defined-but-unreferenced (harmless).
  • Environments balance: \begin=\end=131 across definition/theorem/lemma/proposition/corollary/proof/ itemize/document.
  • Standard packages only (amsmath, amssymb, amsthm, mathtools, enumitem, geometry, hyperref) → portable.
  • Proof-rigour caveats (intentional sketches, flagged for Lean to fully discharge): Stolt (thm:stolt) cites the wave-equation dispersion relation; Poisson (thm:poisson) cites the distributional normal field; CRA static theorem (thm:cra) cites the limit-analysis lower-bound theorem; Goodman–Shi (thm:blocktheory) cites Shi's theorem. These are correct statements with literature-backed proofs; the .tex gives the argument skeleton, the Lean plan (PLAN_lean_formalization.md) lists what each needs to be airtight.

Result: with §20–§27 added, every one of the 249 titles is either COVERED, or an excused NO-DERIVATION. No mathematical algorithm is left out.