-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
876 lines (736 loc) · 35 KB
/
index.html
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
<!doctype html>
<head>
<meta charset="utf-8">
<title>A Discrete Model of the Euclidean Plane</title>
<script src="https://distill.pub/template.v2.js"></script>
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script id="MathJax-script" async
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
</script>
</head>
<body>
<d-title>
<h1>A Discrete Model of the Euclidean Plane</h1>
<p>
<a href="https://github.com/moshelooks">Moshe Looks</a>,
<a href="https://github.com/moshelooks/eugrid/commits/main/index.html">12/17/2021</a>
</p>
<p>
Imagine a digital universe where points in space are vertices in a graph, and the
distance between two points is the length of a shortest path between them. Can the graph
be structured whereby macroscopic observers living in the universe perceive isotropic
space, as we perceive in our universe?
</p>
<figure class="l-body" style="margin-top: 0%;">
<a title="Kanjuro Shibata XX "Ensō (円相)", CC BY-SA 3.0"
href="https://commons.wikimedia.org/wiki/File:Enso.jpg">
<img alt="Enso" src="https://upload.wikimedia.org/wikipedia/commons/f/f1/Enso.jpg">
</a>
</figure>
</d-title>
<d-article>
<h2>Introduction</h2>
<p>
The distance \(d_G(u, v)\) between vertices in an undirected graph \(G = (V, E)\) is the
number of edges in a shortest path between \(u\) and \(v\). The distance \(d_2(u, v)\)
between points on the Euclidean plane is the \(2\)-norm of the line segment between \(u\)
and \(v\). Non-degenerate \(V \subset \mathbb{N}^2\) cannot satisfy \(d_G = d_2\) because
of the <a href="https://en.wikipedia.org/wiki/Square_root_of_2">incommensurability</a> of
the side and the diagonal of a square. Nonetheless, \(d_G\) can be used to approximate
\(d_2\); the approximation will be better or worse as a function of \(G\). How well can
\(d_G\) approximate \(d_2\), as \(|V|\) grows?
</p>
<p>
This question is difficult to answer in full generality. Let's consider the special case
of a graph whose vertices are the square grid \(\{1, \ldots, n\} \times \{1, \ldots,
n\}\). If we add edges between horizontal and vertical neighbors, we get \(d_1\)
taxicab distances, based on the \(1\)-norm. If we additionally add edges between
diagonal neighbors, then we get \(d_\infty\) chessboard distances, based on the
\(\infty\)-norm.
</p>
<figure class="l-body" style="margin-bottom: 0%;">
<img alt="Taxicab Distance" src="figures/manhattan.svg"
style="width: 40%;">
<img alt="Chessboard Distance" src="figures/chessboard.svg"
style="width: 40%; margin-left: 6%">
</figure>
<figure class="l-body" style="display: flex; margin-top: 0%; margin-bottom: 0%;">
<figure style="width: 40%; margin-top: 0%;">
<figcaption>
<b>Left:</b> Graph with taxicab distances.
</figcaption>
</figure>
<figure style="width: 40%; margin-top: 0%; margin-left: 6%;">
<figcaption>
<b>Right:</b> Graph with chessboard distances.
</figcaption>
</figure>
</figure>
<p>
We have the nice property that \(d_1 \leq d_2 \leq d_\infty\), although neither one of
these constructs gives us a very good approximation of \(d_2\). It is easy to see that in
both cases, the divergences from \(d_2\) grow unboundedly with \(n\). In fact,
Fritz<d-cite key="Fritz_2013"></d-cite> has proven that this divergence happens
for <i>every</i> distance function based on a periodic graph. But nothing prevents us
from considering aperiodic graphs. What happens if we start with a graph corresponding to
\(d_1\) and we add edges between only <i>some</i> diagonal neighbors? Let's call this
sort of graph, where \(d_G\) is meant to approximate \(d_2\), an
order-\(n\) <i>Eugrid</i>.
</p>
<p>
Certain formal properties of Eugrids are worth calling out at this point to avoid
confusion. All order-\(n\) Eugrids share the same square grid of vertices depicted
above. Edges corresponding to line segments of unit length are present in all Eugrids.
Eugrids vary in the presence or absence of edges corresponding to line segments of length
\(\sqrt{2}\). Edges corresponding to line segements of other lengths <i>never</i> appear.
</p>
<p>
It is notationally convenient <d-footnote>This representation ignores graph symmetries
and is thus inappropriate for combinatoric calculations.</d-footnote> to represent
order-\(n\) Eugrids by pairs of square bit matrices of order \(n-1\), which we refer to
as the diagonals and antidiagonals, respectively. Diagonals are edges corresponding to
line segments paralleling \(x=y\). Antidiagonals run cross-wise, paralleling \(x=-y\).
</p>
<h2>Eugrid Construction Heuristics</h2>
<p>
Let us consider for the moment only distances from the corner vertex \(\mathbf{1} := (1,
1)\) to other points. This lets us ignore the antidiagonals, which do not affect
distances between \(\mathbf{1}\) and other points, simplifying notation, discussion, and
visualization.
</p>
<p>
A very simple way to interpolate between taxicab and chessboard distances is to decide
on the presence or absence of each diagonal edge by sampling a random variate from a
Bernoulli distribution. We can visualize this interpolation by drawing “circular arcs” of
radius \(n\) where the pixel at \(x, y\) is black iff \(d_G(\mathbf{1}, (x, y)) \le r\).
</p>
<figure class="l-body" style="margin-bottom: 0%;">
<img alt="Circular Arcs" src="figures/arcs.gif"
style="width: 90%; margin-left: 2%;">
</figure>
<figure class="l-body" style="display: flex; margin-top: 0%; margin-bottom: 0%;">
<figure style="width: 45%; margin-top: 0%; margin-left: 2%;">
<figcaption>
<b>Left:</b> Taxicab circular arcs, \(r = 0, 1, 2, 3, 4\).
</figcaption>
</figure>
<figure style="width: 45%; margin-top: 0%; margin-left: 4%;">
<figcaption>
<b>Right:</b> Chessboard circular arcs, \(r = 0, 1, 2, 3, 4\).
</figcaption>
</figure>
</figure>
<figure class="l-body" style="margin-left: 5%;">
<img alt="Circular Arcs" src="figures/randarcs.png" style="width: 90%;">
<figcaption style="width: 80%;">
Circular arcs for random order-\(512\) Eugrids with \(p = 0, 1/8, \ldots, 1\).
</figcaption>
</figure>
<p>
This initially seems promising. If we drill down a bit we find that the best
fit <d-footnote>Determined by Hamming distance from an ideal circular arc.</d-footnote>
is obtained around \(p = 0.17\).
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="Circular Arcs" src="figures/randarcs_zoomed.png" style="width: 90%;">
<figcaption style="width: 80%;">
Circular arcs for random order-\(512\) Eugrids with \(p = 0.13, 0.14, \ldots, 0.21\).
</figcaption>
</figure>
<p>
If we inspect this result carefully however, we notice a problem.
</p>
<figure class="l-body" style="margin-bottom: 0%;">
<img alt="Circular Arc for p=0.17" src="figures/best_randarc.png"
style="width: 64%;">
<img alt="Minimum Angles" src="figures/best_randarc_mangle.png"
style="width: 16%; margin-left: 6%">
</figure>
<figure class="l-body" style="display: flex; margin-top: 0%; margin-bottom: 0%;">
<figure style="width: 30%; margin-top: 0%;">
<figcaption>
<b>Left:</b> Circular arc for random order-\(512\) Eugrid with \(p = 0.17\).
</figcaption>
</figure>
<figure style="width: 50%; margin-top: 0%; margin-left: 6%;">
<figcaption>
<b>Right:</b> Minimum angular measurements; \(x, y\) is black where the graph
distance from \(\mathbf{1}\) to \(x, y\) equals the distance to \(1, y\).
</figcaption>
</figure>
</figure>
<p>
The arc in the figure on the left above looks decently circular away from the axes, but
near the axes themselves there are straight lines, corresponding to a rather high degree
of anisotropy. As the figure on the right above shows, this anisotropy does not diminish
as the measurement scale increases <d-footnote>Diminishing anisotropy with measurement
scale would manifest as sublinear growth in the width of the black region of the figure,
moving downwards.</d-footnote> but remains more-or-less constant, and hence detectable by
a macroscopic observer.
</p>
<p>
This informal analysis suffices to demonstrate that Eugrids based on random Bernoulli
variates are poor models of the Euclidean plane. It is nonetheles encouraging to see that
such a simple procedure can yield reasonably circular arcs, at least away from the axes.
</p>
<p>
In order to devise better heuristics we must take a look at Eugrid microstructure. Let
\((x_v, y_v)\) be the Cartesian coordinates of vertex \(v\). Assuming \(x_u \leq x_v\) and
\(y_u \leq x_v\), <d-footnote>This is always the case when \(u = \mathbf{1}\).</d-footnote>
$$\mathbb{D}_1(u, v) := 1 + d_G(u, v)$$
is the graph distance between \(u\) and \(v + \mathbf{1}\) when the diagonal at
\(v\) <d-footnote>This is the edge between \(v\) and \(v + \mathbf{1}\).</d-footnote> is
present in the graph, and
$$\mathbb{D}_2(u, v) := 1 + \min(d_G(u, (x_v + 1, y_v)), d_G(u, (x_v, y_v + 1)))$$
is the distance when the diagonal at \(v\) is absent. Let us further define
$$L^u_i(v) := |d_2(u, v + \mathbf{1}) - \mathbb{D}_i(u, v)|.$$
\(L^u_1(v)\) is the loss (i.e. deviation from Euclidean distance) from \(u\) when the
diagonal at \(v\) is present, and \(L^u_2(v)\) is the loss from \(u\) when the diagonal
at \(v\) is absent. For example,
$$L^\mathbf{1}_i(v) = |\sqrt{x_v^2 + y_v^2} - \mathbb{D}_i(\mathbf{1}, v)|.$$
</p>
<h3>The \(\mathbf{1}\)-growth heuristic</h3>
<p>
A simple greedy approach to constructing Eugrids is to visit each potential diagonal at
\(v\) exactly once <d-footnote>Taking care to visit the diagonal at \((x+1, y+1)\) after
we have visited the diagonals at \((x+1,y)\) and \((x,y+1)\).</d-footnote> and decide
whether or not to add it to the graph based on whether \(L^\mathbf{1}_1(v)\) or
\(L^\mathbf{1}_2(v)\) is smaller <d-footnote>When the two quantities are equal we add the
diagonal, based on the results of some preliminary ad hoc experiments.</d-footnote>. We
refer to this approach as the \(\mathbf{1}\)-growth heuristic.
</p>
<figure class="l-body" style="margin-left: 10%;">
<img alt="Visualization of Diagonals" src="figures/simple.png" style="width: 80%;">
<figcaption style="width: 80%;">
Visualization of diagonals generated by the \(\mathbf{1}\)-growth heuristic out to \(128,
128\). Pixels are black where \(L_1 \lt L_2\), white where \(L_1 \gt L_2\), and gray
where \(L_1 = L_2\).
</figcaption>
</figure>
<p>
\(\mathbf{1}\)-growth is a completely deterministic procedure, but the graph structure that it
produces is aperiodic, so Fritz's no-go theorem does not apply; arcs around
\(\mathbf{1}\) become increasingly circular as the radius increases.
</p>
<figure class="l-body" style="margin-bottom: 0%;">
<img alt="Circular Arc for 1-Growth Heuristic" src="figures/best_simparc.png"
style="width: 64%;">
<img alt="Minimum Angles" src="figures/best_simparc_mangle.png"
style="width: 16%; margin-left: 6%">
</figure>
<figure class="l-body" style="display: flex; margin-top: 0%; margin-bottom: 0%;">
<figure style="width: 30%; margin-top: 0%;">
<figcaption>
<b>Left:</b> Circular arc for order-\(512\) Eugrid; \(\mathbf{1}\)-growth heuristic.
</figcaption>
</figure>
<figure style="width: 50%; margin-top: 0%; margin-left: 6%;">
<figcaption>
<b>Right:</b> Minimum angular measurements; \(x, y\) is black where the graph
distance from \(\mathbf{1}\) to \(x, y\) equals the distance to \(1, y\).
</figcaption>
</figure>
</figure>
<p>
This demonstrates that the Eugrid representation can give us a very nice model of the
Euclidean plane, with minimal anisotropy, at least from a single perspective. The moment
we shift our perspective however, things begin to seem rather worse.
</p>
<figure class="l-body" style="margin-bottom: 0%;">
<img alt="Circular Arc for 1-Growth Heuristic" src="figures/bad_simparc.png"
style="width: 64%;">
<img alt="Minimum Angles" src="figures/bad_simparc_mangle.png"
style="width: 16%; margin-left: 6%">
</figure>
<figure class="l-body" style="display: flex; margin-top: 0%; margin-bottom: 0%;">
<figure style="width: 80%; margin-top: 0%;">
<figcaption>
As above, but with the perspective shifted from \(\mathbf{1}\) by \(32, 64\).
</figcaption>
</figure>
</figure>
<p>
Even worse than in the case of Bernoulli random variates, we see severe anisotropy around
the axes; back to the drawing board!
</p>
<h3>The \(\Gamma\)-growth heuristic</h3>
<p>
How can we make better Eugrids? We can generalize the \(\mathbf{1}\)-growth heuristic and
consider losses from more vertices than just \(\mathbf{1}\). What is left is to
specify <i>which</i> vertices, and how to weight their relative contributions, since
adding a particular diagonal edge may make some distances more Euclidean, and other less
so.
</p>
<p>
For the diagonal at \(v\), we can potentially calculate losses from all vertices \(u\)
such that \(x_u \leq x_v\) and \(y_u \leq y_v\). But since this both highly redundant and
scales badly with \(n\), we restrict ourselves to vertices along the left and upper edges
of the Eugrid, i.e.
$$\Gamma_v := \{u \mid x_u \leq x_v \land y_u \leq y_v \land \min(x_u, y_u) = 1\}.$$
We refer to this approach as the \(\Gamma\)-growth heuristic, and the resulting graphs as
\(\Gamma\)-Eugrids.
</p>
<figure class="l-body" style="margin-left: 15%;">
<img alt="Gamma distances" src="figures/gamma.svg" style="width: 70%;">
<figcaption>
Vertices in \(\Gamma_v \cup \{v\}\) and line segments \(uv\) for \(u_\in \Gamma_v\) when
\(v = (5, 5)\).
</figcaption>
</figure>
<p>
This gives us nice coverage and is computationally tractable, but requires careful
normalization to balance relative contributions. In particular, we include two factors.
</p>
<p>
The first factor weights the contribution of vertex \(u\) by the angle \(\theta^u_v\ :=
\widehat{abc}\), where \(b := v + \mathbf{1}\) and \(a\) and \(c\) are the midpoints
between \(u\) and its two adjacent points in \(\Gamma_v\) <d-footnote>Additionally
considering \((x_v+1, 1)\) and \((1, y_v+1)\) as adjacent points for the respective edge
cases of \(u = (x_v, 1)\) and \(u = (1, y_v)\).</d-footnote>.
</p>
<ul>
<li>
If \(x_u \gt 1\) and \(y_u = 1\), then \(a = (x_u - 0.5, 1)\) and \(c = (x_u + 0.5,
1)\).
</li>
<li>
Likewise, if \(x_u = 1\) and \(y_u \gt 1\), then \(a = (1, y_u - 0.5)\) and \(c = (1,
y_u + 0.5)\).
</li>
<li>
Finally, if \(x_u = y_u = 1\), then \(a = (1.5, 1)\) and \(c = (1, 1.5)\).
</li>
</ul>
<p>
The second factor mitigates against axis-parallel anisotropy by assigning greater
importance to vertex \(u\) when the line between \(u\) and \(v\) is closer to
axis-parallel, and is defined as
</p>
$$\alpha^u_v := \frac{\max{(x_v - x_u, y_v - y_u}) + 1}{\min{(x_v - x_u, y_v - y_u)} + 1}_.$$
<p>
Putting it all together, we have
$$L^\Gamma_i(v) := \sum_{u_\in \Gamma_v}{\theta^u_v \cdot \alpha^u_v \cdot L^u_i(v)}.$$
<figure class="l-body" style="margin-left: 5%;">
<img alt="Gamma Diagonals" src="figures/gamma_diags.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Diagonals generated by the \(\Gamma\)-growth heuristic out to \(16, 16\).
</figcaption>
</figure>
<figure class="l-body" style="margin-left: 5%;">
<img alt="Gamma Diagonals" src="figures/gamma_diags.png" style="width: 90%;">
<figcaption style="width: 90%;">
Visualization of diagonals generated by the \(\Gamma\)-growth heuristic out to \(1024,
1024\). Pixels are black where diagonals edges are present, and white where they are
absent.
</figcaption>
</figure>
<p>
As with the \(\mathbf{1}\)-growth heuristic, the graph produced by \(\Gamma\)-growth is
deterministically generated yet aperiodic. It has a rather more complex structure,
however, reminiscent of the patterns produced by
<a href=https://mathworld.wolfram.com/Rule30.html>well-known cellular automata</a>.
</p>
<figure class="l-body" style="margin-bottom: 0%;">
<img alt="Circular Arc for Gamma-Growth Heuristic" src="figures/comparc.png"
style="width: 64%;">
<img alt="Minimum Angles" src="figures/comparc_mangle.png"
style="width: 16%; margin-left: 6%">
</figure>
<figure class="l-body" style="display: flex; margin-top: 0%; margin-bottom: 0%;">
<figure style="width: 30%; margin-top: 0%;">
<figcaption>
<b>Left:</b> Circular arc for order-\(512\) Eugrid; \(\Gamma\)-growth heuristic.
</figcaption>
</figure>
<figure style="width: 50%; margin-top: 0%; margin-left: 6%;">
<figcaption>
<b>Right:</b> Minimum angular measurements; \(x, y\) is black where the graph
distance from \(\mathbf{1}\) to \(x, y\) equals the distance to \(1, y\).
</figcaption>
</figure>
</figure>
<p>
This approach gives us fairly circular arcs around \(\mathbf{1}\), with minimal
anisotropy.
</p>
<figure class="l-body" style="margin-bottom: 0%;">
<img alt="Circular Arc for Gamma-Growth Heuristic" src="figures/shift_comparc.png"
style="width: 64%;">
<img alt="Minimum Angles" src="figures/shift_comparc_mangle.png"
style="width: 16%; margin-left: 6%">
</figure>
<figure class="l-body" style="display: flex; margin-top: 0%; margin-bottom: 0%;">
<figure style="width: 80%; margin-top: 0%;">
<figcaption>
As above, but with the perspective shifted from \(\mathbf{1}\) by \(32, 64\).
</figcaption>
</figure>
</figure>
<p>
Furthermore, we obtain reasonable-looking results even when we shift our perspective.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="Gamma Arcs" src="figures/gamma_arcs.png" style="width: 90%;">
<figcaption style="width: 90%;">
Circular arcs of radius \(1000\) with \(1024 \times 1024\) spacing,
on an order-\(8193\) Eugrid; \(\Gamma\)-growth heuristic.
</figcaption>
</figure>
<p>
So far we have only considered the determination of the diagonal edges, corresponding to
line segments paralleling \(x=y\). We must also specify how the antidiagonals edges,
paralleling \(x=-y\), are determined. There are various possibilities that one could try,
but perhaps the simplest, and the one chosen here, is to simply flip the diagonals (in
their bit matrix representation) along the first axis. That is to say, an antidiagonal
edge exists between the vertices \((x+1, y)\) and \((x, y+1)\) iff a diagonal
edge exists between the vertices \((n - x, y)\) and \((n - x +1, y+1)\).
<d-footnote>
While the resulting graphs are technically non-planar, an equivalent planar graph may
be obtained, if desired, by simply doubling the Eugrid so that e.g.
<br>
<img alt="Little X" src="figures/little_x.svg" style="width: 10%;">
<br>
is replaced by
<br>
<img alt="Big X" src="figures/big_x.svg" style="width: 20%;">.
</d-footnote>
</p>
<p>
Now we can at last make lovely circles, like so:
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="Gamma Circles" src="figures/gamma_circles.png" style="width: 90%;">
<figcaption style="width: 90%;">
Circles of radius \(500\) with \(1024 \times 1024\) spacing, on an order-\(8193\)
Eugrid; \(\Gamma\)-growth heuristic.
</figcaption>
</figure>
<p>
At this point you might be getting a bit uncomfortable with developing and evaluating a
discrete model of the Euclidean plane by comparing pictures of vaguely circular blobs.
Fortunately, these sorts of models are well-suited to quantitative analysis, which we
will turn to in the next section.
</p>
<h2>Quantitative Analysis</h2>
<p>
Farr and Fink<d-cite bibtex-key="Farr_2019"></d-cite> propose three tests for discrete
models aiming to capture Euclidean geometry. The tests were proposed for models of the
2-sphere, which Eugrids are not. It is nonetheless fairly straightforward to adapt them
to our setting, bearing in mind that the results obtained thereby will not be quite
apples-to-apples comparable with the original metrics.
</p>
<h3>Hausdorff dimension</h3>
<p>
As defined by <d-cite bibtex-key="Farr_2019"></d-cite> this test measures the statistical
distribution of vertex eccentricity <d-footnote>The eccentricity of a vertex is the
greatest distance between it and any other vertex.</d-footnote> as the size of the graph
increases, in comparison to the distribution that one would expect based on Euclidean
distances. In particular we consider the distribution over random \(v_\in V\) of the
graph eccentricity
$$\epsilon_G(v) := \max_{u_\in V}d_G(u, v)$$
in comparison to the Euclidean eccentricity
$$\epsilon_2(v) := \max_{u_\in V}d_2(u, v).$$
</p>
<p>For comparing Eugrids of different orders \(n\) we will consider the distribution of
$$H_G(v) := \frac{\epsilon_G(v) - \epsilon_2(v)}{\sqrt{n}}_.$$
In particular, we will wish to demonstrate that \(E[H_G]\) and \(SD[H_G]\) both converge
to zero as \(n\) increases. The choice of \(\sqrt{n}\) as the denominator is
admittedly debatable and somewhat subjective. The argument is that we are willing to
address a certain degree of discrepancy by simply constructing a larger graph, but not
impractically so.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="H_G for random Eugrids" src="figures/rand_hg.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(H_G\) for random Eugrids.
</figcaption>
</figure>
<p>
Here, and in the subsequent experiments with random Eugrids, \(p\) is selected using
<a href="https://en.wikipedia.org/wiki/Brent%27s_method">Brent's method</a> to
minimize the square of the mean of \(H_G\). Nonetheless the standard deviation diverges,
and we can see that random Eugrids fail the Hausdorff dimension test.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="H_G for Gamma-Eugrids" src="figures/gamma_hg.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(H_G\) for \(\Gamma\)-Eugrids.
</figcaption>
</figure>
<p>
\(\Gamma\)-Eugrids show a small bias upwards (i.e. graph eccentricity tends to be greater
that Euclidean eccentricity), but on the whole do quite well here.
</p>
<h3>Geodesic confinement</h3>
<p>
The number of vertices \(N_{geo}\) in the geodesics (shortest paths) between vertices can
be easily seen to grow quadratically as a function of distance for graphs corresponding
to taxicab and chessboard distances; i.e.
$$N_{geo}(u, v) \propto d_G(u, v)^2.$$
Farr and Fink <d-cite bibtex-key="Farr_2019"></d-cite> show that this property holds more
generally, for all doubly-periodic planar graphs. Graphs that exhibit quadratic growth in
\(N_{geo}\) with distance are unsuitable as models of Euclidean geometry, which requires
straight lines. Following <d-cite bibtex-key="Farr_2019"></d-cite> we can quantify the
degree of geodesic confinement by estimating \(\gamma\) such that
$$N_{geo}(u, v) \propto d_G(u, v)^\gamma.$$
As long as \(N_{geo}\) scales according to some exponent \(\gamma < 2\) as \(|V|\)
increases, we will see line-like geodesic bundles in the limit. As a practical matter,
the closer we get to linear scaling (i.e. \(\gamma \approx 1\)), the better.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="N_{geo} exponent for random Eugrids" src="figures/rand_gg.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(\gamma\) s.t. \(N_{geo} \propto d_G^\gamma\) for
random Eugrids.
</figcaption>
</figure>
<figure class="l-body" style="margin-left: 5%;">
<img alt="N_{geo} exponent for Gamma-Eugrids" src="figures/gamma_gg.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(\gamma\) s.t. \(N_{geo} \propto d_G^\gamma\) for
\(\Gamma\)-Eugrids.
</figcaption>
</figure>
<p>
Random and \(\Gamma\)-Eugrids both attain geodesic confinement. <d-footnote> The converged value of
\(\gamma \approx 1.5\) for \(\Gamma\)-Eugrids less than ideal; see <a href="#appendix">the appendix</a>
for an approach that attains ideal geodesic confinement, albeit by abandoning unweighted graph distance
and strict determinism.</d-footnote>
</p>
<h3>Pythagorean theorem</h3>
<p>
If ABC is an equilateral triangle with mid-point M halfway between A and B, then \(d_2(M,
C) / d_2(A, B) = \sqrt{3} / 2\). We can test this empirically by investigating
$$T_G(u, v, w, m) := d_G(m, w) / d_G(u, v) - \sqrt{3} / 2$$
for random equidistant vertices \(u, v, w\) where \(m\) is a vertex midway between \(u\)
and \(v\). As with \(H_G\), we would like to see \(E[T_G]\) and \(SD[T_G]\) both converge
to zero as \(n\) increases.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="T_G for random Eugrids" src="figures/rand_tg.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(T_G\) for random Eugrids.
</figcaption>
</figure>
<p>
Random Eugrids appear to pass the Pythagorean theorem test.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="T_{G} for Gamma Eugrids" src="figures/gamma_tg.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(T_G\) for \(\Gamma\)-Eugrids.
</figcaption>
</figure>
<p>
\(\Gamma\)-Eugrids are even better, with the standard deviation dropping down quite
rapidly as the graph size increases.
</p>
<h3>Axis anisotropy</h3>
<p>
We propose a novel fourth test, specifically for Eugrids. We consider the distribution of
\(A_G(u, v, w, m)\) which is calculated using the same formula as \(T_G\) but with a
different sampling distribution over vertices. Specifically, we constrain the sampling of
\(v\) conditional on \(u\) to satisfy \(x_v = x_u \lor y_v = y_u\). In other words, \(u\)
must be reachable from \(v\) by moving in one of the four cardinal directions.
</p>
<p>
As above, we would like to see \(E[A_G]\) and \(SD[A_G]\) both converge to zero as \(n\)
increases.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="A_G for random Eugrids" src="figures/rand_ag.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(A_G\) for random Eugrids.
</figcaption>
</figure>
<p>
\(E[A_G]\) for random Eugrids converges to zero, but \(SD[A_G]\) does not.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="A_G for Gamma-Eugrids" src="figures/gamma_ag.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(A_G\) for \(\Gamma\)-Eugrids.
</figcaption>
</figure>
<p>
\(\Gamma\)-Eugrids demonstrate axis anisotropy that decreases as the size of the graph
grows.
</p>
<h2>Origins and Outlook</h2>
<p>
I was showing my son how to make a glider
in <a href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">Conway's Game of
Life</a>, and mentioned in passing that gliders could only move in four different
directions<d-footnote>There are patterns that move in
<a href=https://conwaylife.com/wiki/Sir_Robin>other directions</a> of course, but every
pattern has a particular set of four different directions that it can move
in.</d-footnote>. This reminded me that we do not appear to live inside of a vast
cellular automaton or similar, and to wonder anew why not. Under reasonable
assumptions<d-cite bibtex-key="Schmidhuber_1997"></d-cite>, we apparently ought to.
</p>
<p>
The most readily apparent discrepancy between our observations and the cellular style of
computation is of course isotropy; a secondary discrepancy is the apparent randomness
<d-cite bibtex-key="Schmidhuber_2006"></d-cite> of certain experimental outcomes. This
led me to wonder how far I could get towards isotropic Euclidean space, in a setting
reminiscent of the Game of Life, with a two-dimensional square grid, unweighted graph
distance, and strict determinism.
</p>
<p>
I would say that I got pretty far, all things considered, but not all the way. In terms
of the empirical results, geodesic confinement is certainly the weakest point; I failed
to make any substantive headway here without <a href="#appendix">abandoning</a> both
unweighted graph distance, <i>and</i> strict determinism. I am also disappointed on the
theoretical side by my failure to make progress towards characterizing the emergence of
approximately Euclidean space from lower-level processes,
as <d-cite bibtex-key="Egan_2002,Farr_2019"></d-cite> have done. The \(\Gamma\)-Eugrid
heuristic is defined <i>in terms</i> of the Euclidean metric.
</p>
<p>
On the positive side, the approach is quite nice computationally <d-footnote>Source code
in <a href=https://julialang.org/>Julia</a> is available
<a href=https://github.com/moshelooks/eugrid/>here</a>.</d-footnote> and all metrics show
a discrete model of the Euclidean plane that becomes increasingly accurate as the graph
grows. The circles are pretty.
</p>
<figure class="l-body" style="margin-top: 0%;">
<img alt="Eugrid Enso" src="figures/eugrid_enso.png">
</figure>
</d-article>
<d-appendix>
<h3 id="appendix">Appendix: Hacking Geodesic Confinement with Infinitesimally Disordered Distances</h3>
<p>
Why do \(\Gamma\)-Eugrids not attain better geodesic confinement? Recall that the
diagonals are aperiodic; the negative results of <d-cite bibtex-key="Farr_2019"></d-cite>
for periodic grids do not apply. Yet it remains possible that the presence of a regular
background grid nonetheless somehow causes a blowup in the number of shortest paths. Here
we show that this is not the cases, by presenting a hack that retains the regular
background grid while attaining ideal geodesic confinement. An elegant approach remains
elusive, however.
</p>
<figure class="l-body" style="margin-left: 10%;">
<img alt="Failed geodesic confinement"
src="figures/geodesic_fail.png" style="width: 80%;">
<figcaption style="width: 80%;">
An illustration of poor geodesic confinement with a \(\Gamma\)-Eugrid. Endpoints are
colored gray, other vertices in geodesics are colored black.
</figcaption>
</figure>
<p>
Thus far we have assumed an unweighted graph, where the diagonal edge length equals the
length of horizontal and vertical edges. Let's try something else:
</p>
<ul>
<li>
The “unit length” of horizontal and vertical edges shall be \((1, 0)\).
</li>
<li>
The length of every diagonal edge shall be \((1, x)\), where \(x\) is drawn uniformly
at random from \(\{1, 2 \ldots 255\}\).
</li>
<li>
Distances are summed elementwise; if \(d_G(u, v) = (l_1, \Delta_1)\) and \(d_G(v, w) =
(l_2, \Delta_2)\) and \(v\) is on a shortest path between \(u\) and \(w\), then
\(d_G(u, w) = (l_1 + l_2, \Delta_1 + \Delta_2)\).
</li>
<li>Distances and are compared
<a href="https://en.wikipedia.org/wiki/Lexicographic_order">lexicographically</a>.
</li>
</ul>
<figure class="l-body" style="margin-left: 10%;">
<img alt="Successful geodesic confinement"
src="figures/geodesic_win.png" style="width: 80%;">
<figcaption style="width: 80%;">
Excellent geodesic confinement for an infinitesimally disordered
\(\Gamma\)-Eugrid. Endpoints are colored gray, other vertices in geodesics are colored
black.
</figcaption>
</figure>
<p>
This approach works, but can be fairly characterized as a hack. By construction, the only
test metric affected by infinitesimally disordered distances is geodesic confinement.
</p>
<figure class="l-body" style="margin-left: 5%;">
<img alt="N_{geo} exponent for Disordered Gamma-Eugrids"
src="figures/gamma_disordered_gg.svg" style="width: 90%;">
<figcaption style="width: 90%;">
Mean and standard deviation of \(\gamma\) s.t. \(N_{geo} \propto d_G^\gamma\) for
infinitesimally disordered \(\Gamma\)-Eugrids.
</figcaption>
</figure>
<p>
The estimated values of \(\gamma\) are actually <i>less</i> than one, because geodesics
are more confined over longer distances. As the mean distance between vertices increases,
the estimate approaches one.
</p>
<d-footnote-list></d-footnote-list>
<h3>Acknowledgments</h3>
<p>
Thanks to <a href="https://lims.ac.uk/profile/?id=63">Dr. Robert Farr</a> for his
feedback and for sharing his code with me. Thanks
to <a href="https://www.linkedin.com/in/adam-earle-5b0b7a15a/">Dr. Adam Earle</a>
for suggesting the illustration of small circular arcs.
</p>
<d-bibliography><script type="text/bibtex">
@article{Farr_2019,
title={Phase transition creates the geometry of the continuum from discrete space},
volume={100},
ISSN={2470-0053},
url={http://dx.doi.org/10.1103/PhysRevE.100.022308},
DOI={10.1103/physreve.100.022308},
number={2},
journal={Physical Review E},
publisher={American Physical Society (APS)},
author={Farr, Robert S. and Fink, Thomas M. A.},
year={2019},
month={Aug}
}
@article{Fritz_2013,
title={Velocity polytopes of periodic graphs and a no-go theorem for digital physics},
volume={313},
ISSN={0012-365X},
url={http://dx.doi.org/10.1016/j.disc.2013.02.010},
DOI={10.1016/j.disc.2013.02.010},
number={12},
journal={Discrete Mathematics},
publisher={Elsevier BV},
author={Fritz, Tobias},
year={2013},
month={Jun},
pages={1289–1301}
}
@book{Egan_2002,
title={Schild's Ladder},
author={Egan, Greg},
year={2002},
publisher={Gollancz},
url={https://www.gregegan.net/SCHILD/SCHILD.html}
}
@incollection{Schmidhuber_1997,
author={J. Schmidhuber},
title={A computer scientist's view of life, the universe, and everything},
booktitle={Foundations of Computer Science: Potential - Theory - Cognition},
editor={C. Freksa and M. Jantzen and R. Valk},
publisher={Lecture Notes in Computer Science, Springer, Berlin},
volume={1337},
pages={201-208},
ISSN={ISSN 0302-9743},
ISBN={3-540-63746-X},
year={1997},
url={https://arxiv.org/pdf/quant-ph/9904050.pdf}
}
@article{Schmidhuber_2006,
author={J. Schmidhuber},
title={Randomness in physics},
journal={Nature},
volume={439},
number={3},
note={Correspondence},
pages={392},
year={2006},
url={https://people.idsia.ch/~juergen/randomness.html}
}
</script></d-bibliography>
<d-citation-list></d-citation-list>
</d-appendix>
</body>