Delaunay triangulation: Difference between revisions

Revision as of 05:38, 9 February 2011

Revision as of 22:14, 9 February 2011

Line 24:

*The union of all simplices in the triangulation is the convex hull of the points.

*The Delaunay triangulation contains at most ''O''(''n''^{⌈''d''&nbsp;/&nbsp;2⌉}) simplices.<ref>{{cite journal

| last = Seidel

| first = R.

| title = The upper bound theorem for polytopes: an easy proof of its asymptotic version

| journal = Computational Geometry

| volume = 5

| pages = 115–116

| date = 1995

| url = http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYS-3YVD096-C&_user=108429&_coverDate=09%2F30%2F1995&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_acct=C000059713&_version=1&_urlVersion=0&_userid=108429&md5=70a4159a39ed8ab2c6709025aa77d5de&searchtype=a }}</ref>.

*In the plane (''d'' = 2), if there are ''b'' vertices on the convex hull, then any triangulation of the points has at most 2''n''&nbsp;&minus;&nbsp;2&nbsp;&minus;&nbsp;''b'' triangles, plus one exterior face (see [[Euler characteristic]]).

*In the plane, each vertex has on average six surrounding triangles.