最小三角剖分（请擅长代数拓扑的朋友指点）

baixinbs

对于类似下面这样一个图，

注意我们只知道这个图的拓扑结构。
如何求它最小的三角划分（即用最少的三角形剖分它）？
例如下图就是一个它的三角剖分。

看起来这个问题好像和代数拓扑相关。当然用其他方法能求解更好。
另外，求近似解也可以。

hujunhua

我们知道一个凸 n 边形可以划分为 n-2 个三角形。
对于一个单连通域，公式(n-2)仍然适用。

程序如下：
1、先找到这样一个凸顶点，它的左右两个邻点的连线在域内。于是该连线将域分割成一个三角形和一个(n-1)边形。
2、对(n-1)边形重复上述操作，直到(n-1)=3。

步骤1中那样的凸顶点总是存在的，我一时还不知道怎么证明。

hujunhua

我可能会错题意了？
所谓图是包括内部的那些点的吧。题主是要求删减除粗线边界之外的连线，使之成为一个只有三角形面的平面图？

baixinbs

hujunhua 发表于 2015-11-26 15:48
我可能会错题意了？
所谓图是包括内部的那些点的吧。题主是要求删减除粗线边界之外的连线，使之成为一个只 ...

不要求所有的顶点都用。
就是在原图中有很多很多的三角形，我就用其中一部分三角形，覆盖整个区域。
你的想法很有启发，非常感谢。

hujunhua

反正得用既有的线和三角形，不能再连新线，是吧？

baixinbs

hujunhua 发表于 2015-11-28 10:14
反正得用既有的线和三角形，不能再连新线，是吧？

是的

Buffalo

乱用名词是很不好的习惯。
首先你这个所谓“拓扑结构”就是莫名其妙的。因为按你的说法这里的连线有明确的曲直之分，还有位置和交点，不管理解成拓扑学里的拓扑结构或者图论/计算机网络里的拓扑结构都不对。
然后看到要把一个图形分成三角块就联想到代数拓扑中的三角剖分也真是醉了。