THE STABILITY OF DELAUNAY TRIANGULATIONS

被引：12
|
作者：
Boissonnat, Jean-Daniel [1 ]
Dyer, Ramsay [1 ]
Ghosh, Arijit [1 ]
机构：
[1] INRIA Sophia Antipolis, F-06902 Sophia Antipolis, France
来源：
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 2013年 / 23卷 / 4-5期
关键词：
Delaunay triangulation; stability; simplex quality;
D O I：
10.1142/S0218195913600078
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of delta-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged.
引用
收藏
页码：303 / 333
页数：31
相关论文
共 50 条
  • [31] On the stretch factor of Delaunay triangulations of points in convex position
    Cui, Shiliang
    Kanj, Iyad A.
    Xia, Ge
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2011, 44 (02): : 104 - 109
  • [32] Single-step creation of localized Delaunay triangulations
    Filipe Araujo
    Luís Rodrigues
    Wireless Networks, 2009, 15 : 845 - 858
  • [33] Improved Upper Bound on the Stretch Factor of Delaunay Triangulations
    Xia, Ge
    COMPUTATIONAL GEOMETRY (SCG 11), 2011, : 264 - 273
  • [34] Delaunay Triangulations of Closed Euclidean d-Orbifolds
    Manuel Caroli
    Monique Teillaud
    Discrete & Computational Geometry, 2016, 55 : 827 - 853
  • [35] Upper and Lower Bounds for Online Routing on Delaunay Triangulations
    Bonichon, Nicolas
    Bose, Prosenjit
    De Carufel, Jean-Lou
    Perkovic, Ljubomir
    van Renssen, Andre
    DISCRETE & COMPUTATIONAL GEOMETRY, 2017, 58 (02) : 482 - 504
  • [36] A FRONTAL APPROACH FOR INTERNAL NODE GENERATION IN DELAUNAY TRIANGULATIONS
    MULLER, JD
    ROE, PL
    DECONINCK, H
    INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN FLUIDS, 1993, 17 (03) : 241 - 255
  • [37] Insert and delete algorithms for maintaining dynamic Delaunay triangulations
    Devijver, Pierre A.
    Dekesel, Michel
    PATTERN RECOGNITION LETTERS, 1982, 1 (02) : 73 - 77
  • [38] A note on point location in delaunay triangulations of random points
    Devroye, L
    Mucke, EP
    Zhu, BH
    ALGORITHMICA, 1998, 22 (04) : 477 - 482
  • [39] The Lifting Projection of Convex Polyhedra for Finding Delaunay Triangulations
    Phan Thanh An
    Nam Dung Hoang
    Nguyen Kieu Linh
    JOURNAL OF CONVEX ANALYSIS, 2022, 29 (01) : 143 - 156
  • [40] Upper and Lower Bounds for Online Routing on Delaunay Triangulations
    Bonichon, Nicolas
    Bose, Prosenjit
    De Carufel, Jean-Lou
    Perkovic, Ljubomir
    van Renssen, Andre
    ALGORITHMS - ESA 2015, 2015, 9294 : 203 - 214
12345