Delaunay Triangulation Algorithms Useful for Multibeam Echosounding
Publication: Journal of Surveying Engineering
Volume 129, Issue 2
Abstract
The Delaunay triangulation is a widely appreciated and investigated mathematical model for topographic surface representation. After a brief theoretical description, six possible basic algorithms to construct a Delaunay triangulation are analyzed and properties that can be exploited for multibeam echosounder data processing are investigated. Two concepts will be treated in more depth: the divide-and-conquer construction algorithm and the incremental method. The calculation speed of the divide-and-conquer method makes it an ideal candidate to construct the initial triangulation of multibeam data. Its runtime performance is compared to that of the incremental algorithm to demonstrate this. The algorithm’s merge step appears to be useful also in replacing triangulated areas of existing triangulations by new data. The incremental algorithm does not seem an effective construction method but it can easily be adapted to accommodate insertion of individual vertices into an existing triangulation and as such it is useful for editing purposes.
Get full access to this article
View all available purchase options and get full access to this article.
References
Cressie, N. (1993). Statistics for spatial data, revised Ed., Wiley, New York.
Dwyer, R. A.(1987). “A faster divide-and-conquer algorithm for constructing Delaunay triangulations.” Algorithmica, 2(2), 137–151.
Fortune, S.(1987). “A sweepline algorithm for Voronoi diagrams.” Algorithmica, 2, 153–174.
Guibas, L., Knuth, E., and Sharir, M.(1992). “Randomized incremental construction of Delaunay and Voronoi diagrams.” Algorithmica, 7, 381–413.
Guibas, L., and Stolfi, J.(1985). “Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.” ACM Trans. Graphics, 4(2), 74–123.
Harel, D. (1987). “The efficiency of algorithms.” Algorithmics. The spirit of computing, Addison-Wesley, Workingham, England, 119–147.
Lawson, C. L.(1972). “Transforming triangulations.” Discrete Math., 3, 365–372.
Lee, D. T., and Schachter, B. J.(1980). “Two algorithms for constructing a Delaunay triangulation.” Int. J. Comput. Inf. Sci., 9(3), 219–242.
Mirante, A., and Weingarten, N.(1982). “The radial sweep algorithm for constructing triangulated irregular networks.” IEEE Comput. Graphics Appl., 2(3), 11–21.
Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. (1999). Spatial tessellations: Concepts and applications of Voronoi diagrams, 2nd Ed., Wiley, New York.
O’Rourke, J. (1998). Computational geometry in C, 2nd Ed., Cambridge University Press, Cambridge, England.
Shamos, M. I., and Hoey, D. (1975). “Closest point problems.” Proc., 16th Annual IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Berkeley, Calif., 151–162.
Shewchuck, J. R. (1996). “Triangulation algorithms and data structures.” 〈http://www.cs.cmu.edu/∼quake/tripaper/triangle2.html〉.
Sibson, R.(1978). “Locally equiangular triangulations.” Comput. J. (UK), 21, 243–245.
Su, P., and Drysdale, R. L. S. (1996). “A comparison of sequential Delaunay triangulation algorithms.” 〈http://www.cs.berkeley.edu/∼jrs/mesh/present.html〉.
Watson, D. F.(1981). “Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes.” Comput. J. (UK), 24(2), 167–172.
Information & Authors
Information
Published In
Journal of Surveying Engineering
Volume 129 • Issue 2 • May 2003
Pages: 79 - 84
Copyright
Copyright © 2003 American Society of Civil Engineers.
History
Received: Apr 12, 2001
Accepted: Nov 15, 2001
Published online: Apr 15, 2003
Published in print: May 2003
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.