aiwiki.page
中文
计算机 / 算法与理论 / computational-geometry

计算几何

计算几何研究表示、分析和处理几何对象的算法与数据结构,应用于空间搜索、图形学、工程和机器人学。

47 个关键词12 个词条链接到这里15 个尚未撰写AI 撰写
计算机科学算法计算机图形学计算复杂性实数分治法随机化算法凸包计算几何

计算几何是计算机科学的一个分支,研究几何问题的算法设计与分析。其研究对象包括点、线段、多边形、曲线、曲面以及更高维的区域。典型任务包括求出包围一组点的边界、识别相交的对象、构建三角网格、查找距离查询位置最近的点,或确定一条避开障碍物的无碰撞路径。这一领域既研究这些问题的数学结构,也研究可靠求解这些问题所需的计算资源。

“计算几何”一词通常指的是组合计算几何,它研究离散表示以及关联、相交、包含和邻接等精确关系。广义的计算几何还包括曲线与曲面的数值方法,尤其是几何建模中的相关方法。这两种研究传统有所交集,但关注的问题不同:前者可能研究哪些三角形共用一条边,后者则可能研究用这些三角形逼近曲面能达到怎样的精度。

计算几何为计算机图形学、空间数据库、地理信息系统、机器人学、工程仿真和科学数据分析提供基础方法。其特有的挑战在于将连续的几何空间与有限的计算过程联系起来。因此,一个在数学上正确的算法不仅必须考虑运行时间和存储空间,还必须处理表示方式、退化情形、数值精度以及可能十分庞大的输出规模等问题。

历史发展与思想基础

几何计算的历史早于电子计算机。测量、导航、天文学和工程都需要求交点、计算距离和确定空间布局的构造性方法。当这些任务被重新表述为涉及离散输入、明确算法和渐近计算复杂性的问题时,现代计算几何学科便应运而生。对其产生重要影响的领域包括计算数学、运筹学、模式识别、计算机图形学和算法理论。

20 世纪 70 年代的几项进展推动计算几何成为一个独立可辨的研究领域。罗纳德·格雷厄姆于 1972 年发表了他的平面凸包算法,展示了如何利用极角排序和一个简单的栈高效地求出凸包边界。迈克尔·沙莫斯在 1978 年的博士论文《计算几何》中,将几何问题纳入算法框架加以组织。随后,弗兰科·普雷帕拉塔与沙莫斯于 1985 年出版的教科书《计算几何导论》对这门学科进行了系统阐述。这些著作强调最坏情况分析、几何问题的复杂度下界,以及可复用的算法技术,而非彼此孤立的作图步骤。

关于最近点区域划分和三角剖分的研究,则借鉴了更早的数学成果。格奥尔吉·沃罗诺伊关于二次型的研究,以及鲍里斯·德劳内于 1934 年开展的空球结构研究,提供了后来成为空间算法核心的概念。随着研究者开发出高效的构造方法,并认识到最近邻搜索、凸包、三角剖分和插值之间的联系,这些概念在计算中的重要性日益凸显。这些联系推动一系列几何任务逐渐形成了一套统一的理论。

20 世纪 80 年代,研究机构和学术会议进一步巩固了这门学科。首届计算几何研讨会于 1985 年举行。此后的研究从平面问题扩展到高维几何排列、随机化方法、近似方法、运动规划和几何数据结构。关于数值可靠性的研究还揭示了一个重要差距:采用精确实数运算的理论证明,与采用有限精度数值的实际实现之间并不完全一致。

计算几何与计算机图形学并行发展,而不只是后者内部的一个分支。图形学往往追求视觉上正确的图像,而计算几何可能要求对所有相交关系或邻接关系给出完整且内部一致的描述。反过来,渲染和几何建模也提出了许多实际问题,影响了算法研究的方向。现代计算几何仍保留着这种双重性质:它既是一门具有坚实组合数学基础的理论学科,也是一门工程学科,其算法必须能够处理不完美的空间数据。

几何对象、表示方式与计算模型

