License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2018.24
URN: urn:nbn:de:0030-drops-87375
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8737/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M. ; Skrepetos, Dimitrios

Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs

pdf-format:
LIPIcs-SoCG-2018-24.pdf (0.5 MB)

Abstract

We present the first near-linear-time (1 + epsilon)-approximation algorithm for the diameter of a weighted unit-disk graph of n vertices, running in O(n log^2 n) time, for any constant epsilon>0, improving the near-O(n^{3/2})-time algorithm of Gao and Zhang [STOC 2003]. Using similar ideas, we can 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 also obtain 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 thus the near-cubic preprocessing bound by Roditty and Segal [SODA 2007].

BibTeX - Entry

@InProceedings{chan_et_al:LIPIcs:2018:8737,
  author =	{Timothy M. Chan and Dimitrios Skrepetos},
  title =	{{Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8737},
  URN =		{urn:nbn:de:0030-drops-87375},
  doi =		{10.4230/LIPIcs.SoCG.2018.24},
  annote =	{Keywords: shortest paths, distance oracles, unit-disk graphs, planar graphs}
}

Keywords: shortest paths, distance oracles, unit-disk graphs, planar graphs
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI