Complexity of the delaunay triangulation of points on surfaces the smooth case | Zendy

Dominique Attali | Zendy; JeanDaniel Boissonnat | Zendy; André Lieutier | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Complexity of the delaunay triangulation of points on surfaces the smooth case

Author(s) -

Dominique Attali,

JeanDaniel Boissonnat,

André Lieutier

Publication year - 2003

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

ISBN - 1-58113-663-3

DOI - 10.1145/777792.777823

Subject(s) - delaunay triangulation , bowyer–watson algorithm , pitteway triangulation , constrained delaunay triangulation , surface triangulation , point set triangulation , minimum weight triangulation , triangulation , ruppert's algorithm , chew's second algorithm , mathematics , surface (topology) , combinatorics , computer science , geometry

It is well known that the complexity of the Delaunay triangulation of N points in R 3, i.e. the number of its faces, can be O (N2). The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface.In this paper, we bound the complexity of the Delaunay triangulation of points distributed on generic smooth surfaces of R 3. Under a mild uniform sampling condition, we show that the complexity of the 3D Delaunay triangulation of the points is O(N log N).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research