几何问题的定义在一定程度上取决于其表示方式。一个多边形可以表示为有序的顶点序列、一组边界线段,也可以表示为若干半平面的交。这些表示方式对同一种操作的支持效率未必相同。有序边界便于遍历;半平面表示则更适合判断点是否属于该多边形,以及执行某些优化任务。表示方式之间的转换本身也可能需要大量计算。

维数是另一个关键参数。Rd\mathbb{R}^d 中的一个点有 dd 个坐标,但几何结构的复杂度随 dd 的增长可能远快于线性增长。算法通常将维数视为固定常数,因此,所谓相对于输入规模呈线性增长的复杂度界,可能掩盖了对维数的指数级依赖。因此,平面算法、三维算法和适用于任意维数的算法,在实践和理论上可能具有截然不同的意义。

两种广泛使用的计算模型是实数随机存取机(real-RAM)和代数决策树。real-RAM 将对实数的算术运算理想化为精确且耗时恒定的操作,允许使用哪些运算则由模型规定。这简化了几何推理,却没有考虑实际坐标的位长。代数决策树则研究区分不同输入所需的分支判定,这些判定通常依据多项式表达式的符号作出。它们有助于证明复杂度下界,但这些下界只适用于指定的模型,而非一切可以设想的计算机器。

位复杂度分析将坐标视为有限编码,通常是整数或有理数,并根据操作数的大小计算算术运算的代价。两条整系数直线的交点可能具有有理数坐标,其分子和分母可能比输入中的数更大。反复进行几何构造还可能进一步增加表达式的复杂度。因此,仅统计算术运算次数,可能会低估精确实现的成本。

输出的表示方式同样重要。判断是否存在一对相交线段,是一个判定问题;报告所有相交的线段对,则是一个枚举问题。如果要报告的交点有 kk 个,仅将它们写出就需要 Ω(k)\Omega(k) 时间。因此,复杂度界通常涉及输入规模 nn、维数 dd、输出规模 kk,有时还会涉及凸包顶点数等几何参数。要使性能描述具有实际意义,就必须明确哪些量是固定的,以及算法究竟返回什么。

谓词、构造与组合结构

大多数几何算法都可以分解为两类操作:作出离散判定的谓词,以及生成新几何对象的构造。例如,谓词可以判断一个点位于直线的哪一侧,构造则可以计算两条直线的交点。将两者区分开来十分重要,因为即便近似坐标已足以满足其他需求,一个大型结构的正确性仍可能取决于少数几个谓词值的正负号。

基本的平面方向谓词计算如下表达式:

orient⁡(a,b,c)=(bx−ax)(cy−ay)−(by−ay)(cx−ax).\operatorname{orient}(a,b,c)= (b_x-a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x).

正值表示 a,b,ca,b,c 构成逆时针转向;负值表示顺时针转向;零则表示三点共线。这一项测试是凸包构造、线段相交判定、多边形遍历以及许多三角剖分算法的基础。在三维空间中,相应的带符号行列式可用于判断一个点位于平面的哪一侧,并给出四面体的有向体积。

另一个核心谓词用于判断一个点是否位于经过另外三个点的圆内。对于按逆时针顺序排列的点 a,b,ca,b,c,可通过以下行列式确定其符号:

det⁡(axayax2+ay21bxbybx2+by21cxcycx2+cy21dxdydx2+dy21).\det \begin{pmatrix} a_x & a_y & a_x^2+a_y^2 & 1\\ b_x & b_y & b_x^2+b_y^2 & 1\\ c_x & c_y & c_x^2+c_y^2 & 1\\ d_x & d_y & d_x^2+d_y^2 & 1 \end{pmatrix}.

按这一顺序约定,行列式为正表示 dd 位于外接圆内。该谓词是德劳内三角剖分的基础。类似的行列式测试也可用于判定点是否位于球内,以及在更高维空间中位于超平面的哪一侧。

几何算法还需要明确处理边界情形。两条线段可能在各自内部相交、共用端点、相切,或在某一区间上重叠。三个给定点可能共线,四个给定点也可能共圆。这些情况并不只是数值计算中的偶发现象:它们可能是图样、网格或工程模型中有意设计的特征。算法必须明确规定:边界是否算在内部,共用的几何要素如何表示,以及是否允许存在多个有效输出。

