Speed up Level 4 embedding validation narrow phase (exact intersection predicate)

[acgetchell]

Summary

Level 4 embedding validation (added in #449) is too slow at scale. For the 2D large-scale case (32,000 vertices -> 63,885 simplices), validation_report (Levels 1-5) takes ~190s, dominated by the Level 4 embedding narrow phase (~174s, ~89%). A secondary cost is the Euclidean Level 5 all-violations scan (~22s), tracked separately in #483. Insertion for the same case is only ~45s.

Measured L4 vs L5 split (2D, 63,885 simplices; feat/449 branch)

Per-level wall times from one validation_report run (in-test watchdog raised so it completes):

• L1-3 (structure + topology): 0.20s
• L4 embedding (embedding_report): 173.6s <- this issue
• L5 delaunay_report (Euclidean all-violations): 21.8s <- tracked in Speed up Euclidean Level 5 Delaunay validation report (O(S*V) all-violations scan) #483
• L5 is_valid_delaunay (flip-based, same pass/fail): 48.8ms

Level 4 is ~89% of the full-report cost; the remaining ~11% is the Euclidean Level 5 all-violations scan (#483). This issue covers Level 4 only.

Evidence

Measured on feat/449-embedded-triangulation-validation (in-test watchdog raised so the run completes):

• Insertion wall time: ~45-46s
• repair wall time: ~0.11s
• validation_report (Levels 1-5): ~190s (L4 ~174s + Euclidean L5 all-violations ~22s + L1-3 ~0.2s)
• Total: ~235s

On the pre-#449 branch the same report ran in ~0.3s, so the new cost is the #449 Level 4 embedding check (plus the renumbered Level 5 all-violations scan; see #483).

Root cause

validate_simplex_embeddings_intersect_only_in_shared_faces (src/geometry/embedding.rs) runs an exact BigRational linear program on every AABB-overlapping candidate pair: it solves D+1 exact DxD barycentric systems and enumerates C(2(D+1), D) active-constraint sets (15/56/210/792 for D=2..5), each an exact Gaussian solve over ratios of bignums (solve_rational_system).

The sweep-and-prune broad phase (landed with #449) removes the O(S^2) AABB scan, but the dominant remaining candidate class is face-sharing neighbors (share a vertex/edge but not a full facet). Their true intersection is exactly the shared face, so the decision sits on a true-zero boundary: a float/interval prefilter is inconclusive there and falls back to exact regardless. The fix has to make the exact path fast.

Proposed approach

1. Fast exact narrow-phase kernel. Replace the BigRational Gaussian solver with fraction-free exact sign evaluation reusing exact_det_sign (Bareiss) - the same exact stage used by insphere/orientation. Reformulate each LP decision (feasibility >= 0, witness > 0) as a sign-of-determinant on the input coordinates. Preserve semantics and error shapes exactly.
2. Cheap disjointness early-out. Before any solve, a conservative f64 separating-axis test (facet normals via the existing robust orientation filter) rejects clearly-disjoint candidate pairs without exact work. Sound: a certified separating axis proves disjointness; inconclusive => proceed.
3. Optional Stage-1 fast filter via matrix_fast_filter -> exact_det_sign where a single determinant drives a decision. General interval arithmetic in la-stack is deferred - it would not resolve the boundary pairs.

Implementation pointers

• Broad phase (done, Add embedded triangulation validation independent of the Delaunay predicate #449): for_each_candidate_simplex_pair (sweep-and-prune) in src/core/embedding.rs; Euclidean charts only, periodic stays exhaustive.
• Stage 0 (done, Add embedded triangulation validation independent of the Delaunay predicate #449): try_validate_full_facet_pair in src/core/embedding.rs already fast-paths full-facet neighbors with two robust_orientation tests, bypassing the barycentric solver for the adjacent-pair case.
• Narrow phase to replace: validate_simplex_pair_intersection -> validate_simplex_embeddings_intersect_only_in_shared_faces (src/geometry/embedding.rs), currently exact BigRational with no f64 filter.
• Predicate idiom to reuse: matrix_fast_filter (Shewchuk det+errbound, src/geometry/matrix.rs) -> exact_det_sign (Bareiss) -> degenerate fallback, as in try_orientation_from_matrix / try_insphere_from_matrix (src/geometry/predicates.rs).

Soundness / correctness

• No semantic change to Level 4. Add a property test asserting the new narrow phase agrees with the current BigRational predicate on the shared domain (random + degenerate simplex pairs, 2D-5D).
• Keep the periodic/toroidal path on the exact predicate (compat with the periodic Level 4 verification landed in Periodic-aware Delaunay verification (Level 4) for toroidal triangulations #315).
• Typed errors and the is_valid_embedding / embedding_report / validate_embedding surface stay unchanged.

Acceptance criteria

• Benchmark before/after per docs/dev/perf-tuning.md; add a Level 4 embedding-validation benchmark if none exists (2D-5D, realistic + near-degenerate inputs).
• embedding_report() (Level 4) for the 2D 63,885-simplex case drops from ~174s to <= a few seconds.
• just ci green. (Full validation_report at this scale also needs Speed up Euclidean Level 5 Delaunay validation report (O(S*V) all-violations scan) #483 to drop the ~22s Euclidean Level 5 all-violations cost.)

Notes

• Prerequisite Add embedded triangulation validation independent of the Delaunay predicate #449 is merged (v0.8.0): the SAP broad phase and the perf-smoke decoupling (DELAUNAY_LARGE_DEBUG_VALIDATION=construction) are on main, so this issue is unblocked and ready to start.
• Sibling / follow-up: Speed up Euclidean Level 5 Delaunay validation report (O(S*V) all-violations scan) #483 (speed up the Euclidean Level 5 all-violations Delaunay report). Speed up Level 4 embedding validation narrow phase (exact intersection predicate) #482 blocks Speed up Euclidean Level 5 Delaunay validation report (O(S*V) all-violations scan) #483.
• Related: Periodic-aware Delaunay verification (Level 4) for toroidal triangulations #315 (closed - periodic-aware Delaunay verification (Level 4) for toroidal triangulations). An earlier revision of this issue cited docs: clarify README scientific basis summary and deeper validation docs #445 by mistake; docs: clarify README scientific basis summary and deeper validation docs #445 is a docs issue.
• A short spike to confirm the kernel reaches the target before the full reformulation is reasonable.

[acgetchell]

v0.8.0 scope update

The revised Level 4 narrow-phase implementation is being carried by #506 for v0.8.0. This issue remains open in the v0.8.1 milestone for the acceptance work that should not be rushed into the release audit:

• add an independent old-vs-new agreement oracle over randomized and degenerate 2D-5D simplex pairs;
• record representative before/after Level 4 benchmarks, including the documented 32,000-vertex / 63,885-simplex case;
• confirm the optimized path meets the issue performance target with the invariant checks intact.

The bounded v0.8.0 4D/5D slow-test probes are release regressions, not substitutes for that evidence. #483 remains the separate Level 5 all-violations follow-up and stays blocked on this work.