Editing Delaunay triangulation (section)

===Divide and conquer===
A [[divide and conquer algorithm]] for triangulations in two dimensions was developed by Lee and Schachter and improved by [[Leonidas J. Guibas|Guibas]] and [[Jorge Stolfi|Stolfi]]{{r|GS1985}}{{r|Peterson}} and later by Dwyer.{{r|Dwyer1987}}  In this algorithm, one recursively draws a line to split the vertices into two sets. The Delaunay triangulation is computed for each set, and then the two sets are merged along the splitting line.  Using some clever tricks, the merge operation can be done in time {{math|O(''n'')}}, so the total running time is {{math|O(''n'' log ''n'')}}.{{r|Leach1992}}

For certain types of point sets, such as a uniform random distribution, by intelligently picking the splitting lines the expected time can be reduced to {{math|O(''n'' log log ''n'')}} while still maintaining worst-case performance.

A divide and conquer paradigm to performing a triangulation in {{mvar|d}} dimensions is presented in "DeWall: A fast divide and conquer Delaunay triangulation algorithm in E<sup>''d''</sup>" by P. Cignoni, C. Montani, R. Scopigno.{{r|CMS1998}}

The divide and conquer algorithm has been shown to be the fastest DT generation technique sequentially.<ref>A Comparison of Sequential Delaunay Triangulation Algorithms {{cite web |url=http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf |title=Archived copy |access-date=2010-08-18 |url-status=dead |archive-url=https://web.archive.org/web/20120308043808/http://www.cs.berkeley.edu/%7Ejrs/meshpapers/SuDrysdale.pdf |archive-date=2012-03-08 }}</ref><ref>{{cite web|url=https://www.cs.cmu.edu/~quake/tripaper/triangle2.html|title=Triangulation Algorithms and Data Structures|website=www.cs.cmu.edu|access-date=25 April 2018|url-status=live|archive-url=https://web.archive.org/web/20171010072746/https://www.cs.cmu.edu/~quake/tripaper/triangle2.html|archive-date=10 October 2017}}</ref>