Jer*_*Kun 13 algorithm computational-geometry chazelle-algorithm
由于Chazelle(1991),有一种用于在线性时间内对多边形进行三角测量的算法,但是,AFAIK,在一般的数学软件库中没有他的算法的任何标准实现.
有谁知道这样的实现？
Jas*_*ies 17
看到这个答案的问题强大的算法太复杂而无法实现:
根据Skiena(算法设计手册的作者)的说法,"[该]算法实施起来毫无希望."
我以前找过一个实现,但找不到一个.我认为可以安全地假设没有人因为其复杂性而实现它,并且我认为它也有相当大的常数因子,因此O(n lg n)对于具有较小常数因子的算法不会很好.