集合覆盖和打点集是组合优化中的基本问题，在离线、在线和动态设置中都有深入研究。我们研究这些问题的几何版本，并提出了新的在线和动态算法。在线版本的集合覆盖（或命中集）中，给出 $m$ 个集合（或 $n$ 个点），在线上一个接一个地到达 $n$ 个点（或 $m$ 个集合）。在动态版本中，点（或集合）既可以到达也可以离开。我们的目标是维护一个集合覆盖（或打点集），同时最小化计算出的解的大小。
针对任意大小（轴对齐）正方形的在线集合覆盖，我们提供了一个紧密的 $O(\log n)$-competitive 算法。在这一设置中，对于命中集，我们提供一个紧密的 $O(\log N)$-competitive 算法，假定所有点在 $[0,N)^{2}$ 内具有整数坐标。在这些设置中，除了已知的任意集合系统的在线算法外，先前没有为任何一种设置知道在线算法。
对于具有 $d$ 维超矩形的动态集合覆盖和命中集，我们可以获得 $(\log m)^{O(d)}$-approximation 算法，更新时间的最坏情况为 $(\log m)^{O(d)}$。这在一定程度上回答了 Chan 等人提出的一个开放性问题 [SODA’22]。先前即使在正方形设置下（针对任何一个问题），也不知道具有多项式对数更新时间的动态算法。我们的主要技术贡献是一种扩展的四叉树方法和一种减少几何集合覆盖实例到具有有限频率的一般集合覆盖实例的技术。
论文链接：http://arxiv.org/pdf/2303.09524v1
更多计算机论文：http://cspaper.cn/