Computing the Minimum Bottleneck Moving Spanning Tree

Haitao Wang

doi:10.1007/s00453-025-01358-0

2025-11-14

PRE

Haitao Wang

Yiming Zhao *

DOI：10.1007/s00453-025-01358-0

原文链接

原文求助

摘要

En 中文

给定平面上一组包含n个移动点点的集合P，我们考虑为这些移动点计算一棵支撑树，该支撑树在点移动过程中不改变其组合结构。目标是在整个移动过程中最小化支撑树的瓶颈权重（即所有边中最大的欧几里得长度）。此前该问题已被解决，计算时间为\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>2)$$\end{document} [Akitaya, Biniaz, Bose, De Carufel, Maheshwari, Silveira, and Smid, WADS 2021]。在本文中，我们提出了一种新的算法，计算时间为\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>{4/3} \log <^>3 n)$$\end{document}。

Keyword:

Minimum spanning tree

Moving points

Unit-disk range emptiness query

Dynamic data structure