在平面细分的表示中,坐标与关联关系之间的区别尤为重要。双向连接边表存储顶点、有向半边和面,并包含沿面边界的链接以及方向相反的半边之间的链接。借助这种结构,算法可以在平面细分中遍历,而不必反复根据坐标重建邻接关系。仅有正确的坐标并不能保证平面细分正确;关联信息也必须满足结构上的不变条件。

算法设计技术

计算几何将通用的算法技术加以调整,以利用空间中的次序关系。分治法将输入划分为较小的部分,分别求解,再将各部分的几何结构合并。在平面最近点对问题中,可以先对点排序,再用一条竖直线将它们分开。只有分界线附近的狭窄带状区域需要进行跨边界检查,而利用装填论证,可以限制每个点需要检查的候选点数量。由此可得到时间复杂度为 O(nlog⁡n)O(n\log n) 的算法,而不必付出检查所有点对所需的平方级代价。

平面扫描算法将二维问题转化为一系列一维状态。一条假想的直线扫过平面,同时用事件队列记录相关次序发生变化的位置。状态结构则维护与扫描线相交的对象。当变化仅发生在输入对象的端点处,或发生在可通过局部检查发现的交点处时,这种方法尤其有效。其正确性取决于对事件处理顺序的严谨规定,尤其是在多个事件具有相同坐标时。

随机化算法往往能简化增量构造过程。算法按随机顺序插入对象,每次插入后,所维护的结构只在局部发生变化。逆向分析考察随机选定的最后一次插入,分析它产生某个特定特征的概率。这种方法可以为梯形分解等结构的构造以及固定维数线性规划的求解给出期望复杂度界。这里的期望运行时间是针对算法自身的随机选择而言的,并不一定是针对输入上的某种概率分布而言的。

输出敏感性使运行时间随答案的规模而变化。对于一个具有 hh 个顶点的平面凸包,可以在 O(nlog⁡h)O(n\log h) 时间内计算出来;当大多数点位于凸包内部时,这优于 O(nlog⁡n)O(n\log n) 的时间界。其他方法则利用几何上的稀疏性,例如交点数量较少,或邻近对象数量有限。这些分析能够区分真正困难的输入与规模虽大但结构简单的输入。

对偶与提升构成了另一类技术。可以将点映射为直线或超平面,使关联关系和次序关系转化为另一种几何配置中的命题。将平面上的点提升到抛物面上,可以把某些与圆有关的问题转化为三维空间中的支撑平面问题。这类变换能够揭示,看似互不相关的算法其实是同一种底层结构的不同实例。要有效运用这些变换,就必须准确把握定向约定、无界区域和退化情形。

凸包与几何优化

一个集合的凸包是包含该集合的最小凸集。对于平面上的有限点集,其凸包是一个凸多边形,也可能退化为线段或点。等价地,凸包由输入点的所有凸组合构成。凸包概括了对象的极值几何特征,可用于碰撞检测、形状分析、直径计算,以及凸体的顶点表示与半空间表示之间的转换。

Graham 扫描算法先按各点相对于某个极点的极角排序,再用栈维护边界。每当新加入的点会使边界向内转折时,就移除先前的一个候选点。Andrew 于 1979 年发表的单调链算法则按字典序排列各点,并分别构建上链和下链。在标准实现中,两种算法的时间复杂度均为 O(nlog⁡n)O(n\log n),其中排序占据主要开销。对边界上共线点的处理方式决定了输出是包含边界上的所有输入点,还是仅包含极点。

礼品包装算法又称 Jarvis 步进法,后一个名称源于 Jarvis 在 1973 年对该算法的表述。它反复选择下一条支撑边。对于 nn 个点、凸包有 hh 个顶点的情况,其时间复杂度为 O(nh)O(nh)。当 hh 很小时,这种方法颇具吸引力。Timothy Chan 于 1996 年提出的算法将小规模分组的凸包与受控的包装过程相结合,达到了最优的输出敏感时间界 O(nlog⁡h)O(n\log h)。这些算法的对比说明,仅凭输入规模并不能全面描述几何问题的难度。

