计算几何

Published: by Creative Commons Licence

  • Tags:

切比雪夫距离

对于二维平面上两个点(a,b),(c,d),它们的切比雪夫距离定义为

由于切比雪夫距离不容易被预处理,有时候需要先转换为曼哈顿距离进行处理。下面给出转换的数学公式:

证明方式比较简单,首先将右边公式转换为:

考虑两种情况,第一种$a-c$与$b-d$同号。那么右边的公式取值为$|(a-c)+(b-d)|=|a-c|+|b-d|$。而第二种情况下,$a-c$与$b-d$异号。那么右边的公式取值为$|(a-c)-(b-d)|=|a-c|+|-(b-d)|=|a-c|+|b-d|$。因此证明了等式的成立。

利用这个公式我们可以先将所有平面上的点$(x,y)$转换为$(x+y,x-y)$的形式,之后计算各个点间的切比雪夫距离就可以得到原平面的曼哈顿距离。同理,如果我们将平面上的点$(x,y)$转换为$(\frac{x+y}{2}, \frac{x-y}{2})$,之后计算各个点之间的曼哈顿距离,那么就可以得到原平面的切比雪夫距离。

曼哈顿距离的组合

最近从一个atcoder的问题中学了一个新的东西,记录一下。

给定序列$2^0,2^1,2^2,\ldots, 2^k$,我们从$(0,0)$出发,我们可以不断从序列中选取一个整数x并删除,之后向四个方向中的一个方向移动距离x。重复这个过程直到序列为空。

我们可以证明通过上面这个流程可以从$(0,0)$移动到距离$(0,0)$曼哈顿距离为奇数且小于$2^{k+1}$的所有整数坐标顶点。

至于怎么构造到$(x,y)$的路径,我们可以选择最后一个数字$2^k$,之后沿着四个方向移动,判断哪种方案移动后到$(0,0)$的距离小于$2^k$,选择它即可。递归这个流程就可以构造出解决方案了。

斜线转坐标轴平行线

问题1:平面上有$n$个坐标不同的点$(x,y)$。对于顶点$(x_0,y_0)$,我们可以用过该点的两条斜率分别为$\frac{\pi}{4}$与$-\frac{\pi}{4}$的直线将整个二维平面划分为四个区域。我们可以按照四个区域相对于$(x_0,y_0)$的位置将其分为上下左右四个方向。现在我们希望对每个点统计处于其上方区域、下方区域、左边区域、右边区域(不存在与区域的划分线上)的顶点数目。

斜线不是很好处理,我们可以发现若一个顶点$(a,b)$落在$(x_0,y_0)$的右区域上,这时候有$(a-x_0,b-y_0)$的极角落在$(-\frac{\pi}{4},\frac{\pi}{4})$。这意味着

这里我们可以将所有点的坐标$(x,y)$变化成$(y-x,y+x)$,这样一个点$A$处于$B$的右区域,当且仅当这个$A$变换后的顶点处于$B$变换后的顶点的左上方。

对于其余三个方向我们可以做同样的变化。事实上由于这是线性变换,因此可以很容易得出:右区域对应左上,左区域对应右下,上区域对应右上,而下区域对应左下

现在问题就变成了统计每个顶点左上,左下,右上,右下各有多少顶点,离散化后用BIT统计即可。

一道不错的类似题目

求三角形内心坐标

问题:在圆心为原点,半径为1的圆周上,存在$n$个点($n\leq 3000$)。现在我们随机从中取出三个不同的点,考虑三个点构成的三角形的内心坐标。问三角形内心坐标的期望。

原题是https://atcoder.jp/contests/agc039/tasks/agc039_d。做法是套公式。考虑复平面,根据欧拉公式有:对于所有实数$x$,有:

同时,假设选择的三个点为$\exp(i\varphi_1),\exp(i\varphi_2),\exp(i\varphi_3)$,且满足$0\leq \varphi_1 < \varphi_2 < \varphi_3<2\pi$,那么由这三个点组成的三角形的内心一定为

这样我们只要暴力两两枚举即可解决这个问题,时间复杂度是$O(n^2)$以及一个很大的常数,因为$sin$和$cos$函数会被调用$O(n^2)$次。

多维偏序问题

问题1:给出$n$二维平面上的顶点$(x_i,y_i)$,满足$x_i,y_i\geq 0$,同时给出$m$个请求,每个请求查询左下角为$(0,0)$,右上角为$(r,t)$的矩形中有多少平面上顶点存在

