Sparse geometric graphs with small dilation
- Aronov, Boris
- de Berg, Mark
- Cheong, Otfried
- Gudmundsson, Joachim
- Haverkort, Herman
- Smid, Michiel
- Vigneron, Antoine
DOIAbstract
AbstractGiven a set S of n points in RD, and an integer k such that 0⩽k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position
Add to ORKG