A functional language to implement the divide-and-conquer Delaunay triangulation algorithm

摘要

This paper investigates the implementation of a functional language algorithm for the divide-and-conquer Delaunay triangulation. The global aim is to improve its performance. Up to now it is not available an algorithm that can build the Delaunay triangulation for n points, with non-uniform distribution, with time complexity lower than O(n log n). With this purpose an improved algorithm in C by Geoff Leach was selected, this algorithm improved the Guibas–Stolfi algorithm by a factor of 4–5. The programming language selected was OCaml—Objective Categorical Abstract Machine Language, taking as a base the good results obtained in other computational mathematics research works. The expectation is that the code written in OCaml can solve the triangulation in less time and more efficiently than the C written code.