Probabilistic Killer: 一个关于最近点对假随机做法的小讨论

Background

最近点对问题:给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。

一个广为人知的随机做法是这样的:

我们充分发扬人类智慧:
将所有点全部绕原点旋转同一个角度,然后按 $x$ 坐标排序
根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 $5$ 个点来计算答案
这样速度快得飞起,在 $n=1000000$ 时都可以在 1 s 内卡过

——P1429 平面最近点对(加强版)最高赞题解。

当然,上面这个声称看起来就不对——因为随一次失败概率显然可能很大。之前也有传言这个有类似根号的正确性下界保证,然后我暑假整理模板的时候也相信了这一点,不过,仔细想起来,这是不对的!

当然,不对得并不是很明显,我先和 Chihao 讨论得出了一个构造方法,然后在几何画板上画出来后,发现角度存在非常牛逼的等角关系,交给几何大师证明了一下发现显然对;之后,路过的毛哥哥一语中的,发现构造的点就在一个圆上,然后就发现这个题性质更美妙了。

因此我就出了这个题,放在了 IEEE 21 算法课第一次上机作业的附加题里:

Probabilistic killer

随机化大师博先生认为 Closest pair 一题非常简单,因此他随手设计了如下算法来通过这个题:

​ 将所有点按随机的角度绕原点旋转并按照 $x$ 轴排序后,计算相邻两个点的距离。

为了防止运气太差,博先生的程序实际上会从初始角开始的半平面内均匀尝试 $T$ 次:

  1. 均匀随机地从 $[0, \pi)$ 中选择一个角度 $\theta_0$,作为初始角;
  2. 重复 $T$ 次,将所有点从初始坐标绕原点逆时针旋转 $\theta_k = \theta_0 + \frac {k-1} {T} \pi$ 并按照 $x$ 轴排序,计算相邻两个点之间的距离。
  3. 输出 $T$ 次计算结果中出现过的距离最小值。

霏老师觉得博先生的做法是搞笑的,并请来了你构造数据卡掉博先生的做法。

Input

输入一个数,$T (1 \leq T \leq 400)$,表示博先生的程序此时采用的参数。

Output

你需要按照 Closest pair 一题的输入格式输出一组数据。

输出第一行为一个正整数 $n (2 \leq n \leq 4\times10^5)$,表示点数。

接下来 $n$ 行,第 $i$ 行为用空格隔开的整数 $x_i, y_i (-10^7 \leq x_i, y_i \leq 10 ^ 7)$,表示 $p_i = (x_i, y_i)$。

你的输出中,不应当包含两个坐标完全相同的点。

How do we judge your answer

本题有 $20$ 组测试点,每组测试点 $5$ 分。

对于第 $i$ 组数据,

  1. $T=i ^ 2$;
  2. 你输出的 $n$ 应当满足: $2 \leq n \leq \lfloor 4\times 10^5 / T\rfloor $。$i= 20$ 时,$n \leq 1000$ 。

对于你的输出,我们将采用如下方法进行测试:

  1. 首先使用正确的最近点对算法计算正确答案。
  2. 固定一个隐藏的随机种子 $\mathrm{SEED}_i$,使用随机数生成器生成 $ 20$ 个初始角度运行博先生的程序。
  3. 如果你成功让博先生的程序输出错误至少 $2$ 次,你就赢了。

作为参考,运行一次 $T = 1$ 的正确率降低至 $1 / 500$ 时,你有 $>0.99$ 的概率通过最后一组测试数据。

Constraints

Time Limit: 3s

Memory Limit: 128MB

Sample Input

1

Sample Output

3
0 0
0 1
0 2

Note

很难不发现样例输出(除了格式)是完全错误的:由于 $(1, 2)$ $(2, 3)$ 的距离均为 $1$,因此所有排列均存在相邻两个点距离为 $1$。评测器会非常肯定地拒绝掉这个输入。

请注意,尽管概率测度是 $0$,实际中仍可能存在旋转后 $x$ 坐标相同的点对,此时排序算法可能返回任意顺序。


Solution

题面的最终要求是:用 $n = 1000$ 个点,使得一次运行成功概率低于 $~1/500$。

其实这里也很明显了,意思就是存在一个构造方法,使得用 $n$ 个点构造出 $O(1/n)$ 的 case。

参考做法是这样的:

我们考虑钦定最近点为 $A=(0, -0.5)$ 与 $B=(0, 0.5)$ ,此时最近点对距离为 $1$。

结论:对于任意目标概率 $\varepsilon > 0$,存在一个构造方法,使得只需要使用至多 $1/\varepsilon$ 个实数点,便可将算法一次成功概率降低至 $\varepsilon$。这种构造方法的所有点分布在 $A, B$ 以某个 $y$ 轴上的圆心 $C$ 形成的圆上,并且相邻两个点的圆心角恰为 $\angle ACB=2\pi/\varepsilon$。下图为 $\varepsilon = 0.06$ 时,$y$ 正负区域的前四个点。图中剩余部分是原始构造所使用的辅助线。

下面我们对思路进行解释。

