DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.101

Improved Algorithms for Distance Selection and Related Problems

Authors: Haitao Wang and Yiming Zhao

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer 1 ≤ k ≤ binom(n,2), the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in O(n^{4/3} log² n) time [Katz and Sharir, 1997]. In this paper, we improve their algorithm to O(n^{4/3} log n) time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work [Avraham, Filtser, Kaplan, Katz, and Sharir, 2015] by a factor of roughly log²(m+n) (resp., (m+n)^ε), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future.

Cite as

Haitao Wang and Yiming Zhao. Improved Algorithms for Distance Selection and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ESA.2023.101,
  author =	{Wang, Haitao and Zhao, Yiming},
  title =	{{Improved Algorithms for Distance Selection and Related Problems}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{101:1--101:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.101},
  URN =		{urn:nbn:de:0030-drops-187544},
  doi =		{10.4230/LIPIcs.ESA.2023.101},
  annote =	{Keywords: Geometric optimization, distance selection, Fr\'{e}chet distance, range searching}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2022.82

Computing the Minimum Bottleneck Moving Spanning Tree

Authors: Haitao Wang and Yiming Zhao

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

Given a set P of n points that are moving in the plane, we consider the problem of computing a spanning tree for these moving points that does not change its combinatorial structure during the point movement. The objective is to minimize the bottleneck weight of the spanning tree (i.e., the largest Euclidean length of all edges) during the whole movement. The problem was solved in O(n²) time previously [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]. In this paper, we present a new algorithm of O(n^{4/3} log³ n) time.

Cite as

Haitao Wang and Yiming Zhao. Computing the Minimum Bottleneck Moving Spanning Tree. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.MFCS.2022.82,
  author =	{Wang, Haitao and Zhao, Yiming},
  title =	{{Computing the Minimum Bottleneck Moving Spanning Tree}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{82:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.82},
  URN =		{urn:nbn:de:0030-drops-168801},
  doi =		{10.4230/LIPIcs.MFCS.2022.82},
  annote =	{Keywords: minimum spanning tree, moving points, unit-disk range emptiness query, dynamic data structure}
}

Search Results

Documents authored by Zhao, Yiming

Improved Algorithms for Distance Selection and Related Problems

Abstract

Cite as

Computing the Minimum Bottleneck Moving Spanning Tree

Abstract

Cite as

Thanks for your feedback!

Could not send message