Delaunay Decompositions Minimizing Energy of Weighted Toroidal Graphs

58E11; 58E20; Delaunay decomposition; Dirichlet energy; Maxwell–Cremona correspondence; Primary: 52C25; Secondary: 82B99; Tutte embedding; Theoretical Computer Science; Geometry and Topology; Discrete Mathematics and Combinatorics; Computational Theory and Mathematics

Abstract :

[en] Given a weighted graph on a torus, each realization to a Euclidean torus is associated with the Dirichlet energy. By minimizing the energy over all possible Euclidean structures and over all realizations within a fixed homotopy class, one obtains a harmonic map into an optimal Euclidean torus. We show that only with this optimal Euclidean structure, the harmonic map and the edge weights are induced from a weighted Delaunay decomposition.

Disciplines :

Mathematics

Author, co-author :

LAM, Wai Yeung ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Mathematics (DMATH)

External co-authors :

Language :

English

Title :

Delaunay Decompositions Minimizing Energy of Weighted Toroidal Graphs

Publication date :

2024

Journal title :

Discrete and Computational Geometry

ISSN :

0179-5376

eISSN :

1432-0444

Publisher :

Springer

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://link.springer.com/content/pdf/10.1007/s00454-024-00699-x.pdf

FnR Project :

FNR14766753 - CoSH - Convex Surfaces In Hyperbolic Geometry, 2020 (01/09/2021-31/08/2024) - Jean-marc Schlenker

Funders :

Fonds National de la Recherche Luxembourg
Chinese University of Hong Kong

Funding text :

The author was partially supported by the FNR grant CoSH O20/14766753 and the Institute of Mathematical Sciences at The Chinese University of Hong Kong.

Available on ORBilu :

since 02 April 2025

Statistics

Number of views

42 (1 by Unilu)

Number of downloads

32 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

WoS citations^™

Bibliography

A. Bobenko M. Skopenkov Discrete Riemann surfaces: linear discretization and its convergence J. Reine Angew. Math. 2016 720 217 250 3565974
C. Borcea I. Streinu Liftings and stresses for planar periodic frameworks Discrete Comput. Geom. 2015 53 4 747 782 3341577
Y. Colin de Verdière Comment rendre géodésique une triangulation d’une surface? Enseign. Math. (2) 1991 37 3–4 201 212 1151746
Erickson, J., Lin, P.: A toroidal Maxwell–Cremona–Delaunay correspondence. In: Cabello, S., Chen, D.Z. (eds.) 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 164, pp. 40:1–40:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl (2020). https://doi.org/10.4230/LIPIcs.SoCG.2020.40
D. Glickenstein A monotonicity property for weighted Delaunay triangulations Discrete Comput. Geom. 2007 38 4 651 664 2365828
D. Glickenstein Discrete conformal variations and scalar curvature on piecewise flat two- and three-dimensional manifolds J. Differ. Geom. 2011 87 2 201 237 2788656
S.J. Gortler C. Gotsman D. Thurston Discrete one-forms on meshes and applications to 3D mesh parameterization Comput. Aid. Geom. Des. 2006 23 2 83 112 2189438
Gu, X., Yau, S.-T.: Global conformal surface parameterization. In: Kobbelt, L., Schroeder, P., Hoppe, H. (eds.) Eurographics Symposium on Geometry Processing. The Eurographics Association (2003). https://doi.org/10.2312/SGP/SGP03/127-137
T. Kajigaya R. Tanaka Uniformizing surfaces via discrete harmonic maps Ann. H. Lebesgue 2021 4 1767 1807 4353977
R. Kenyon The Laplacian and Dirac operators on critical planar graphs Invent. Math. 2002 150 2 409 439 1933589
Kenyon, R., Lam, W.Y., Ramassamy, S., Russkikh, M.: Dimers and circle patterns. Ann. Sci. Éc. Norm. Supér. (4) 55 (3), 865–903 (2022). https://doi.org/10.24033/asens.2507
R.W. Kenyon D.B. Wilson Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs J. Am. Math. Soc. 2015 28 4 985 1030 3369907
M. Kotani T. Sunada Standard realizations of crystal lattices via harmonic maps Trans. Am. Math. Soc. 2001 353 1 1 20 1783793
W.Y. Lam Quadratic differentials and circle patterns on complex projective tori Geom. Topol. 2021 25 2 961 997 4251440
Lam, W.Y.: Discrete harmonic maps between hyperbolic surfaces. arXiv Preprint (2024). arXiv:2405.02205
Lam, W.Y.: Space of circle patterns on tori and its symplectic form. arXiv Preprint (2024). arXiv:2406.06733
Lam, W.Y., Pinkall, U.: Holomorphic vector fields and quadratic differentials on planar triangular meshes. In: Advances in Discrete Differential Geometry, pp. 241–265. Springer, Berlin (2016)
Lovász, L.: Discrete analytic functions: an exposition. In: Surveys in Differential Geometry. Surv. Differ. Geom., vol. 9, pp. 241–273. Int. Press, Somerville (2004). https://doi.org/10.4310/SDG.2004.v9.n1.a7
J.C. Maxwell On reciprocal figures, frames, and diagrams of forces Trans. R. Soc. Edinb. 1870 26 1 1 40
C. Mercat Discrete Riemann surfaces and the Ising model Commun. Math. Phys. 2001 218 1 177 216 1824204
U. Pinkall K. Polthier Computing discrete minimal surfaces and their conjugates Exp. Math. 1993 2 1 15 36 1246481
S. Rippa Minimal roughness property of the Delaunay triangulation Comput. Aid. Geom. Des. 1990 7 6 489 497 1079398
B.A. Springborn A variational principle for weighted Delaunay triangulations and hyperideal polyhedra J. Differ. Geom. 2008 78 2 333 367 2394026
J.C. Urschel L.T. Zikatanov Discrete trace theorems and energy minimizing spring embeddings of planar graphs Linear Algebra Appl. 2021 609 73 107 4146456
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995). https://doi.org/10.1007/978-1-4613-8431-1