Delaunay graphs are almost as good as complete graphs (Q584279)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Delaunay graphs are almost as good as complete graphs
scientific article

    Statements

    Delaunay graphs are almost as good as complete graphs (English)
    0 references
    0 references
    0 references
    0 references
    1990
    0 references
    Let S be a set of N points in the plane and let DT(S) be the graph of the Delaunay triangulation of S. For all points a and b of S, let d(a,b) be the Euclidean distance from a to b and let DT(a,b) be the length of the shortest path in DT(S) from a to b. We show that there is a constant c \((\leq ((1+\sqrt{5})/2)\pi \approx 5.08)\) independent of S and N such that \(\frac{DT(a,b)}{d(a,b)}<c.\)
    0 references
    Delaunay triangulation
    0 references
    Euclidean distance
    0 references
    shortest path
    0 references
    0 references

    Identifiers