Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.82
URN: urn:nbn:de:0030-drops-168801
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16880/
Wang, Haitao ; Zhao, Yiming
Computing the Minimum Bottleneck Moving Spanning Tree
| pdf-format: |
|
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.
BibTeX - Entry
@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/opus/volltexte/2022/16880},
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}
}
| Keywords: | minimum spanning tree, moving points, unit-disk range emptiness query, dynamic data structure | |
| Seminar: | 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 22.08.2022 |
