Delaunay三角剖分是否包含所有外接圆为空的三角形

Question

我有一组点，我想找到所有有空外接圆的三角形。我认为Delaunay三角测量就是这么做的。

我读过一些关于这个主题的论文，但我不确定Delaunay三角测量是否能找到所有这样的三角形。如果是，那么我如何从数学上证明这一点？

Answer 1

这里有一个证明：假设p，q，r是p的三个不在一条公共线上的点，使得p的其他点都不在由p，q、r定义的圆C中。那么C的中心是p的Voronoi图V（p）的Voronoy节点。上面提到的节点的对偶就是你的三角形。

关于Voronoi图和Delaunay三角图的基本性质，请参阅de Berg，Cheong，van Krevild，Overmars的"计算几何"。