Efficient Embeddings in Exact Arithmetic
ACM Transactions on Graphics · 2023-08 · 42 (4) · 1-17
DOI: 10.1145/3592445 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 26.07.2023. Verfasst von Ugo Finnendahl und 3 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 52 Literaturangaben. Gefördert von: HORIZON EUROPE European Research Council, Berlin Mathematics Research Center MATH+.
Abstract (Originalsprache)
We provide a set of tools for generating planar embeddings of triangulated topological spheres. The algorithms make use of Schnyder labelings and realizers. A new representation of the realizer based on dual trees leads to a simple linear time algorithm mapping from weights per triangle to barycentric coordinates and, more importantly, also in the reverse direction. The algorithms can be implemented so that all coefficients involved are 1 or -1. This enables integer computation, making all computations exact. Being a Schnyder realizer, mapping from positive triangle weights guarantees that the barycentric coordinates form an embedding. The reverse direction enables an algorithm for fixing flipped triangles in planar realizations, by mapping from coordinates to weights and adjusting the weights (without forcing them to be positive). In a range of experiments, we demonstrate that all algorithms are orders of magnitude faster than existing robust approaches.
Förderung
- HORIZON EUROPE European Research Council
- Berlin Mathematics Research Center MATH+
Zitieren
APA
Finnendahl, U., Bogiokas, D., Cervantes, P. R., & Alexa, M. (2023). Efficient Embeddings in Exact Arithmetic. ACM Transactions on Graphics, 42(4), 1-17. https://doi.org/10.1145/3592445
Vancouver
Finnendahl U, Bogiokas D, Cervantes PR, Alexa M. Efficient Embeddings in Exact Arithmetic. ACM Transactions on Graphics. 2023;42(4):1-17. doi:10.1145/3592445
BibTeX
@article{Finnendahl2023,
author = {Finnendahl, Ugo and Bogiokas, Dimitrios and Cervantes, Pablo Robles and Alexa, Marc},
title = {Efficient Embeddings in Exact Arithmetic},
journal = {ACM Transactions on Graphics},
year = {2023},
volume = {42},
number = {4},
pages = {1--17},
doi = {10.1145/3592445}
}
EUVIMED