Dynamic Convex Hulls under Window-Sliding Updates
Dynamic Convex Hulls under Window-Sliding Updates
复制标题
DOI：
10.48550/arxiv.2305.08055
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Haitao Wang
中科院分区：
文献类型：
--
作者：
Haitao Wang
我们考虑在以下特殊的插入和删除顺序（称为{\ em em窗口斜线更新}）下，动态维护飞机上集合点的凸面的问题： $ s $的点并删除$ s $的最左点。我们提出了一个$ o（| s |）$ - 空间数据结构，可以处理$ O（1）$摊销时间中的每个更新，以便可以回答$ s $的凸面上的标准二进制搜索查询在$ o（\ log h）$时间中，其中$ h $是$ s $的凸壳的顶点的数量，凸壳本身可以以$ o（h）$时间输出。
We consider the problem of dynamically maintaining the convex hull of a set $S$ of points in the plane under the following special sequence of insertions and deletions (called {\em window-sliding updates}): insert a point to the right of all points of $S$ and delete the leftmost point of $S$. We propose an $O(|S|)$-space data structure that can handle each update in $O(1)$ amortized time, such that standard binary-search-based queries on the convex hull of $S$ can be answered in $O(\log h)$ time, where $h$ is the number of vertices of the convex hull of $S$, and the convex hull itself can be output in $O(h)$ time.