Delaunay triangulation
Until 2005
Delaunay triangulation is one of the classical problems in computational geometry. We have intensively studied various approaches of how to improve the speed of the algorithms. In 2005 we have published the fastest algorithm up to that time, based on sweep-line paradigm. For this algorithm the source code is available, and it may be used freely for any kind of non-commercial use. The benchmark data sets are attached, too.
Papers:
Kolingerová, B. Žalik. Improvements to randomized incremental Delaunay insertion. Computers & Graphics, 26(3), 2002, 477-490.
B. Žalik, I. Kolingerová. An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm. The International Journal of Geographical Information Science, 17(2), 2003, 119-138.
M. Zadravec, B. Žalik. An almost distribution-independent incremental Delaunay triangulation algorithm. Visual Computer, 21(6), 2005, 384-396.
I. Kolingerová, B. Žalik. Reconstructing domain boundaries within a given set of points using Delaunay triangulation. Computers & Geosciences, 32(9), 2006, 1310-1319.
D. Špelič, F. Novak, B. Žalik. Delaunay Triangulation Benchmarks. Journal of Electrical Engineering, 59(1), 2008, 49-52.
V. Domiter, B. Žalik. Sweep-line algorithm for constrained Delaunay triangulation. International Journal of Geographical Information Science, 22(4), 2008, 449-462.
D. Špelič, F. Novak, B. Žalik. Educational support for computational geometry course - The Delaunay triangulation tester. International Journal of Engineering Education, 25(1), 2009, 93-101.
and
B. Žalik. An efficient sweep-line Delaunay triangulation algorithm. Computer-Aided Design, 37(10), 2005, 1027-1038.