Descent parity desynchronizes on hemisphere+ rings with a long edge collinear to the probe lattice

[espg]

🤖 from Claude

Follow-up from PR #106 (Refs #103), filed on espg's go-ahead (comment). Pre-existing behavior made visible by #106's parity oracle — the old noise-sign machinery was strictly weaker on the same family. Not triggered by any workload reported so far; discovered by the phase-2 adversarial self-review.

Reproducer

Ring vertices (lat, lon): (10,45), (50,45), (-10,170), (-70,225), (-10,280) — hemisphere+ (winding taken as-given), with the first edge running 40° along the lon-45 meridian, i.e. collinear with the HEALPix probe lattice (base-0 centres and their descendants sit on that same near-plane, 1 ulp off coplanar).

• Debug build (with Uniform symbolic crossing predicate: fix base-cell-boundary mis-fill #106's parity oracle): polygon_to_morton_coverage(&lats, &lons, 6, true) panics — parity oracle diverged at uniform cell (51, 3) (and others).
• Release build: silently wrong coverage; vs the same ring with the meridian edge nudged to lon = 45.000001, the symmetric difference is thousands of cells at order 6 (measured 8221/~22k on the pre-phase-4 head; same order of magnitude after).
• Pinned as the #[ignore]d test test_descent_hemisphere_ring_collinear_edge_oracle in src_rust/src/coverage/tests.rs — un-ignore when this lands.

Diagnosis (from the PR #106 debugging session)

The seed layer is not the problem — after PR #106 phase 4, base_fills' donor chain is fully symbolic and every winding-classifiable seed agrees with it (pinned by test_base_fills_chain_no_antipodal_phantom).

The break is in the descent's fill chain, localized by leg-by-leg replay:

• Seed base 0 (centre (41.81, 45), exactly on the collinear edge's segment) chains to outside — consistent: the donor chord from centre 1 (winding +2π, inside) crosses edge 1 once.
• Leg centre(0,0) → centre(3,1) — both endpoints on the lon-45 near-plane, i.e. the probe is collinear with the 40° edge — counts exactly one crossing (edge 1, the transversal sibling departing the shared vertex (50,45)); the collinear edge 0 reports no crossing.
• But centre(3,1) at (66.44, 45) is unambiguously outside (winding 0, trustworthy — the point is on the edge's great circle but far beyond the segment and its antipode). Odd parity between two outside points ⇒ the subtree inverts; the oracle fires at the first uniform descendant.

So the vertex-graze bookkeeping between a collinear edge and its transversal sibling at the shared vertex desynchronizes: with all sidedness signs individually exact (post-#106), the pair of verdicts (edge 0: no, edge 1: yes) is still jointly wrong by one crossing for a probe that overlaps the collinear edge over tens of degrees rather than crossing it transversally. The arcs_cross_sos 4-sign identity is exact per arc pair; what's missing is a consistency argument (or construction) for the overlap configuration — two nearly-identical great circles whose intersection points are determined by 1-ulp residues, where "which incident edge carries the graze" must agree with the seed's side of the same near-plane. This is exactly the long-arc/scalloped-boundary territory sphere.rs's layer-2 comment defers ("an edge-crossing PIP built on layer 2 is deferred while its long-arc behaviour is validated").

Scope / what is NOT affected

• Every configuration in morton_coverage / from_wkt mis-fill polygons whose edges lie on base-cell boundaries (lon ≡ 0 mod 45°, lat = 0) #103's report (on-grid boxes, ring sectors, cap meridians, equator edges) — fixed and pinned by the 87-case matrix in mortie/tests/test_coverage_boundary.py.
• Sub-hemisphere polygons: normalize=True's orientation handling plus short probe legs appear to keep the family unreachable in the matrix sweep; the reproducer needs the hemisphere+ ring to place the transversal sibling's far endpoint where the graze attribution matters.

Suggested direction

1. Characterize the overlap configuration precisely (two near-coincident circles, segment overlap, shared vertex): enumerate the exact-sign outcomes and identify the invariant that must hold between "probe endpoint's side of the edge plane" (the seed/fill semantics) and "graze attribution at the shared vertex".
2. Candidate fixes, in increasing ambition: (a) detect probe-collinear edges (|dot(unit n_ab, p)| and |dot(unit n_ab, q)| both < ε) and handle the overlap case by splitting the parity decision at the shared vertices' exact sides — a bounded special case; (b) the deferred edge-crossing PIP from a fixed reference with reserved identity, replacing chained fill entirely for degenerate subtrees; (c) route the whole fill chain through exact segment-overlap reasoning (S2's VertexCrossing analogue for collinear overlaps).
3. Whatever lands, the acceptance gate already exists: un-ignore test_descent_hemisphere_ring_collinear_edge_oracle, and the parity oracle validates every uniform cell on the whole suite.

Refs #103, PR #106.

[espg]

Candidate fixes, in increasing ambition: (a) detect probe-collinear edges (|dot(unit n_ab, p)| and |dot(unit n_ab, q)| both < ε) and handle the overlap case by splitting the parity decision at the shared vertices' exact sides — a bounded special case; (b) the deferred edge-crossing PIP from a fixed reference with reserved identity, replacing chained fill entirely for degenerate subtrees; (c) route the whole fill chain through exact segment-overlap reasoning (S2's VertexCrossing analogue for collinear overlaps).

what are the pros and cons of (a), (b), and (c) in terms of run time, correctness, robustness, and maintainability. Do you have a recommendation? Does it make sense to implement more then one of the them and test the candidate implementations against each other, or do we have a pretty good idea of the trade space ahead of time?

[espg]

🤖 from Claude

Trade-space across the four axes, then the recommendation.

(a) Special-case probe-collinear overlaps in the parity chain

• Runtime: effectively free — detection is two dots per (probe, edge) pair and only on the already-escalated degenerate path.
• Correctness: fixes the diagnosed family, but it's a patch on the chain: the proof obligation becomes "this special case composes with every other leg" — graze attribution at both ends of an overlap, chains of collinear edges end-to-end, overlap at a probe endpoint vs interior, collinear corner-probes. Each is another case analysis.
• Robustness: medium — closes the known reproducer without producing a global invariant. The repo's own history is the counter-argument: Polygon's malformed when crossing the prime meridian #11 → Robust hemisphere+ point-in-polygon (S2-style orientation + SoS) #44 → on_minor_arc FP/SoS hardening #78 → SoS-harden on_minor_arc in robust_crossing #87 → morton_coverage / from_wkt mis-fill polygons whose edges lie on base-cell boundaries (lon ≡ 0 mod 45°, lat = 0) #103 were each "one more local hardening," and each left a residue.
• Maintainability: worst per line — a subtle special case in the subtlest hot-path code, unreadable in two years.

(b) Direct classification for degenerate subtrees (the deferred edge-crossing PIP)

• Runtime: O(E) per degenerate cell (one reference→centre arc through arcs_cross_sos over all edges) instead of O(local edges) per leg — but only cells flagged on an edge plane pay it; clean polygons (every zagg workload so far) pay literally zero. Memoizable per subtree if a profile ever asks.
• Correctness: strong, and the argument is short: chaining is replaced by one arc from one fixed, already-classified reference point, so joint consistency across legs — the thing that actually broke — reduces to the correctness of independent single arcs_cross_sos calls, which is the property we've already validated hard. Crucially, this is the generalization of the phase-4 fix that already works: base_fills' donor chain is exactly this mechanism at the seed level, pinned by test.
• Robustness: high — one mechanism, already field-tested at the seeds, extended to cells.
• Maintainability: good — deletes "chain + hope" for degenerate regions; the invariant is one sentence: degenerate cells are classified directly, never chained.
• Caveats: reference selection must avoid antipodal/degenerate reference arcs — the base_fills donor logic (non-antipodal, unambiguous donor) already solves this and can be reused verbatim.

(c) Full collinear-overlap crossing algebra (S2 VertexCrossing analogue)

• Runtime: neutral (predicate-level).
• Correctness: the theoretically complete answer — total crossing counts for shared vertices and overlaps, making the chain itself trustworthy everywhere.
• Robustness: highest if implemented correctly — and that's the catch: S2 needed VertexCrossing + EdgeCrosser plus real proofs; ours must additionally compose with SoS identities and the exact-sign layer. The highest chance of a subtle bug sits precisely in the machinery meant to eliminate subtle bugs.
• Maintainability: heaviest — a genuine geometric-kernel component with standing proof obligations, justified only if we need trusted chains globally, which (b) makes unnecessary.

Recommendation: (b), with (a)'s detection as its trigger, skip (c). They're not really three competitors: (a)'s collinearity test is the natural gate ("this cell/subtree is degenerate → classify directly"), (b) is the fix, and (c) buys generality we stop needing once degenerate regions aren't chained. This also unifies the code: seeds and cells then use one identical mechanism.

Race implementations? Mostly no — the trade space is analytic (composition-proof vs direct-evaluation is a structural argument, not an empirical one), and building (a) standalone just to lose to (b) duplicates the gate we'd keep anyway. The empirical piece worth doing is a shared validation harness, not competing implementations: adversarial-ring fuzz (random rings with deliberate collinear runs on lattice planes, both hemispheres, both windings, nudged-control differentials) running under the parity oracle, plus un-ignoring test_descent_hemisphere_ring_collinear_edge_oracle as the acceptance gate. That harness scores (b) now and would score a future (c) identically if one is ever wanted.

---

Generated by Claude Code

[espg]

🤖 from Claude

Clarifying the last sentence of the recommendation ("this also unifies the code: seeds and cells then use one identical mechanism") — that refers to (a) + (b), not (c).

After PR #106 phase 4, base_fills already classifies seeds by direct evaluation: pick an unambiguous donor, run one arc through arcs_cross_sos over all edges, done. Option (b) is that same construction applied to cells whose centres (a)'s collinearity gate flags as degenerate — replacing the multi-leg chained fill for exactly those cells. So (a)+(b) leaves one classification mechanism in the codebase, used identically at both levels: degenerate point ⇒ classify directly from a clean reference; everything else ⇒ the fast chain. (c) would unify along a different axis — making the chain itself trustworthy everywhere — which stops being necessary once degenerate regions aren't chained at all.

---

Generated by Claude Code

[espg]

Recommendation: (b), with (a)'s detection as its trigger

approved

[espg]

🤖 from Claude

Label-readiness: ready for implement directly — the design fork ((a)+(b) vs (c)) is settled above with your sign-off, and the acceptance gates already exist in executable form. The remaining choices (gate placement, reference selection, memoization) are engineering decisions the parity oracle adjudicates; none is a fork needing your call. For completeness, the phasing the PR would carry:

1. Phase 1 — the gate + direct classifier. (a)'s collinearity detection (|dot(unit n_ab, centre)| < ε against relevant edges) as the trigger; a classify_direct(point) -> bool built on base_fills' existing donor machinery (unambiguous reference + one arcs_cross_sos pass over all edges — reuse, not new code). Unit tests on the Descent parity desynchronizes on hemisphere+ rings with a long edge collinear to the probe lattice #107 reproducer's specific centres.
2. Phase 2 — wire into the descent. A gated node takes fill = classify_direct(centre) instead of the chained parity; children of a gated node re-evaluate the gate (a subtree exits degeneracy as it descends off the plane). Un-ignore test_descent_hemisphere_ring_collinear_edge_oracle — the acceptance gate.
3. Phase 3 — adversarial fuzz harness. Random rings with deliberate collinear runs on lattice planes × both hemispheres × both windings × nudged-control differentials, running under the parity oracle; doubles as the standing validation harness for any future predicate work.
4. Phase 4 — perf check. CodSpeed comparison; the gate is two dots on the already-escalated path and classify_direct only fires for gated cells, so clean geometry should be flat.

Blocked-by note: builds directly on PR #106's machinery, so the PR would be Blocked by #106 until that merges (or branch from its branch if you'd rather it not wait).

---

Generated by Claude Code