这是个典型的二维偏序问题,我们可以提前所有顶点按照$x$坐标进行排序,如果$x$坐标相同,则按照$y$坐标排序。对请求通样这样处理,并且利用双指针技术在请求范围内的所有顶点加入后回答请求,这时候请求就变成了有多少顶点的$y$坐标小于等于$t$,这可以用BIT或线段树维护。总的时间复杂度为$O((n+m)\log_2n)$。

问题2:给出$n$三维的顶点$(x_i,y_i,z_i)$,满足$x_i,y_i,z_i\geq 0$,同时给出$m$个请求,每个请求查询左下角为$(0,0,0)$,右上角为$(r,t,d)$的矩形中有多少顶点存在

这个是三维偏序问题,与所有偏序问题一样,我们可以通过提前排序消除一个维护带来的影响。剩下的就是二维数据的维护了,你可以选择树套树,也可以选择CDQ分治。树套树时间复杂度为$O((n+m)(\log_2n)^2)$,空间复杂度为$O(n(\log_2n)^2)$,CDQ分治的时间复杂度为$O((n+m)(\log_2(n+m))^2)$,空间复杂度为$O(n+m)$。

问题3:给出$n$三维的顶点$(x_i,y_i,z_i)$,满足$x_i,y_i,z_i\geq 0$,同时给出$m$个请求,每个请求查询左下角为$(l,b,f)$,右上角为$(r,t,d)$的矩形中有多少顶点存在

这个问题类似于问题2,区别在于要去我们计算的是落在一个三维矩形中有多少顶点。一种简单的方式就是利用容斥,记$S$表示落在由$(0,0,0)$与$(r,t,d)$矩形中的所有顶点,记$X$表示满足$x<l$的顶点集合,同理定义$Y$和$Z$,那么我们要计算的落在左下角为$(l,b,f)$,右上角为$(r,t,d)$的矩形中顶点数目,等价于计算:$\mid \overline{X}\cap \overline{Y}\cap\overline{Z}\mid$。这是个简单的容斥,可以转换为$2^3$个左下角为$(0,0,0)$的矩形顶点数的统计。

一道CF的例题

一些游走问题

问题1:给出一组二维向量$v_1,v_2,\ldots,v_n$,你要选择一组符号$s_1,s_2,\ldots,s_n$,其中$s_i\in {-1,1}$。其中$\mid v_i \mid \leq D$,要求选择的符号满足$\mid \sum_{i=1}^ns_iv_i \mid\leq \sqrt{2}D$。

如果只有两个向量的话,我们可以构造一个半径为$D$的圆,我们将两个向量以及其负向量加入,可以证明至少会有两个向量是处于同一个$90$度半圆内,而这个半圆内的任意两点距离都不会超过$\sqrt{2}D$,这与我们的符号也就选好了。

现在考虑一般情况,此时至少有三个向量,我们取这样三个向量以及其负向量加入到半径为$D$的圆内,此时,至少有两个向量处于同一个$60$度半圆内,而这个半圆内任意两点的距离都不会超过$D$,因此我们找出这两个向量,并合并为一个向量即可。重复这个过程直到向量数目少于3为止。如果剩余向量数为2,那么需要特殊处理,否则任意选一个符号就好了。

直线(线段)排序的优化技巧

考虑现在有$n=10000$条二维直线(所有直线都不与$Y$轴平行,且任意两条直线最多有一个交点)。之后给定$m=10000$个请求,第$i$个请求给定一个数$x_i$,要求将所有直线根据与直线$y=x_i$交点的纵坐标从小到大排序,并输出排序后的编号。

要计算交点坐标,有$O(1)$的做法,因此如果我们使用快速排序或选择排序,那么时间复杂度将为在$O(nm\log_2n)$。

下面我将提出一种排序技术,可以将时间复杂度优化到$O(n(m+n))$。

首先我们离线请求,将请求按照$x_i$从小到大进行排序。之后我们逐个处理请求,但是处理每个请求的时候,我们使用的排序算法是插入排序。为什么要使用最坏时间复杂度为$O(n^2)$的插入排序呢?因为插入排序在序列本身有序的情况下是线性的。下面我们给出严格的时间复杂度分析。

我们考虑插入排序的时间复杂度,其本质是扫描整个序列一次,并且每一次解决一个逆序对时对时间复杂度贡献$1$,因此当序列完全为逆序的时候,总共有${n\choose 2}$个逆序对,这时候时间复杂度为$O(n^2)$。

