Maintenance of a piercing set for intervals with applications
Maintenance of a piercing set for intervals with applications
复制标题
DOI：
10.1007/s00453-002-1006-1
复制
发表时间：
2003-05-01
期刊：
影响因子：
1.1
通讯作者：
Segal, M
中科院分区：
文献类型：
--
作者：
Katz, MJ;Nielsen, F;Segal, M
提出了一种线性大小的动态数据结构，它使我们能够在O(c(S)log\S\)时间内计算出一个新的最小穿孔集，其中c(S)是新的最小穿孔集的大小。我们还说明了如何为S保持一个穿孔集，其大小至多(1+epsilon)c(S)，对于小于或等于1的0<；epsilon，在(O)超过bar((logS/epsilon))的每次更新的摊销时间内。然后应用这些结果得到以下三个问题的有效解：(I)射手定位问题，(Ii)计算圆上圆弧的最小穿孔集，(Iii)动态维护d维点集的盒覆盖。
We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c(S) log \S\), where c(S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1 + epsilon)c(S), for 0 < epsilon less than or equal to 1, in (O) over bar((log\S\)/epsilon) amortized time per update. We then apply these results to obtain efficient solutions to the following three problems: (i) the shooter location problem, (ii) computing a minimum piercing set for arcs on a circle, and (iii) dynamically maintaining a box cover for a d-dimensional point set.