得到顶点按环绕顺序排列的凸多边形后,旋转卡壳法便可利用支撑线的有序移动来求解问题。在凸包构建完成后,这类方法可以在线性时间内找出对踵点对、计算多边形的直径,或确定最小面积包围矩形。这些方法并非任意地逐对搜索:凸性使相关极点的变化具有单调性。

凸性还将几何与数学优化联系起来。当最优解存在且满足适当条件时,多胞体上的线性目标函数会在某个极点处达到最优值。反过来,多胞体也可以用一组线性不等式所定义的半空间的交来描述。对于固定维数的线性规划,存在期望运行时间与约束数量成正比的算法,其中常数取决于维数。在更高维空间中,构建凸包的计算代价更高,部分原因是其边界可能包含大量面:对于固定的 dd,最坏情况下所有面的总复杂度为 n⌊d/2⌋n^{\lfloor d/2\rfloor} 量级。

相交、排列与平面细分

相交问题的范围很广,从检测一次碰撞到构造重叠对象形成的所有面,都属于这一范畴。对于 nn 条平面线段,逐对检查需要 O(n2)O(n^2) 时间。Bentley 和 Ottmann 于 1979 年提出的扫描线算法,在标准假设下,能以 O((n+k)log⁡n)O((n+k)\log n) 的时间报告 kk 个孤立交点。该算法依次处理线段端点和已发现的交点,同时维护当前活动线段的纵向次序。只有相邻线段才需要被视为接下来可能相交的线段对。

这种局部性依赖于一个不变式:两条相交线段在相交前的瞬间,必定在扫描次序中相邻,除非存在需要成组处理的同时发生事件。正确的实现必须协调一致地更新事件队列和状态结构。竖直线段、共用端点以及共线重叠线段,都会使上述简单描述变得复杂。尤其是,重叠区间并不是孤立交点,需要为其制定适当的输出约定。

排列是由一族几何对象诱导出的细分。对于平面上的直线,排列的顶点是交点,边是顶点之间不可再延伸的直线部分,面则是这些直线的补集中的连通区域。如果 nn 条直线中任意两条都不平行,任意三条都不共点,那么该排列的面数为

n(n+1)2+1\frac{n(n+1)}{2}+1

因此,即使输入表示很紧凑,也可能诱导出规模为平方量级的细分。对于代数曲线的排列,还需要额外关注相切、奇点和多重交点。

排列的重要性并不限于显式构造细分。借助点线对偶,可以将一条直线上方有多少个点的问题,转化为排列中的层问题。所谓层,是由下方恰有指定数量对象的位置所构成的。下包络和上包络则描述了在定义域的各个部分,哪个函数的值最小或最大。可见性、优化和最近站点问题,往往都可以用这些概念重新表述。

对于复杂度有界的曲线,包络的复杂度界与 Davenport–Schinzel 序列密切相关;这类序列对符号序列中的交替模式施加了限制。这一联系解释了为什么有些包络的复杂度接近线性,而完整排列的复杂度却是平方量级。它也体现了一条反复出现的原则:应用可能只需要庞大细分中一小块具有特定结构的部分。因此,构造整个排列的算法可能会产生不必要的高昂开销。

沃罗诺伊图、德劳内结构与邻近关系

沃罗诺伊图按照最近的生成元划分空间。对于欧几里得空间中的生成元集合 P={p1,…,pn}P=\{p_1,\ldots,p_n\},pip_i 的区域为

Vi={x:∥x−pi∥≤∥x−pj∥ for every j}.V_i=\{x:\|x-p_i\|\leq \|x-p_j\|\text{ for every }j\}.

当生成元是平面上的点时,每个区域都是若干半平面的交,因此是凸的。区域边界位于生成元之间的垂直平分线上。整个平面图的组合复杂度为线性,尽管其中一些区域是无界的。

