Sparse geometric graphs with small dilation

Details Sparse geometric graphs with small dilation Sparse geometric graphs with small dilation

2007-02-14

arxiv.org/abs/cs/0702080v2

Computer Science

Computational Geometry

Scientific paper

Given a set S of n points in R^D, 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(n log n). For any k, we also construct planar n-point sets for which any geometric graph with n-1+k edges has dilation Omega(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.

Affiliated with

Also associated with

No associations

Rating

Sparse geometric graphs with small dilation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparse geometric graphs with small dilation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse geometric graphs with small dilation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-209668