包围许多点的圆盘的计算问题

《Discrete Applied Mathematics》:Computational aspects of disks enclosing many points

【字体: 大 中 小 】 时间:2026年10月22日 来源:Discrete Applied Mathematics 1.1

编辑推荐:

   摘要 设 $S$ 为平面上 $n$ 个点的集合。我们提出若干不同的算法,用于在 $S$ 中寻找一对点,使得任何包含这对点的圆都必须包含 $S$ 中至少 $cn$ 个点,其中 $c > 0$ 为某个常数。第一个算法是随机化算法,对于一般位置的点,它以 $O(n \log n)$

  

摘要 设 $S$ 为平面上 $n$ 个点的集合。我们提出若干不同的算法,用于在 $S$ 中寻找一对点,使得任何包含这对点的圆都必须包含 $S$ 中至少 $cn$ 个点,其中 $c > 0$ 为某个常数。第一个算法是随机化算法,对于一般位置的点,它以 $O(n \log n)$ 的预期时间找到这样的一对点,其中 $c = 1/2 - \sqrt{1 + 2\alpha}/12$,对任意 $0 < \alpha < 1$ 成立。第二个算法同样针对一般位置的点,时间复杂度为二次,但常数 $c$ 改进为 $1/2 - 1/\sqrt{12} \approx 1/4.7$。第二个算法还可作为子程序,在 $O(n^2 \log n)$ 时间内找到使任何包含该对的圆中点数量最大化的那一对点。我们还考虑了该问题的若干变体。当点集 $S$ 处于凸位置时,我们给出了一个线性时间算法,找到一对点使得任何经过它们的圆都包含 $S$ 中至少 $n/3$ 个点。对于仅关心找到一对点使得该对点的直径圆包含大量点的变体,我们同样有一个线性时间算法,可找到一个包含 $S$ 中至少 $n/3$ 个点的圆。最后,我们将前两个算法推广到点集用两种颜色着色的情形。我们还考虑了将这些算法适应于 $S$ 为简单多边形 $P$ 内部点集的情形,其中"圆"的概念被替换为测地圆。

