平面非相交曲线的Voronoi Diagrams泛化及高效算法问询

定义明确性 #

• 对于平面内非相交的简单曲线：这个问题定义完全明确。平面中任意一点到曲线的欧氏距离，是该点到曲线上所有点的距离最小值——只要曲线是闭集（非相交简单曲线基本都满足），这个最小值必然存在。即使存在曲线上多个点到目标点距离相等，也不影响Voronoi区域的划分逻辑：每个区域包含所有到对应曲线距离严格小于到其他曲线距离的点，而区域边界则是到至少两条曲线距离相等的点的轨迹，整个划分逻辑和点集Voronoi图一致，没有歧义。
• 对于线段：作为曲线的特殊情况，定义更清晰。线段是紧致闭集，任意点到线段的最近点要么是垂足（在线段内部），要么是线段的端点，距离计算无模糊性，对应的Voronoi区域划分自然完全明确。

高效计算算法 #

• 线段集合的Voronoi图（又称线段Voronoi图）是计算几何中的经典问题，有成熟的高效解法：
  • 可以基于Fortune算法的思想扩展实现，通过处理线段端点、垂足等特殊情况，将线段的Voronoi图生成过程转化为类似点集的扫描线过程，时间复杂度可达O(n log n)（n为线段数量）。
  • 生成的Voronoi图结构比点集的更复杂，包含直线段、抛物线弧等元素，但算法的可行性和效率都经过了验证，是工业界和学术界常用的工具。
• 一般非相交曲线：如果是分段光滑曲线（比如多段圆弧、二次曲线拼接而成），可以拆分为光滑曲线段逐个处理，但目前没有像Fortune算法那样通用的O(n log n)级算法。针对特定类型的曲线（如圆弧、椭圆弧），有专门的扩展算法，时间复杂度根据曲线类型和数量有所不同，大致在O(n log n)到O(n²)之间。

与混淆概念的区别 #

你提到搜索时遇到的“弯曲度量空间”或“弯曲区域”问题，和当前问题核心不同：前者是修改了距离度量的定义（比如用曲面上的测地线距离），而你的问题是保持欧氏距离不变，仅将生成元从点替换为曲线/线段，属于“对象Voronoi图”的子类，这类问题的研究聚焦于生成元的形态扩展，而非度量空间的改变。

内容的提问来源于stack exchange，提问作者Yuval S