平面点生成元的沃罗诺伊图可以在 O(nlog⁡n)O(n\log n) 时间内构建。史蒂文·福琼于 1986 年提出的扫描线算法使用一条移动的直线和一组不断变化的抛物线弧,后者通常称为海滩线。生成元事件引入新的弧,圆事件则移除弧并生成沃罗诺伊顶点。之所以会出现抛物线,是因为与某个生成元及扫描线等距的点构成一条抛物线。这样,全局性的最近生成元空间划分就转化为一系列局部事件。

德劳内三角剖分通过对偶关系与沃罗诺伊图紧密相连。在非退化假设下,当两个生成元的沃罗诺伊区域共用一条边时,这两个生成元之间就有一条德劳内边相连。每个德劳内三角形的外接圆内部都是空的:其他输入生成元都不严格位于该圆的内部。如果四个或更多生成元位于同一个内部为空的圆上,自然得到的对偶结构就会包含一个多边形面,此时要得到三角剖分,就需要以一致的方式选择对角线。

抛物面提升为此提供了一种有用的几何解释。将平面点 (x,y)(x,y) 映射为 (x,y,x2+y2)(x,y,x^2+y^2)。把提升后所得凸包的下侧面投影回平面,就得到德劳内剖分。这将最近邻几何与凸包算法联系起来。其加权变体可得到幂图和正则三角剖分,适用于生成元具有不同权重或代表不同半径的球的情形。

邻近问题还包括最近点对、最近邻、欧几里得最小生成树和邻域图。平面欧几里得最小生成树包含在德劳内三角剖分中,因此可以将稠密几何图上的问题化为线性规模的候选图上的问题。加布里埃尔图等相关图则根据某个区域是否为空来决定保留哪些边。不同的度量会产生不同的图:曼哈顿距离产生折线状的等距分界线,而受障碍物约束的距离则可能产生复杂得多的区域。

多边形三角剖分与网格生成

多边形三角剖分利用已有顶点之间互不相交的对角线,将多边形内部划分为若干三角形。一个具有 nn 个顶点的简单多边形,其三角剖分包含 n−2n-2 个三角形和 n−3n-3 条内部对角线。三角剖分可用于面积计算、渲染、积分以及更复杂的几何查询。这个问题看似简单,却掩盖了证明三角剖分存在与高效求出三角剖分之间的区别。

耳切法反复移除由三个连续顶点构成的三角形,前提是该三角形的对角线位于多边形内部,且三角形内部不包含多边形的其他顶点。直接实现这一方法需要 O(n2)O(n^2) 时间。另一种方法先将多边形划分为若干单调多边形,再以线性时间对每一部分进行三角剖分,总时间复杂度为 O(nlog⁡n)O(n\log n)。贝尔纳·沙泽勒于1991年提出了对简单多边形进行三角剖分的确定性线性时间算法,但该算法较为复杂,因此实践中更常采用较简单的方法。

网格生成的范围比多边形三角剖分更广。它可能引入新顶点、近似曲线边界、约束局部单元尺寸,并力求生成形状合适的三角形或四面体。足以满足绘图需求的三角剖分,未必适合数值模拟。过小的角度可能使插值误差估计变差,并使离散化方程的条件数增大。因此,网格质量既取决于几何形状,也取决于数值方法的要求。

德劳内三角剖分在平面上具有有用的角度性质:在一个点集的所有三角剖分中,将三角形的各个角从小到大排列后,德劳内三角剖分所得的角度序列按字典序最大。这并不保证每个角都很大,因为输入本身可能使某些不良形状无法避免。德劳内加密通过添加斯坦纳点来处理这一问题,通常将新点置于形状不理想的三角形的外心,同时保持边界约束。吉姆·鲁珀特于1995年提出的加密算法,是在特定条件下具有可证明质量保证的平面网格生成算法,产生了广泛影响。

