Most finite point sets in the plane have dilation \(>1\) (Q2256585)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Most finite point sets in the plane have dilation \(>1\)
scientific article

    Statements

    Most finite point sets in the plane have dilation \(>1\) (English)
    0 references
    0 references
    0 references
    0 references
    19 February 2015
    0 references
    Let \(S\) be a finite point set in the plane. Consider a geometric graph \(T=(V,E)\) drawn in the plane, such that its vertex set contains \(S\). The dilation of a pair of vertices in \(T\) is the minimum sum of lengths of edges along paths connecting them in \(T\) divided by the Euclidean distance of the pair of vertices. The dilation of \(T\) is the maximum dilation of a pair of vertices. David Eppstein characterized triangulations with dilation 1. Call a point set \(S\) special, if it is contained as a subset of the vertex set of some of Eppstein's triangulations. The main result of the paper states that if a finite point set \(S\) is not special, then there exists a \(\Delta(S)>1\) number, such that for any geometric graph \(T=(V,E)\) drawn in the plane, such that its vertex set contains \(S\), the dilation of the graph \(T\) exceeds \(\Delta(S)\).
    0 references
    0 references
    computational geometry
    0 references
    geometric graph
    0 references
    dilation
    0 references
    detour
    0 references
    spanning ratio
    0 references
    stretch factor
    0 references
    0 references