The Delaunay triangulation closely approximates the complete Euclidean graph (Q4028874)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 140458
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The Delaunay triangulation closely approximates the complete Euclidean graph |
scientific article; zbMATH DE number 140458 |
Statements
28 March 1993
0 references
complete graph
0 references
planar graph
0 references
Delaunay triangulation
0 references
Voronoi diagram
0 references
shortest path
0 references
Euclidean distance
0 references
0.8852227926254272
0 references
0.8558869361877441
0 references
0.8558869361877441
0 references
The Delaunay triangulation closely approximates the complete Euclidean graph (English)
0 references
[For the entire collection see Zbl 0753.00021.] Let \(S\) be a finite set of points in the plane. The Delaunay triangulation is the graph corresponding to the Voronoi diagram of \(S\). It is shown that for any two points of \(S\) the ratio between the length of the shortest path in the Delaunay triangulation and their Euclidean distance is less than 2.42.
0 references
