THE MATHThree papers.
One is in the city.
We tried three recent results. Only the ones that helped are used. The rest were measured and left out.
USEDAn aperiodic monotile
David Smith, Joseph Samuel Myers, Craig S. Kaplan, Chaim Goodman-Strauss. arXiv 2303.10798, first posted 2023-03-20; journal version DOI 10.5070/C64163843.
Plazas in the city are paved with the hat: one shape that fills the plane but never repeats.
- Covers a 30 m disc with 888 hats: of 18,010 sample points, 0 uncovered and 0 covered twice.
- Building a 22 m patch (494 hats) takes 644 to 831 ms the first time and 17.9 to 26.6 ms after that (3 fresh runs).
Why it is in. It is a real aperiodic tiling, built exactly, and it costs one build per page load.
BENCHMARKED, NOT USEDBreaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin. arXiv 2504.17033, first posted 2025-04-23.
A newer way to find shortest paths that is faster in theory. We built it and raced it against the standard method.
Full shortest-path search from one source, median of the runs. Same answers as the standard method on every run.| Graph | Points / links | Runs | Standard | This paper | Result |
|---|
| random sparse n=10000 out-degree 4 | 10,000 / 39,999 | 7 | 4.38 ms | 76.7 ms | 17.5x slower |
| random sparse n=100000 out-degree 4 | 100,000 / 399,999 | 7 | 86.7 ms | 1,173 ms | 13.5x slower |
| ANOMALY walk graph, seed 20261027, gen 300 (972 buildings) | 112,896 / 1,794,260 | 7 | 62.8 ms | 1,356 ms | 21.6x slower |
| ANOMALY walk graph, seed 20261027, gen 2000 (3694 buildings) | 112,896 / 1,794,260 | 7 | 80.0 ms | 2,067 ms | 25.8x slower |
Why it is out. On the city at generation 2000 (112,896 points, 1,794,260 links) the engine finds one route in 0.33 ms (median of 200 routes). This method works out every destination at once and took 1,796 ms (median of 12 routes). The city only ever needs one route.
BENCHMARKED, NOT USEDUniversal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert E. Tarjan, Jakub Tětek. arXiv 2311.11793, first posted 2023-11-20.
A smarter waiting line for the standard shortest-path method, proven the best possible in theory. We built it and measured it.
Full shortest-path search from one source, median of the runs. Same answers as the standard method on every run.| Graph | Points / links | Runs | Standard | This paper | Result |
|---|
| random sparse n=10000 out-degree 4 | 10,000 / 39,999 | 7 | 4.38 ms | 24.9 ms | 5.7x slower |
| random sparse n=100000 out-degree 4 | 100,000 / 399,999 | 7 | 86.7 ms | 486 ms | 5.6x slower |
| ANOMALY walk graph, seed 20261027, gen 300 (972 buildings) | 112,896 / 1,794,260 | 7 | 62.8 ms | 204 ms | 3.2x slower |
| ANOMALY walk graph, seed 20261027, gen 2000 (3694 buildings) | 112,896 / 1,794,260 | 7 | 80.0 ms | 347 ms | 4.3x slower |
Why it is out. On the city at generation 2000 (112,896 points, 1,794,260 links), one route took 1.21 ms with a plain binary heap and 5.24 ms with this heap (4.3x slower, median of 200 routes).