Dimitrios
Skrepetos,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
We give the first near-linear-time (1+epsilon)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O(nlog^2 n) time for any constant epsilon>0, considerably improving the near-O(n^{3/2})-time algorithm of Gao and Zhang [STOC 2003]. We can also construct a (1+epsilon)-approximate distance oracle for weighted unit-disk graphs with O(1) query time, with a similar improvement in the preprocessing time, from near O(n^{3/2}) to O(n\log^3 n). We obtain similar new results for a number of other related problems in the weighted unit-disk graph metric, such as the radius and bichromatic closest pair.
As a further application, we use our new distance oracle, along with additional ideas, to solve the (1+epsilon)-approximate all-pairs bounded-leg shortest paths problem for a set of n planar points, with near O(n^{2.579}) preprocessing time, O(n^2\log n) space, and O(\log{\log n}) query time, improving the near-cubic preprocessing bound by Roditty and Segal [SODA 2007].
It is a joint work with my supervisor Timothy M. Chan, and it will be presented in SoCG 2018.