HCPO: an efficient insertion order for incremental Delaunay triangulation
作者： Sheng Zhou , Christopher B. Jones
DOI: 10.1016/J.IPL.2004.09.020
关键词:
摘要: ved. Among the five flavors [15] of sequential 2D Delaunay triangulation algorithms, incremental insertion methods (e.g., [8]) are most popular mainly because they potentially dynamic, simple to implement and easy be generalized higher dimensions. However, normally not regarded as among fastest methods. The basic principle constructing (DT) by is well known (see textbooks such [2] for detail). A point inserted into in two steps: location finds triangle or component which lies, update restore property triangulation. Point dominated an orientation (nor-
core.ac.uk
elsevier.com
sci-hub.se 参考文章(14)
S.W. Sloan, A fast algorithm for constructing Delaunay triangulations in the plane Advances in Engineering Software. ,vol. 9, pp. 34- 55 ,(1987) , 10.1016/0141-1195(87)90043-X
P. J. Green, R. Sibson, Computing Dirichlet Tessellations in the Plane The Computer Journal. ,vol. 21, pp. 168- 173 ,(1978) , 10.1093/COMJNL/21.2.168
Rex A. Dwyer, A faster divide-and-conquer algorithm for constructing delaunay triangulations Algorithmica. ,vol. 2, pp. 137- 151 ,(1987) , 10.1007/BF01840356
Michael I. Shamos, Franco P. Preparata, Computational Geometry: An Introduction ,(1978)
Leonidas Guibas, Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi ACM Transactions on Graphics. ,vol. 4, pp. 74- 123 ,(1985) , 10.1145/282918.282923
Leonidas J. Guibas, Donald E. Knuth, Micha Sharir, Randomized incremental construction of Delaunay and Voronoi diagrams Algorithmica. ,vol. 7, pp. 381- 413 ,(1992) , 10.1007/BF01758770
Ernst P. Mücke, Isaac Saias, Binhai Zhu, Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations symposium on computational geometry. ,vol. 12, pp. 274- 283 ,(1996) , 10.1145/237218.237396
Takao Ohya, Masao Iri, Kazuo Murota, A fast voronoi-diagram algorithm with quaternary tree bucketing Information Processing Letters. ,vol. 18, pp. 227- 231 ,(1984) , 10.1016/0020-0190(84)90116-9
Olivier Devillers, Sylvain Pion, Monique Teillaud, Walking in a triangulation Proceedings of the seventeenth annual symposium on Computational geometry - SCG '01. pp. 106- 114 ,(2001) , 10.1145/378583.378643
Jonathan Richard Shewchuk, Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates, Discrete and Computational Geometry. ,vol. 18, pp. 305- 363 ,(1997) , 10.1007/PL00009321