但是考虑到直线排序的特殊性,对于任意两条直线$A$与$B$,直线$A$与$B$的偏序关系最多改变一次(由$A<B$变成$A>B$)。即除了第一次的插入排序后,之后每个逆序对对时间复杂度的贡献仅为$O(1)$,而插入排序的其余部分是线性的。

因此总的时间复杂度为$O(n(m+n))$。

最近点对

问题1:给定$n$个二维点,要求计算最近一对点的距离。(这里用的距离是欧几里得距离)

算法导论上给出了一个最近点对的算法。

问题2:给定$n$个二维点,要求计算最近一对点的距离。(这里用的距离是曼哈顿距离)

我们可以先将所有点按照$x$坐标排序,如果$x$相同就按$y$排序。之后每个顶点只和前面的点计算最短距离,而全局的最近点一定能从这些最短距离中取到。

之后我们对于一个顶点$p=(x_i,y_i)$,我们可以将左边的所有顶点分成两部分,一部分的$y$坐标恒大于等于$y_i$,另外一部分则小于$y_i$。

注意对于左上顶点$lt=(x_j,y_j)$,其与$p$距离为$x_i-y_i-x_j+y_j$,考虑到$x_i-y_i$是常数,因此我们对上平面的点维护最小的$-x_j+y_j$即可。同理对于下平面的顶点$lb=(x_k,y_k)$,其与$p$距离为$x_i+y_i-x_j-y_j$,我们只需要对下平面的点维护最小的$-x_j-y_j$即可。

上面提到的内容可以通过维护两颗线段树实现。因此总的时间复杂度为$O(n\log_2n)$。

多条线段判断是否有交点

给定$n$条线段,判断是否存在至少一对线段有交点。

我们可以从左到右扫描所有线段。将线段左端点视作加入事件,右端点视作离开事件。

加入事件,记当前$x$为$x_0$,我们二分找到插入的位置(按照线段于$x=x_0$这条线的交点的纵坐标排序),之后判断前驱和后继与新线段是否有交点,有则直接输出解,否则加入线段。

删除事件,删除线段后,还需要重新判断一下前驱和后继是否有交点,有则直接输出解,否则继续流程。

上面的做法是不支持垂直线段的。要支持垂直线段可以这样做,以线段中心为轴稍微旋转线段。或者可以直接特殊处理垂直线段和垂直线段的交点,以及判断垂直线段与其余线段的交点。

总的时间复杂度为$O(n\log_2n)$。

曼哈顿距离最小生成树

给定二维平面上$n$个点,每对点之间存在一条边,边权等于二者的曼哈顿距离。要求找到一株最小生成树。这里$n\leq 10^5$。

一种简单的思路就是用不用最小堆优化的Prim算法,时间复杂度为$O(n^2)$,但是还是差点意思。

最近在Topcoder上学到了可以$O(n\log_2n)$计算曼哈顿距离最小生成树的技术。下面讲解一下。

考虑任意一个点$P$,我们以其为中心,将平面分成8部分。

http://community.topcoder.com/i/education/lineSweep/octants.png

假设$Q$为西北平面中离$P$最近的顶点,而$R$是另外任意一个顶点。可以发现假如$PR$是最小生成树中的一条边,那么$QR$与$QP$不可能同时出现,但是二者的边权均不会超过$PR$,因此我们可以用$QR$或$QP$中的一条边替代$PR$。换句话说,就是$PR$这条边我们在计算最小生成树的时候不需要考虑。

这样一来,每个顶点最多有$8$条边需要考虑,因此总共需要考虑的边的数目仅为$8n$。这时候我们利用Kruskal算法就可以直接$O(n\log_2n)$出解了。

接下来我们讨论如何为每个顶点找到这$8$条边。我们先考虑如何为每个顶点找到西北方向的最近的顶点,而其它方向可以通过这个方法推广出去逐一解决。

我们发现对一个顶点$P$有贡献的其余顶点$Q$都满足$Q.x+Q.y\leq P.x+P.y$且$Q.y\geq P.y$。如果没有$Q.y\geq P.y$这个条件,那么我们可以将所有顶点按照两个维度的和进行排序处理,非常简单。但是现在加上了$Q.y\geq P.y$这个条件,我们就不能这么做了。但是我们可以用分治的技术解决这个问题。

我们定义$dac(S)$表示对$S$代表的点集计算最近的西北部点,同时输入的$S$按照$y$坐标从小到大排序(如果$y$相同,则按$x$进行排序),而处理完后,$S$按照两个维度的和从小到大排序。

