This paper presents a new way to compute the Delaunay triangulation of a planar set P of n points, using sweep-circle technique combined with the standard recursive edge-flipping. The algorithm sweeps the plane by an increasing circle whose center is a fixed point in the convex hull of P. Empirical results and comparisons show that it reduces the number of incircletests and edge-flips, and it is efficient in practice.

1. Adam B, Kauffmann P, Schmitt D, Spehner JC. An increasing-circle sweep-algorithm to construct the Delaunay diagram in the plane. In: Proceedings of CCCG; 1997..
2. Barber CB. Computational geometry with imprecise data and arithmetic. PhD thesis. Princeton; 1993..
3. E. Béchet, J.C. Cuilliere and F. Trochu, Generation of a finite element MESH from stereolithography (STL) files. Comput-Aid Des, 34 (2002), pp. 1– 17.Article | PDF (3067 K) | | View Record in Scopus | | Cited By in Scopus (48)
4. M.D. Berg, Kreveld M. van, M. Overmars and O. Schwarzkopf, Computational geometry, algorithms and applications, Springer-Verlag (2008).
5. Biniaz A. Circumcircular range searching in higherorder Delaunay triangulations. In: Proceedings of JCCGG; 2009..
6. Biniaz A. Slope preserving terrain simplification—an experimental study. In: Proceedings of CCCG; 2009..
7. A. Biniaz and Gh. Dastghaybifard, Drainage reality in terrains with higher order Delaunay triangulations Advances in 3D geoinformation systems, Springer-Verlag (2008), pp. 199–213.
8. Biniaz A, Dastghaybifard Gh. Slope fidelity in terrains with higher order Delaunay triangulations. In: Proceedings of WSCG; 2008..
9. Biniaz A, Dastghaybifard Gh. A comparison of plane sweep Delaunay triangulation algorithms. In: Proceedings of CSICC; 2007..
10. K.Q. Brown, Voronoi diagrams from convex hulls. Inf Proc Lett, 5 (1979), pp. 223– 228. Article | PDF (852 K) | | View Record in Scopus | | Cited By in Scopus (60)
11. S.W. Cheng and S.H. Poon, Three-dimensional Delaunay mesh generation. Discr Comput Geom, 36 (2006), pp. 419–456. | View Record in Scopus | | Cited By in Scopus (7)
12. T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to algorithms, MIT Press/McGraw-Hill, Cambridge (MA) (1990).
13. F. Dehne and R. Klein, A sweep-circle algorithm for Voronoi diagrams (extended abstract), Springer-Verlag, Berlin (1988).
14. R.A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time. Discr Comput Geom, 6 (1991), pp. 343–367. | View Record in Scopus | | Cited By in Scopus (43)
15. R.A. Dwyer, A faster divide-and-conquer algorithm for constructing Delaunay triangulations. Algorithmica, 2 (1987), pp. 137– 151. | View Record in Scopus | | Cited By in Scopus (11)
16. S. Fortune, Voronoi diagrams and Delaunay triangulations, J.E. Goodman, J. O’Rourke, Editors , Handbook of discrete and computational geometry, CRC Press LLC, Boca Raton (FL) (1997), pp. 377–388 [chapter 20].
17. S. Fortune, A sweep-line algorithm for Voronoi diagrams. Algorithmica, 2 (1987), pp. 153–174. | View Record in Scopus | | Cited By in Scopus (283)
18. G. Gonçalves, P. Julien, S. Riazano and B. Cervelle, Preserving cartographic quality in DTM interpolation from contour lines. ISPRS J Photogr Remote Sen, 56 (2002), pp. 210–220. Article | PDF (434 K) | | View Record in Scopus | | Cited By in Scopus (7)
19. J. Gudmundsson, M. Hammar and Kreveld M. van, Higher order delaunay triangulations. Comput Geom: Theory Appl, 23 (2002), pp. 85–98. Article | PDF (205 K) | | View Record in Scopus | | Cited By in Scopus (22)
20. J. Gudmundsson, H. Haverkort and Kreveld M. van, Constrained higher order Delaunay triangulations. Comput Geom: Theory Appl, 30 (2005), pp. 271–277. Article | PDF (182 K) | | View Record in Scopus | | Cited By in Scopus(6)
21. L. Guibas, D. Knuth and M. Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7 (1992), pp. 381–413.
22. L. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans Graphics, 4 2 (1985), pp. 75–123.
23. Kok T. de, Kreveld M. van and M. Löffer, Generating realistic terrains with higher-order Delaunay triangulations. Comput Geom: Theory Appl, 36 (2007), pp. 52–67.
24. I. Kolingerova and B. Žalik, Improvements to randomized incremental Delaunay insertion. Comput Graphics, 26 (2001), pp. 477–490.
25. C.L. Lawson, Software for C1 surface interpolation, J.R. Rice, Editor, Mathematical software III, Academic Press, New York (1997), pp. 161–194.
26. D.T. Lee and B.J. Schachter, Two algorithms for constructing a Delaunay triangulation. Int J Comput Inf Sci, 9 (1980), pp. 219–242.
27. A. Maus, Delaunay triangulation and the convex hull of n points in expected linear time. BIT, 24 (1984), pp. 151–163. | View Record in Scopus |
28. J.H. Park and H.W. Park, Fast view interpolation of stereo images using image gradient and disparity triangulation. Signal Process: Image Commun, 18 (2003), pp. 401–416. Article | PDF (1345 K) | | View Record in Scopus |
29. Philip J. The area of a random convex polygon. Tech report TRITA MAT 04 MA 07..
30. F.P. Preparata and M.I. Shamos, Computational geometry: an introduction, Springer, Berlin (1985).
31. J.R. Shewchuk, General-dimensional constrained delaunay and constrained regular triangulations. I: Combinatorial properties. Discr Comput Geom, 39 (2008), pp. 580–637. | View Record in Scopus |
32. J.R. Shewchuk, Lecture notes on Delaunay mesh generation, Univ. of Calif. at Berkeley (1999).
33. Shewchuk JR. Triangle: engineering a 2D quality mesh generator and Delaunay triangulator. In: Proceedings of SCG’96 (ACM symposium on computational geometry); 1996. p. 124–33..
34. Silva V. de, A weak characterisation of the Delaunay triangulation. Geomet Ded, 135 (2008), pp. 39–64.
35. Su P, Drysdale RLS. A comparison of sequential Delaunay triangulation algorithms. In: Proceedings of SCG’95 (ACM symposium on computational geometry); 1995. p. 61–70..
36. A.M. Tekalp and J. Ostermann, Face and 2-D mesh animation in MPEG-4. Signal Process: Image Commun, 15 (2000), pp. 387–421. Article | PDF (812 K) | | View Record in Scopus |
37. B. Žalik, An efficient sweep-line Delaunay triangulation algorithm. Comput-Aid Des, 37 (2005), pp. 1027–1038. Article | PDF (587 K) | | View Record in Scopus |
38. B. Žalik and I. Kolingerova, An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm. Int J Geograph Inf Sci, 17 (2003), pp. 119–138.

Computational geometry Delaunay triangulation In-circle test Recursive edge-flipping Sweep-line Sweep-circle