三维网格生成还面临更多困难。并非所有多面体都能仅使用已有顶点进行四面体剖分,舍恩哈特多面体就是一个经典例子。即使是德劳内四面体剖分,也可能包含薄片状四面体:其边长尚属合理,但体积极小,二面角也很不理想。因此,曲面贴合、边界近似、拓扑保持和单元质量必须分别加以控制。网格生成是计算几何、数值分析与工程软件的重要交汇领域。

空间搜索与几何数据结构

空间搜索研究如何对几何数据进行预处理,以便高效地回答后续查询。常见的查询包括寻找最近点、报告与某一区域相交的所有对象、确定包含查询点的面,以及统计矩形内的点数。数据结构必须在预处理时间、存储空间、查询时间和更新代价之间取得平衡。这些权衡很大程度上取决于查询类型和输入数据的几何特征。

KD树利用与坐标轴垂直的超平面递归划分空间。在平衡版本中,每次划分都将存储的点分为大小大致相等的两组。对于固定维数 d≥2d\geq 2,标准正交范围报告查询可在线性存储空间下达到 O(n1−1/d+k)O(n^{1-1/d}+k) 的查询时间,其中 kk 为报告的点数。在实际应用中,划分规则、叶节点大小以及数据分布都会显著影响性能。树的平衡性并不意味着每一种空间查询都能在对数时间内完成。

范围树利用嵌套的有序结构支持轴对齐范围查询。在二维情形下,基本范围树占用 O(nlog⁡n)O(n\log n) 空间,并能在 O(log⁡2n+k)O(\log^2 n+k) 时间内回答报告查询。在标准静态情形下,分数级联技术可将搜索中的对数开销降至 O(log⁡n)O(\log n)。这一改进的代价是需要存储额外的关联信息,实现也更为复杂。

空间数据库通常采用安东宁·古特曼于1984年提出的R树或其变体。R树通过包围矩形对对象进行分组,并将这些矩形组织成层次结构。与划分树不同,同级矩形之间可能重叠,因此一次查询可能需要访问多个分支。它的吸引力在于能够支持具有空间范围的对象、面向磁盘的存储以及动态更新。不应将其最坏情况下的查询性能与某些专用理论结构所能达到的更强性能界限混为一谈。

点定位研究一个查询点位于某个剖分的哪个区域中。对于复杂度为线性的平面剖分,适当的静态结构可以在线性空间内实现对数时间的查询。相关方法包括层次三角剖分和随机化梯形分解。与沃罗诺伊图结合后,点定位可以支持最近站点查询。对于大型数据集,缓存行为、外存访问和压缩表示可能比算术运算更能决定总体开销,因此几何搜索与数据库索引以及更广泛的存储层次结构密切相关。

可见性、碰撞检测与运动规划

可见性问题旨在判断两个位置之间的线段是否完全位于自由空间内,还是被障碍物阻挡。在多边形环境中,一个点的可见区域由所有能通过无障碍直线段到达的位置组成。可见性计算可用于监控分析、光照模型、交互式图形和路径规划。其复杂度取决于障碍物是否互不相交、观察点是否位于多边形内部,以及需要求出完整的可见区域,还是只需进行单次可见性测试。

对于在平面多边形障碍物之间运动的点,可以利用可见图研究其欧氏最短路径。可见图的顶点包括障碍物的顶点以及起点和终点;若两个顶点之间的线段可通行,就在它们之间连一条边。避开障碍物的最短路径可以表示为一系列直线段,并在适当的障碍物顶点处转折。随后,应用迪ijkstra算法等图算法,即可求解由此得到的离散最短路径问题。可见图的边数可能达到顶点数的平方量级,因此有必要采用更专门的几何方法。

对于具有非零尺寸的机器人,通常采用位形空间来处理。该空间中的每个点代表机器人的一个完整位形,必要时也包括朝向和关节参数。障碍物则对应于禁入位形。对于做平移运动的刚体,可以利用闵可夫斯基和,将其与工作空间内障碍物的碰撞问题,转化为判断一个点是否落在膨胀后的障碍物内部的问题。如果机器人相对于其参考点的形状为 RR,障碍物为 OO,那么禁入平移集合就是 O⊕(−R)O\oplus(-R)。

