Robust and Efficient Delaunay triangulations of points on or close to a sphere
Autor: | Caroli, Manuel, Machado Manhães De Castro, Pedro, Loriot, Sebastien, Rouiller, Olivier, Teillaud, Monique, Wormser, Camille |
---|---|
Přispěvatelé: | Geometric computing (GEOMETRICA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Algorithms, Biology, Structure (ABS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science [ETH Zürich] (D-INFK), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), INRIA, ANR-07-BLAN-0319,Triangles,New challenges in triangulations(2007) |
Jazyk: | angličtina |
Rok vydání: | 2009 |
Předmět: |
Sphere
Voronoi Diagram ACM: G.: Mathematics of Computing/G.4: MATHEMATICAL SOFTWARE/G.4.6: Reliability and robustness Exact Geometric Computing Computational Geometry CGAL ACM: D.: Software/D.2: SOFTWARE ENGINEERING/D.2.13: Reusable Software/D.2.13.1: Reusable libraries Computer Science::Computational Geometry Delaunay Triangulation Space of Circles ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems/F.2.2.2: Geometrical problems and computations [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.5: Computational Geometry and Object Modeling/I.3.5.3: Geometric algorithms languages and systems |
Zdroj: | [Research Report] RR-7004, INRIA. 2009 |
Popis: | We propose two approaches for computing the Delaunay triangulation of points on a sphere, or of rounded points close to a sphere, both based on the classic incremental algorithm initially designed for the plane. The space of circles gives the mathematical background for this work. We implemented the two approaches in a fully robust way, building upon existing generic algorithms provided by the cgal library. The effciency and scalability of the method is shown by benchmarks. |
Databáze: | OpenAIRE |
Externí odkaz: |