引言 设 $S$ 为平面上 $n$ 个点的集合。若点 $p \in S$ 位于圆的边界上或圆的内部,则称该圆包含或包围点 $p$。对于任意两个不同的点 $p, q \in S$,我们定义 $C_S(p, q)$ 为最小的整数,使得任何包围 $p$ 和 $q$ 的圆都至少包围 $C_S(p, q)$ 个 $S$ 中的点。设 $\Pi(S)$ 为 $C_S(p, q)$ 在所有点对 $\{p, q\}$ 上的最大值,设 $\Pi(n)$ 为 $\Pi(S)$ 在所有 $n$ 个点的集合 $S$ 上的最小值。寻找 $\Pi(n)$ 精确值的问题由 Neumann-Lara 和 Urrutia [21] 于 1988 年提出。他们证明了 $S$ 中存在一对点,使得任何包含该对的圆都必须包含 $S$ 中至少 $cn$ 个点,其中 $c > 1/60$ 为某个常数。在此后大约一年的时间里,该结果中的常数因子被不断改进,最终 Edelsbrunner 等人 [14] 证明了存在一对点,使得任何包含该对的圆也包含 $S$ 中至少 $n/4.7$ 个点。最近,Bose 等人研究了将问题从平面设置推广到简单多边形设置的情形 [8]。这些结果都证明了存在这样的点对,但均未考虑寻找这样一对点的算法问题。这正是本文的关注焦点。用于证明存在性的许多思想在欧几里得设置和测地设置中都将为我们提供算法。组合问题由 Neumann-Lara 和 Urrutia [21] 于 1988 年提出,他们证明了 $S$ 中存在一对点 $p, q$,具有这样的性质:任何包含 $p$ 和 $q$ 的圆都包含 $S$ 中至少 $\lceil(n-2)/60\rceil$ 个点。他们还定义了 $\overline{\Pi}(n)$ 为 $\Pi(S)$ 在所有凸位置的 $n$ 个点的集合 $S$ 上的最小值,并证明了 $\overline{\Pi}(n) \geq \lceil(n-2)/4\rceil$。此后,Bárány 等人 [7] 将下界改进为 $\Pi(n) \geq n/30$。同时,Hayward 等人 [17] 也研究了该问题,证明了 $\lfloor n/27 \rfloor + 2 \leq \Pi(n) \leq \lceil n/4 \rceil + 1$,以及 $\overline{\Pi}(n) = \lceil n/3 \rceil + 1$。后来 Hayward [16] 将非凸位置点集的下界改进为 $\Pi(n) \geq \lceil 5(n-2)/84 \rceil$。最后,Edelsbrunner 等人 [14] 证明了 $\Pi(n) \geq n - 32 - \sqrt{n-2}/2 - 1/12 = (12 - 1/\sqrt{12})n + O(1) \approx n/4.7$,这是 $\Pi(n)$ 目前最好的下界。Ramos 和 Via?a [25] 给出了相同界的一种替代证明,他们证明了更强的结果:总是存在两个点 $p$ 和 $q$,使得任何以 $p$ 和 $q$ 为边界上点的圆都包含至少 $n/4.7$ 个点,且该圆之外也有至少 $n/4.7$ 个点。Claverol 等人 [11] 利用高阶 Voronoi 图给出了该事实的另一种证明。该问题的变体多年来被不断研究。Akiyama 等人 [3] 证明了存在两个点 $p$ 和 $q$,使得以线段 $pq$ 为直径的圆包围至少 $n/3$ 个点。Bárány 等人 [7] 研究了该问题在 $\mathbb{R}^d$ 中的情形。具体来说,他们证明了对于 $\mathbb{R}^d$ 中 $n$ 个点的集合 $S$,存在 $S$ 的一个大小为 $\lfloor(d+3)/2\rfloor$ 的子集 $T$,使得任何包含 $T$ 的 $d$ 维球都包含 $S$ 中至少 $cn$ 个点,其中 $c > 0$ 为某个常数。Bárány 和 Larman [6] 进一步将该结果从球推广到二次曲面。此外,[11]、[24]、[26] 中还研究了该问题的双色版本,目标是在找到一对异色点对,使得任何包含该对的圆都必须包含大量点。Prodromou [24] 还将该着色版本的问题推广到更高维空间。许多这些变体被 Bose 等人 [8] 从平面推广到包含在简单多边形中的点集。他们证明了给定简单多边形 $P$ 中 $n$ 个点的集合 $S$,存在 $S$ 中的两个点,使得任何以这两个点为边界上点的测地圆都包含 $S$ 中至少 $n/5$ 个点。对于处于测地凸位置的点集,他们证明了存在一对点,使得任何包含该对的测地圆都包含至少 $n/3$ 个点,与欧几里得设置的界相匹配。他们还考虑了直径圆版本和双色版本的问题,以及点在圆内外的版本。在本文中,我们提出了不同的算法,给定 $n$ 个点的集合 $S$,找到一对点使得任何包含这些点的圆都包含 $S$ 中常数量级的点。前两个算法针对一般位置的点集。第一个是随机化算法,在 $O(n \log n)$ 的预期时间内找到一对点 $p$ 和 $q$,使得任何包含 $p$ 和 $q$ 的圆都包含 $S$ 中至少 $cn$ 个点,其中 $c$ 为任意常数 $0 < c < 1/4.7$。该算法运行时间中的常数取决于 $c$ 的值。第二个是二次时间算法,找到一对点 $p$ 和 $q$,使得任何包含 $p$ 和 $q$ 的圆都包含 $S$ 中至少 $n/4.7$ 个点,与 $\Pi(n)$ 目前最好的下界相匹配。第二个算法还可用于在 $O(n^2 \log n)$ 时间内找到使 $C_S(p, q)$ 最大化的那一对点。第三个算法针对凸位置的点集,找到一对点 $p$ 和 $q$,使得任何包含 $p$ 和 $q$ 的圆都包含 $S$ 中至少 $n/3$ 个点,这是 $\overline{\Pi}(n)$ 的最优界。该算法在线性时间内找到这对点。第四个是直径圆版本的算法,在 $O(n)$ 时间内找到两个点 $p$ 和 $q$,使得以 $pq$ 为直径的圆包含 $S$ 中至少 $n/3$ 个点。最后,我们展示了如何修改前两个算法以适用于该问题的双色版本:给定 $n/2$ 个红点和 $n/2$ 个蓝点的集合 $S$,找到一对红蓝点对,使得任何包含该对的圆都包含 $S$ 中至少 $cn$ 个点,其中 $c$ 为某个常数。我们还讨论了这些算法如何推广到简单多边形中的点集。需要格外小心,因为在平面上平凡的许多性质在此设置中变得更加困难。例如,在平面上寻找经过三个点的圆的圆心只需常数时间。在简单多边形中,这样的圆甚至可能不存在。我们将展示如何处理所有出现的困难。

各节概要

背景 在本节中,我们给出算法所需的背景知识,包括平面(欧几里得设置)和简单多边形(测地设置)两个方面。

平面中的算法 在本节中,我们提出三种算法,用于在欧几里得平面中寻找一对点 $p$ 和 $q$,使得 $C_S(p, q) \geq cn$,其中 $c > 0$ 为某个常数。

简单多边形中的算法 在本节中,我们考虑在简单多边形设置中寻找一对 $\{p, q\}$ 使得 $C_S(p, q) \geq cn$ 的问题。在本节中,设 $S$ 为简单多边形 $P$ 内部的 $n$ 个点的集合,其中 $P$ 有 $m$ 个顶点,$r$ 个为反射顶点,$m - r$ 个为凸顶点。我们的算法计算简单多边形内部的最短路径和 $k$ 阶测地 Voronoi 图。给定一个具有 $m$ 个顶点和 $r$ 个反射顶点的简单多边形 $P$,Aichholzer 等人 [2] 证明了可以计算出一个简单多边形 $P'$。

结论 我们提出了若干不同的算法,给定平面上 $n$ 个点的集合 $S$,找到一对点 $p$ 和 $q$ 使得 $C_S(p, q) \geq cn$,其中 $c > 0$ 为某个常数。其中前两个算法针对一般位置的点集。其余算法针对问题的变体:点处于凸位置时、仅关心找到一对点使得该对的直径圆包含大量点时、以及点集为双色时。我们还研究了如何将这些

致谢 G. E. 部分由 MICIU/AEI/10.13039/501100011033 资助的 PID2023-150725NB-I00 基金支持。P. B. 和 T. T. 部分由 NSERC 资助。

Prosenjit Bose | Guillermo Esteban | Tyler Tuttle
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号