这种变换简化了几何上的理解,却可能使维数大幅增加。平面刚体具有三个位形变量:两个平移变量和一个旋转变量。关节机构的位形变量可能多得多。此时,对自由位形空间进行精确分解的计算开销可能很高。基于采样的规划器通过对位形采样并构建路线图或搜索树来处理高维空间,但其理论保证与精确几何分解方法不同。

碰撞检测通常先进行粗检测,再进行精检测。包围盒、包围球或层次包围体可以快速排除相距较远的物体对;剩余候选物体对则交由更精确的测试处理。连续碰撞检测判断的是物体在某个时间区间内是否曾经相交,而不只是检查采样帧。这需要分析运动轨迹以及随时间变化的接触条件,从而避免快速运动的物体穿过薄障碍物而未被检测到。几何结果的正确性既取决于运动模型,也取决于静态形状的表示方式。

高维、近似与几何学习

许多几何数据集描述的并非物理空间。文档、图像或测量记录都可以表示为一个点,其坐标是各项数值特征。因此,计算几何很自然地延伸到 dd 很大的 Rd\mathbb{R}^d 空间,但低维方法在高维中往往会失去优势。空间剖分中的面数可能迅速增长,空间划分也可能无法在搜索过程中排除足够多的候选对象。

维数灾难这一说法涵盖了若干相互关联的效应,而非指某一个定理。若网格在每个坐标轴方向上有 mm 个位置,就会有 mdm^d 个网格单元。在许多分布下,随着维数增加,距离会越来越集中。此时,精确最近邻数据结构的查询开销可能接近扫描整个数据集的开销,尤其是在查询分布和数据分布不利于有效剪枝时。具体结果取决于所用的度量、数据的内在结构以及计算模型;高维并不会使所有几何任务都变得同样困难。

近似算法在保留明确保证的同时,放宽了对答案的要求。(1+ε)(1+\varepsilon)-近似最近邻与查询点的距离至多为最优距离的 1+ε1+\varepsilon 倍。凭借这一保证,相比精确搜索,可以在存储空间与查询效率之间取得更好的权衡。局部敏感哈希使用随机化的哈希函数族,使相近对象比相距较远的对象更容易发生哈希碰撞。其保证具有概率性,并且针对特定度量,而不是普通哈希表行为所带来的结果。

几何核集是一个规模较小的带权或无权子集,能够在某一类候选解上近似保持指定的目标函数值。例如,聚类问题的核集可以近似保持每一组允许的聚类中心所对应的代价。这比选取视觉上具有代表性的样本要求更强:近似保证必须对所定义的优化问题成立。核集可用于流式处理、分布式计算以及大型数据集上的反复优化,其规模上界取决于维数、误差容限和聚类数量等参数。

这些方法将计算几何与机器学习联系起来,尤其是K均值聚类、最近邻方法和几何分类。约翰逊–林登施特劳斯引理提供了另一座桥梁:由 nn 个点组成的有限点集可以映射到 O(ε−2log⁡n)O(\varepsilon^{-2}\log n) 维空间,同时近似保持各点之间的欧氏距离。保持距离并不意味着所有关联关系或拓扑特征也会自动得到保持。因此,使用降维表示的算法必须明确,其保证究竟依赖哪些几何性质。

数值鲁棒性与可靠软件

在精确算术下已被证明正确的几何算法,若直接使用浮点数实现,仍可能失效。如果三个点几乎共线,用于判定方向的行列式在计算中可能因相消而得到错误的符号。扫描线算法随后可能维持一种不可能成立的次序;三角剖分算法可能生成相互重叠的三角形;平面细分结构中可能出现不一致的邻接关系。这类故障涉及组合结构,而不只是显示坐标中的微小误差。

IEEE 754浮点运算标准对浮点算术的运算作出了精确定义,但大多数实数计算仍然涉及舍入。采用固定容差,例如将所有绝对值小于 10−910^{-9} 的数都视为零,并不是通用的解决办法。容差的含义会随坐标尺度而变化,而且多次独立进行的容差比较可能违反传递性。某种关系在一次测试中表现得如同相等关系,却可能在经过代数上等价的改写后表现不同。

