PhD Seminar • Algorithms and Complexity — Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk GraphsExport this event to calendar

Wednesday, May 2, 2018 — 1:30 PM EDT

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.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2020 (184)
    1. October (3)
    2. September (21)
    3. August (28)
    4. July (14)
    5. June (18)
    6. May (17)
    7. April (20)
    8. March (16)
    9. February (25)
    10. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)