论文标题
计算最小瓶颈移动跨越树
Computing the Minimum Bottleneck Moving Spanning Tree
论文作者
论文摘要
鉴于在飞机上移动的$ n $点的集合$ p $，我们考虑了为这些移动点计算生成树的问题，这些问题不会在点移动期间改变其组合结构。目的是在整个运动过程中最大程度地减少生成树的瓶颈重量（即所有边缘的最大欧几里得长度）。该问题以前在$ O（n^2）$之前解决[Akitaya，Biniaz，Bose，de Carufel，Maheshwari，Silveira和Smid，Wads 2021]。在本文中，我们提出了$ o（n^{4/3} \ log^3 n）$时间的新算法。
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^2)$ 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^3 n)$ time.
