Spaces:
Sleeping
Sleeping
File size: 2,580 Bytes
e0ef700 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #!/usr/bin/env python3
"""Verify that certificate points produce the correct Delaunay triangulation."""
import json
import numpy as np
from scipy.spatial import Delaunay
from collections import Counter
# Load complete package
with open('complete_challenge_package.json', 'r') as f:
package = json.load(f)
# Get realizable challenge and certificate
challenge = package['challenge_1_realizable']
certificate_points = np.array(challenge['certificate_points'])
target_triangles = challenge['triangles']
print("="*70)
print("CERTIFICATE VERIFICATION")
print("="*70)
print(f"\nChallenge: {challenge['label']}")
print(f" Target triangulation: {len(target_triangles)} triangles")
print(f" Certificate points: {len(certificate_points)} points")
# Compute Delaunay of certificate points
print(f"\nComputing Delaunay triangulation of certificate points...")
tri = Delaunay(certificate_points)
computed_triangles = [tuple(simplex) for simplex in tri.simplices]
print(f" Result: {len(computed_triangles)} triangles")
# Compare combinatorial structure (normalize for comparison)
def normalize_triangulation(triangles):
"""Sort triangles for comparison."""
return sorted([tuple(sorted(t)) for t in triangles])
target_normalized = normalize_triangulation(target_triangles)
computed_normalized = normalize_triangulation(computed_triangles)
# Check if identical
if target_normalized == computed_normalized:
print(f"\n✓✓✓ CERTIFICATE VERIFIED ✓✓✓")
print(f" The certificate points produce EXACTLY the target triangulation!")
else:
print(f"\n✗ Certificate mismatch")
print(f" Target has {len(target_normalized)} triangles")
print(f" Computed has {len(computed_normalized)} triangles")
# Find differences
target_set = set(target_normalized)
computed_set = set(computed_normalized)
missing = target_set - computed_set
extra = computed_set - target_set
if missing:
print(f" Missing {len(missing)} triangles from target")
if extra:
print(f" Extra {len(extra)} triangles not in target")
# Also verify structural validity
print(f"\nStructural validation of certificate triangulation:")
edge_count = Counter()
for t in computed_triangles:
v0, v1, v2 = t
for edge in [tuple(sorted([v0, v1])), tuple(sorted([v1, v2])), tuple(sorted([v2, v0]))]:
edge_count[edge] += 1
max_count = max(edge_count.values()) if edge_count else 0
if max_count <= 2:
print(f" ✓ All edges in ≤2 triangles (max: {max_count})")
else:
print(f" ✗ Some edges in >2 triangles!")
print("="*70)
|