对于一个请求,我们将输入分成上下两个平面中的顶点,并分别递归解决。之后我们发现下平面对上平面是没有贡献的,但是上平面可能对下平面存在贡献,且上平面的顶点$Q$,对于下平面的顶点$P$都是满足$Q.y\geq P.y$这个条件的。因此我们只需要直接处理即可。之后用合并排序的方式将上下两个平面的顶点集合合并。

很显然上面的流程时间复杂度是$O(n\log_2n)$的,我们要为$8$个平面都重复上面的流程,因此总的时间复杂度为$O(8n\log_2n)$。

提供一道Topcoder題目SRM 760 ComponentsForever。

一些圆覆盖问题

在二维平面上给定$n$个红点和$m$个黑点。要求找到半径最大的圆的半径,满足这个圆中至少包含一个红点,且不含任何黑点。(一个圆周上的点可以认为是在圆内,也可以认为是在圆外)。如果这个圆可以任意大,就输出$-1$。其中$1\leq n,m\leq 1000$。

这是一道原题

首先我们考虑什么情况下圆会任意大,这时候至少有一个红点落在所有点组成的凸包上。接下来我们认为圆不能任意大。

一般的思路是可以发现圆周上至少有3个点才能确定一个圆,因此我们可以直接枚举所有的三个点确定的圆,这样的话时间复杂度为$O(n^4)$。

考虑假如存在满足条件的半径为$R$的圆,则对于任意$r\leq R$,半径为$r$的满足条件的圆也一定存在(我们可以在$R$圆中划出一个更小的圆,覆盖其中的一个红点即可)。因此我们可以用二分来找到最大的圆的半径。

在给定半径为$r$的情况下,可能的圆非常多,我们不可能一个一个枚举。可以注意到如果存在一个半径为$r$的覆盖圆,也一定存在一个半径为$r$覆盖圆,有至少一个顶点落在圆周上(稍微挪动一下圆心即可)。有了这个性质,我们就可以枚举每个点,计算这个点落在圆周上,圆心相对于这个点的弧度可能是哪些(这是一个经典问题了)。

枚举每个点的时间复杂度为$O((n+m)\log_2(n+m))$,因此一轮二分的check所花费的时间复杂度为$O((n+m)^2\log_2(n+m))$。配合二分的时间复杂度为$O((n+m)^2\log_2(n+m)\log_2 M)$,其中$M$与精度有关。

但是这里有一个小小的优化思路,之前我们是外面二分圆大小,内部枚举所有边缘点来实现的,现在我们外部枚举所有边缘点,内部二分圆大小。注意到以红点落在圆边缘的情况下,随着半径的增大,覆盖圆的存在性单调减少,因此可以二分直接查出红点落在圆边缘下最大的覆盖圆,记半径为$low$。之后我们二分计算蓝点$b$落在圆边缘下最大的覆盖圆,记为$high$,如果$high\geq low$,则对于任意半径为$r\in [low,high]$,都存在一个半径为$r$的覆盖圆,覆盖一个红点且$b$落在圆边缘上(如果不存在,记$k$为最小的$b$落在圆周的覆盖圆的半径,此时$k>low$且正好一个红点落在圆周上,这与$low$的定义相悖)。

当然上面还没有达到优化的作用,因为时间复杂度还是没有变。但是接下来我们应用一个技巧,就是设$L$为目前为止找到的最大覆盖圆的半径,则接下来处理某个点$x$并进行二分之前,我们先检测一下是否存在一个半径为$L$的覆盖圆,$x$落在圆周上。如果不同过,则不必进行后面的二分。

我们可以发现检测次数一共是$n+m$次,这部分的时间复杂度为$O((n+m)^2\log_2n)$,二分次数则很特殊。我们可以为每个顶点赋予一个权值,这个权值恰好等于以它落在圆周上最大半径的覆盖圆的半径。可以发现二分次数实际上是我们枚举的顶点的一个特殊的递增序列(如果一个顶点的权值比之前所有枚举的顶点权值都要大,则二分次数增加1)。如果我们提前打乱所有顶点的处理顺序(保持红点在所有蓝点处理前被处理),则可以证明二分的总次数的期望为$O(\log_2n)$。因此二分的时间复杂度为$O((n+m)\log_2n\log_2M)$。总的时间复杂度为$O((n+m)^2\log_2n)$。

参考资料