三角剖分算法（triangulation algorithm），理学-计算机科学技术-计算机科学理论-算法-计算几何算法，求德洛奈三角剖分的算法。平面上的点集P的德洛奈三角剖分D(P)是使得在P中没有点严格处于D(P)中任意一个三角形外接圆的内部的三角剖分。简介德洛奈三角剖分（Delaunay triangulation）是1934年由俄国数学家B.德洛奈（Boris Delaunay）提出。在点集可能形成的三角剖分中，德洛奈三角剖分所形成的三角形的最小角最大。即德洛奈三角剖分能避免出现“极瘦角”。给定一个点集，如果所有点共线，则不存在德洛奈三角剖分；若有至少四点共圆，则德洛奈三角剖分不唯一。最简单的德洛奈三角剖分算法是翻边算法。但是这个算法的时间复杂度是O(n2)。Lawson提出了逐点插入和局部优化的算法，Bowyer和Watson在1981年也提出总体思路为逐点插入的算法，时间复杂度也较高。分治法最初由Lee和Schachter提出，然后由Guibas和Stolfi改进，最终由Dwyer完善，时间复杂度为O(nlogn)。