A SEQUENTIAL ALGORITHM FOR  CONSTRUCTING THE DELAUNAY TRIANGULATION

Trịnh Minh Đức

doi:10.34238/tnu-jst.9487

A SEQUENTIAL ALGORITHM FOR CONSTRUCTING THE DELAUNAY TRIANGULATION

About this article

Received: 28/12/23 Revised: 28/03/24 Published: 29/03/24

Authors

Trinh Minh Duc , TNU - University of Information and Communication Technology

Abstract

The problem of constructing Delaunay triangulation is one of the important problems in Computational Geometry. The Delaunay triangulation has been used widely in computational geometry and extended to other multi-purpose domains, for example, GIS, terrain modelling, computer graphics, pattern recognition, finite element analysis… As a result, developing fast and effective algorithms to construct the Delaunay triangulation is becoming more and more important. There are a variety of sequential algorithms implemented effectively for constructing the Delaunay triangulation. In this paper, we present a sequential algorithm for constructing the Delaunay triangulation of a finite planar point set based on divide-and-conquer stratery. In particular, we use a restricted area of the examination of points for testing the circle criterion. The efficiency of the proposed algorithm is verified by comparing its performance with the Delaunay triangulation procedure given by O’Rourke. The results show that the implementation of our algorithm significantly achieves better speedups over O’Rourke’s code.

Keywords

Delaunay triangulation; Triangulation; Divide-and-conquer; Voronoi diagram; Computational geometry

Full Text:

PDF (Tiếng Việt)

References

[1] K. H. Huebner, D. L. Dewhirst, D. E. Smith, and T. G. Byrom, The Finite Element Method for Engineers. Wiley, New York, NY, USA, 2001.

[2] L. Tang, C. Ren, Z. Liu, and Q. Li, “A Road Map Refinement Method Using Delaunay Triangulation for Big Trace Data,” ISPRS International Journal of Geo-Information, vol. 6, no. 2, pp. 141-153, 2017.

[3] M. Flores, G. Torres, G. García, and M. Licona, “Fingerprint verification methods using delaunay triangulations,” International Arab Journal of Information Technology, vol. 14, pp. 346-354, 2017.

[4] S. Fortune, “A sweepline algorithm for Voronoi diagrams,” Algorithmica, vol. 2, pp. 153-174, 1987.

[5] R. A. Dwyer, “A faster divide-and-conquer algorithm for constructing Delaunay triangulations,” Algorithmica, vol. 2, pp. 137-151, 1987.

[6] L. Guibas and J. Stolfi, “Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,” ACM Transactions on Graphics, vol. 4, no. 2, pp. 74-123, 1985.

[7] P. Green and R. Sibson, “Computing Dirichlet tessellations in the plane,” Computer Journal, vol. 21, pp. 168-173, 1977.

[8] M. -B.Chen, T. -R. Chuang, and J. -J. Wu, “Parallel divide-and-conquer scheme for 2D Delaunay
triangulation,” Concurrency and Computation: Practice and Experience, vol. 18, pp. 1595-1612, 2006.

[9] P. T. An and L. H. Trang, “A Parallel Algorithm Based on Convexity for the Computing
of Delaunay Tessellation,” Numerical Algorithms, vol. 59, no. 3, pp. 347–357, 2012.

[10] W. Wu, Y. Rui, F. Su, L. Cheng, and J. Wang, “Novel parallel algorithm for constructing Delaunay triangulation based on a twofold-divide-and-conquer scheme,” GIScience & Remote Sensing, vol. 51, no. 5, pp. 537-554, 2014.

[11] D. T. Lee and B. J. Schachter, “Two Algorithms for Constructing a Delaunay Triangulation,” International Journal of Computer and Information Sciences, vol. 9, no. 3, pp. 219-242, 1980.

[12] M. I. Shamos and D. Hoey, “Closest-point Problems,” Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975, pp. 151-162.

[13] P. T. An, “Method of orienting curves for determining the convex hull of a finite set of points in the plane,” Optimization, vol. 59, no. 2, pp. 175-179, 2010.

[14] J. O’Rourke, Computational Geometry in C, Second edition. Cambridge University Press, 1998.

[15] M. de Berg, Computational Geometry Algorithms and Applications. Springer, Germany, 2000.

[16] A. Okabe, B. Boots, and K. Sugihara, Spatial Tessellations: Concepts and Applications of voronoi Diagrams, First edition, John Winley and Sons Ltd, 1992.

DOI: https://doi.org/10.34238/tnu-jst.9487

Refbacks

There are currently no refbacks.



Remember me