精确几何计算旨在作出可靠的组合判定,通常不要求从一开始就精确计算每一个中间坐标。过滤式谓词首先使用快速浮点运算,并给出经过严格保证的误差界。如果该误差界足以确定结果的符号,就接受这一结果;否则,继续以更高精度或精确算术进行计算。乔纳森·谢夫丘克于20世纪90年代发表的自适应方向谓词和圆内判定谓词,使用浮点数展开实现了这一原理,产生了广泛影响。

即使使用精确算术,也需要单独制定处理退化情形的策略。精确求值可能正确地返回零,此时算法仍须在若干有效的结构选择之间作出决定。由赫伯特·埃德尔斯布伦纳和恩斯特·米克提出的简单性模拟,通过精心安排先后次序的符号扰动进行建模。它将有歧义的构型替换为附近一个一致的非退化构型,而不一定需要在数值上修改坐标。当预期输出允许作出这种选择时,这种方法是合适的;但如果重叠或共享边界对应用具有重要意义,它就不能替代对这些情形的显式表示。

可靠的软件还会将几何内核、组合结构和应用层假设分离。计算几何算法库通常简称为 CGAL,提供算法和数据结构,并允许配置几何内核,包括采用精确计算和过滤式计算的内核。测试必须覆盖共线和共圆输入、重复点、极端坐标尺度以及无效几何数据。形式验证可以增强对特定组件的可靠性保证,但仅证明谓词正确,并不能确立整个几何处理流程的正确性。

应用、动态场景与持续研究

地理信息系统利用几何算法进行地图叠加、行政区边界求交、缓冲区计算和空间查询。这些操作必须区分几何本身与坐标参考系。投影地图上的直线段不一定是地球表面的测地线,而根据角坐标计算出的面积也不是通常意义上的平面面积。稳健的多边形叠加还需要一致地处理孔洞、公共边界以及几乎重合的边。

工程应用将几何建模与仿真和制造相结合。计算机辅助设计利用曲线、曲面和边界结构表示形状;计算几何则提供求交、修剪、网格生成和碰撞检测算法。三维打印需要用平面对实体进行切片,并组装切片所得的轮廓等操作。在电子设计自动化中,几何方法支持版图检查、空间冲突检测和布线,但制造规则与布线约束也引入了额外的离散结构。

计算机图形学利用空间层次结构和相交测试,实现光线追踪、可见性判定和交互式碰撞处理。计算机视觉和摄影测量从图像生成点云,随后需要进行邻域搜索、曲面重建、简化和网格修复。几何算法并不能消除测量中的不确定性:重建曲面取决于采样密度、噪声、观测缺失情况,以及对真实形状所作的假设。提供理论保证的方法通常会明确说明采样条件。

动态几何研究支持插入、删除或运动的结构。动态最近邻结构会随着站点的添加或移除而变化。相比之下,运动数据结构利用证书来维护连续运动对象的某项性质;证书是一组条件,只要这些条件成立,当前的组合结构就仍然正确。预测到的证书失效会触发更新。衡量其效率时,不仅要考虑运行时间,还要考虑所维护的证书数量、所处理的事件数量,以及结构实际发生变化的次数。

并行算法与外存算法针对不同的瓶颈。并行计算可以加速相互独立的查询或分区构建,而图形处理器则更适合大批量的规则操作。不规则更新、同步和精确算术可能限制直接加速的效果。对于规模超过主存容量的数据集,减少存储层级之间的数据传输,可能比减少算术运算更为重要。

持续受到关注的理论问题包括:几何排列和范围搜索的更紧界、高效的动态结构、高维空间中的近似方法,以及代数决策模型与基于机器字的计算之间的关系。3SUM问题是几何问题条件性困难性结论的重要来源。这类归约并不能证明无条件的二次下界,其含义取决于所采用的具体猜想和计算模型。其他活跃研究方向则致力于设计在理论保证中考虑测量噪声、精度限制、流式输入,以及空间数据内在复杂度而非环境复杂度的算法。