## Abstract

We present the first near-linear-time algorithm that computes a (1 + ε)- approximation of the diameter of a weighted unit-disk graph of n vertices. Our algorithm requires O (n log^{2} n) time for any constant ε > 0, so we considerably improve upon the near-O (n^{3/2}) -time algorithm of Gao and Zhang [17]. Using similar ideas we develop (1+ε)- approximate distance oracles of O (1) query time with a likewise improvement in the preprocessing time, specifically from near O (n^{3/2}) to O (n log^{3} n). We also obtain similar new results for a number of related problems in the weighted unit-disk graph metric such as the radius and the bichromatic closest pair. As a further application we employ our distance oracle, along with additional ideas, to solve the (1 + ε)-approximate all-pairs bounded-leg shortest paths (apBLSP) problem for a set of n planar points. Our data structure requires O (n^{2} log n) space, O (log log n) query time, and nearly O (n^{2:579}) preprocessing time for any constant ε > 0, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal [31].

Original language | English (US) |
---|---|

Pages (from-to) | 3-20 |

Number of pages | 18 |

Journal | Journal of Computational Geometry |

Volume | 10 |

Issue number | 2 |

DOIs | |

State | Published - 2019 |

## ASJC Scopus subject areas

- Geometry and Topology
- Computer Science Applications
- Computational Theory and Mathematics