Paper Info
Title
An optimal bound for conforming quality triangulations: (extended abstract)
Abstract
This paper shows that for any plane geometric graph G with n vertices, there exists a triangulation T conforms to G , i.e. each edge of G is the union of some edges of T , where T has O(n2) vertices with angles of its triangles measuring no more than (11/15)&pgr;. Additionally, T can be computed in O(n2logn) time. The quadratic bound on the size of its vertex set is within a constant factor of worst case optimal.
Year
DOI
Venue
1994
10.1145/177424.177976
Symposium on Computational Geometry 2013
Keywords
Field
DocType
plane geometric graph,constant factor,worst case optimal,n vertex,quality triangulations,vertex set,geometric graph,polyhedra,surface reconstruction,dynamic programming,triangulation
Geometric graph theory,Discrete mathematics,Combinatorics,Spatial network,Bound graph,Vertex (geometry),Polyhedron,Quadratic equation,Triangulation (social science),Mathematics,Point set triangulation
Conference
ISBN
Citations 
PageRank 
0-89791-648-4
1
0.56
References 
Authors
11
1
Name
Order
Citations
PageRank
Tiow-Seng Tan139827.99