The Delaunay tetrahedralization from Delaunay triangulated surfaces.

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 211
  • Download : 0
Given a surface mesh F in R 3 with vertex set S and consisting of Delaunay triangles, we want to construct the Delaunay tetrahedralization of S.We present an algorithm which constructs the Delaunay tetrahedralization of S given a bounded degree spanning subgraph T of F. It accelerates the incremental Delaunay triangulation construction by exploiting the connectivity of the points on the surface. If the expected size of the Delaunay triangulation is linear, we prove that our algorithm runs in O(n log* n) expected time, speeding up the standard randomized incremental Delaunay triangulation algorithm, which is O(n log n) expected time in this case.We discuss how to find a bounded degree spanning subgraph T from surface mesh F and give a linear time algorithm which obtains a spanning subgraph from any triangulated surface with genus g with maximum degree at most 12g for g>0 or three for g=0.
Issue Date

SCG '02 Proceedings of the eighteenth annual symposium on Computational geometry , pp.145 - 150

Appears in Collection
CS-Conference Papers(학술회의논문)
Files in This Item
There are no files associated with this item.


  • mendeley


rss_1.0 rss_2.0 atom_1.0