DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2018.24

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

Authors: Timothy M. Chan and Dimitrios Skrepetos

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

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].

Cite as

Timothy M. Chan and Dimitrios Skrepetos. Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2018.24,
  author =	{Chan, Timothy M. and Skrepetos, Dimitrios},
  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 =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.24},
  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}
}

Document

DOI: 10.4230/LIPIcs.ESA.2017.25

Faster Approximate Diameter and Distance Oracles in Planar Graphs

Authors: Timothy M. Chan and Dimitrios Skrepetos

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We present an algorithm that computes a (1+varepsilon)-approximation of the diameter of a weighted, undirected planar graph of n vertices with non-negative edge lengths in O(nlog n(log n + (1/varepsilon)^5)) expected time, improving upon the O(n((1/varepsilon)^4 log^4(n) + 2^{O(1/varepsilon)}))-time algorithm of Weimann and Yuster [ICALP 2013]. Our algorithm makes two improvements over that result: first and foremost, it replaces the exponential dependency on 1/varepsilon with a polynomial one, by adapting and specializing Cabello's recent abstract-Voronoi-diagram-based technique [SODA 2017] for approximation purposes; second, it shaves off two logarithmic factors by choosing a better sequence of error parameters during recursion. Moreover, using similar techniques, we improve the (1+varepsilon)-approximate distance oracle of Gu and Xu [ISAAC 2015] by first replacing the exponential dependency on 1/varepsilon on the preprocessing time and space with a polynomial one and second removing a logarithmic factor from the preprocessing time.

Cite as

Timothy M. Chan and Dimitrios Skrepetos. Faster Approximate Diameter and Distance Oracles in Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ESA.2017.25,
  author =	{Chan, Timothy M. and Skrepetos, Dimitrios},
  title =	{{Faster Approximate Diameter and Distance Oracles in Planar Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.25},
  URN =		{urn:nbn:de:0030-drops-78382},
  doi =		{10.4230/LIPIcs.ESA.2017.25},
  annote =	{Keywords: planar graphs, diameter, abstract Voronoi diagrams}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.24

All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time

Authors: Timothy M. Chan and Dimitrios Skrepetos

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

In this paper we study the all-pairs shortest paths problem in (unweighted) unit-disk graphs. The previous best solution for this problem required O(n^2 log n) time, by running the O(n log n)-time single-source shortest path algorithm of Cabello and Jejcic [Comput. Geom., 2015] from every source vertex,where n is the number of vertices. We not only manage to eliminate the logarithmic factor, but also obtain the first (slightly) subquadratic algorithm for the problem, running in O(n^2 sqrt{ frac{log log n}{log n} }) time. Our algorithm computes an implicit representation of all the shortest paths, and, in the same amount of time, can also compute the diameter of the graph.

Cite as

Timothy M. Chan and Dimitrios Skrepetos. All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ISAAC.2016.24,
  author =	{Chan, Timothy M. and Skrepetos, Dimitrios},
  title =	{{All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.24},
  URN =		{urn:nbn:de:0030-drops-67948},
  doi =		{10.4230/LIPIcs.ISAAC.2016.24},
  annote =	{Keywords: unit-disk graphs, all-pairs shortest paths, computational geometry}
}

3 Search Results for "Skrepetos, Dimitrios"

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

Abstract

Cite as

Faster Approximate Diameter and Distance Oracles in Planar Graphs

Abstract

Cite as

All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time

Abstract

Cite as

Thanks for your feedback!

Could not send message