假设对于某个方向 $\theta$ ,在排序后最近点不相邻,那么也就是过 $A, B$ 做 $\theta$ 角度的两条直线之间夹了一个坏点,算法就挂了。

对于任意一个坏点,他能覆盖的实际上是一个角度区间,我们希望用尽量少的点覆盖尽可能大的角度区间。

同时,除了最近点对外,所有点周围 $1$ 的距离内不能有任何其他点。

一个非常直观的想法是:我们围绕这两个点作一个大圆,上面均匀撒一些距离略大于 1 的点,以在每个角度都能干扰到算法。

但是这么做是错的,因为:

  • 对于每个方向上的坏点,越接近原点,那么覆盖的区间越大。大圆太远的话,覆盖区间很小,效果有限;
  • 如果 $\theta$ 贴近 $x$ 轴,那么算法很容易失败;如果 $\theta$ 贴近 $y$ 轴,那么算法很难失败。如果恰好有点在 $y$ 轴附近,那么算法将会直接失败。因此,大圆上均匀分布并不会使得坏点很均匀。

因此我们尝试从覆盖区间入手考虑。由于贴近 $y$ 轴的更坏,我们从 $y$ 轴出发,依次构造出所有点。

以上图为例,我们放弃掉 $y$ 轴周围 $\theta = \varepsilon \pi$ 的角度,过 $A$ 作与 $y$ 为 $\theta$ 的直线,交 $B$ 为圆心 $1$ 为半径的圆上为 $X_2$。此时,$X_2$ 即为第一个确定的点,其相对 $y$ 正半轴的角度区间为 $[\angle yAX_2 = \theta, \angle yBX_2]$ 。

考虑下一个点:其角度区间起点需要是 $\angle yBX_2$,那么我们过 $A$ 作与 $y$ 为 $\angle yBX_2$ 的直线,交 $X_2$ 为圆心 $1$ 为半径的圆上为 $Z_2$。此时,$Z_2$ 即为第一个确定的点,其相对 $y$ 正半轴的角度区间为 $[\angle yA Z_2=\angle y B X_2, \angle y B Z_2]$ 。

可以发现 $X_2$ 和 $Z_2$ 的构造方法是完全相同的,因此可以一直做下去。

这个方法有以下美妙的性质:

  1. 上文提到的所有角度区间大小均等于 $\theta$,可用圆、菱形、平行线证得;
  2. 上文提到的所有点共圆,可用四点共圆证明。

因此,这样的构造必然会在得到 $1/2\varepsilon$ 个点后停止,对称构造负半轴,则一共 $1/\varepsilon$ 个点。

尽管我很想给这个圆上的构造一个几何解释,但是我的几何水平有限,很难找到一个合适的几何意义。如果有人能找到更好的解释并告诉笔者,我将感激不尽。

因此,本题的参考解法就是随便在哪里画一个圆就好,最好需要微调一下让最近点对唯一。

其实可以做到使用的点数更少:注意到上图中远离 $y$ 轴的部分都可以移动到靠近 $y$ 轴的部分,来让覆盖的角度区间尽量大。当然,这样的话解法就蛮丑了,因此范围就设为了圆能过的范围。

由于本题需要整数点,将格子放大(例如 $A=(0, -5000), B=(0, 5000)$) 然后取整即可。为了防止取整误差导致答案变化,可以在输出时将 $A, B$ 稍微往原点靠近一点。不过由于取整误差的存在,需要多放一些点来规避误差(理论上需要 $500$ 个点即可,但由于取整误差,其实在 $800$ 个点左右才满足题目要求)。


事实上,从 $x$ 轴开始构造也是有机会的,以下是李志腾同学提交的构造方法。由于构造十分精妙,正确率达到了 $ \frac {\tan^{-1}(4/1250)} {\pi / 2} \approx 1/490 $,亦是满足题目要求的。


首先选择两个点作为 closest pair(如 $A(0,0)$ 和 $B(4,0)$), 然后开始旋转 y 轴,接下来只要每次构造一对到 y 轴的距离小于 $B$ 点到 y 轴距离的点即可,同时还要保证构造的这一组坐标点与已存在的点之间的距离大于 $AB$ 之间的距离。

初始状态 y 轴顺时针旋转 0°, 选取 $E(3,4)$ 和 $F(-3,-4)$ 一组对称点,使其为当前到 $newY$ 轴距离最近的两点。

接下来顺时针旋转 $newY$ 轴,当接近 ▲$AEB$ 的角平分线时,继续构造对称点对 $G(8,4)$ 和 $H(-8,-4)$, 使其为当前到 $newY$ 轴距离最近的两点。重复以上步骤,每次添加一组对称点对,使 $B$ 点在 $newY$ 轴旋转过程中始终不是到 $newY$ 轴最近的两点之一。

不难发现,只要每次都将第一象限的点横坐标+5,第三象限的点横坐标-5,就能达到上述目的。因此最后构造的点对如下:


Epilogue

Chihao 说 adaptive 的采样也有一个下界,大约是 $T^{1/3} n^ {2/3}$,不过因为我没听懂所以我不知道到底怎么回事。(orz sampling)

Leave a Reply

Your email address will not be published.