2026-07-23T06:16:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23198 2025-10-02T12:42:43Z ddc:004 open_access

Non-Euclidean Erdős-Anning Theorems Eppstein, David integer distances additively weighted Voronoi diagrams convex distance functions Riemannian manifolds geodesic distance The Erdős-Anning theorem states that every point set in the Euclidean plane with integer distances must be either collinear or finite. More strongly, for any (non-degenerate) triangle of diameter δ, at most O(δ²) points can have integer distances from all three triangle vertices. We prove the same results for any strictly convex distance function on the plane, and analogous results for every two-dimensional complete Riemannian manifold of bounded genus and for geodesic distance on the boundary of every three-dimensional Euclidean convex set. As a consequence, we resolve a 1983 question of Richard Guy on the equilateral dimension of Riemannian manifolds. Our proofs are based on the properties of additively weighted Voronoi diagrams of these distances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Eppstein 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.46 urn:nbn:de:0030-drops-231983 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.46 eng https://creativecommons.org/licenses/by/4.0/legalcode