The Euclidean distance geometry (EDG) problem is a crucial machine learning task that appears in many applications. Utilizing the pairwise Euclidean distance information of a given point set, EDG reconstructs the configuration of the point system. When only partial distance information is available, matrix completion techniques can be incorporated to fill in the missing pairwise distances. In this paper, we propose a novel dual basis Riemannian gradient descent algorithm, coined RieEDG, for the EDG completion problem. The numerical experiments verify the effectiveness of the proposed algorithm. In particular, we show that RieEDG can precisely reconstruct various datasets consisting of 2- and 3-dimensional points by accessing a small fraction of pairwise distance information.
more »
« less
Non-Euclidean Erdős-Anning Theorems
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.
more »
« less
- Award ID(s):
- 2212129
- PAR ID:
- 10688186
- Editor(s):
- Aichholzer, Oswin; Wang, Haitao
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Volume:
- 332
- ISSN:
- 1868-8969
- ISBN:
- 978-3-95977-370-6
- Page Range / eLocation ID:
- 46:1-46:15
- Subject(s) / Keyword(s):
- integer distances additively weighted Voronoi diagrams convex distance functions Riemannian manifolds geodesic distance Theory of computation → Computational geometry
- Format(s):
- Size: 15 pages; 1548818 bytes Other: application/pdf
- Size(s):
- 15 pages 1548818 bytes
- Right(s):
- Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The Euclidean distance geometry (EDG) problem is a crucial machine learning task that appears in many applications. Utilizing the pairwise Euclidean distance information of a given point set, EDG reconstructs the configuration of the point system. When only partial distance information is available, matrix completion techniques can be incorporated to fill in the missing pairwise distances. In this paper, we propose a novel dual basis Riemannian gradient descent algorithm, coined RieEDG, for the EDG completion problem. The numerical experiments verify the effectiveness of the proposed algorithm. In particular, we show that RieEDG can precisely reconstruct various datasets consisting of 2- and 3-dimensional points by accessing a small fraction of pairwise distance information.more » « less
-
Abstract We study unknottedness for free boundary minimal surfaces in a three-dimensional Riemannian manifold with nonnegative Ricci curvature and strictly convex boundary, and for self-shrinkers in the three-dimensional Euclidean space. For doing so, we introduce the concepts of boundary graph for free boundary minimal surfaces and of graph at infinity for self-shrinkers. We prove that these surfaces are unknotted in the sense that any two such surfaces with isomorphic boundary graph or graph at infinity are smoothly isotopic.more » « less
-
Abstract We give a necessary condition on a geodesic in a Riemannian manifold that can run in some convex hypersurface.As a corollary, we obtain peculiar properties that hold true for every convex set in any generic Riemannian manifold ( M , g ) {(M,g)} .For example, if a convex set in ( M , g ) {(M,g)} is bounded by a smooth hypersurface, then it is strictly convex.more » « less
-
For a polygon P with holes in the plane, we denote by ϱ(P) the ratio between the geodesic and the Euclidean diameters of P. It is shown that over all convex polygons with h convex holes, the supremum of ϱ(P) is between Ω(h1/3) and O(h1/2) . The upper bound improves to O(1+min{h3/4Δ,h1/2Δ1/2}) if every hole has diameter at most Δ⋅diam2(P) ; and to O(1) if every hole is a fat convex polygon. Furthermore, we show that the function g(h)=supPϱ(P) over convex polygons with h convex holes has the same growth rate as an analogous quantity over geometric triangulations with h vertices when h→∞more » « less
An official website of the United States government

