An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm

References

• AURENHAMMER , F. 1991 . Voronoi diagrams—a survey of a fundamental geometric data structure . ACM Computing Surveys , 23 : 345 – 405 .
   Web of Science ®Google Scholar
• BENTLEY , J. L. , WEIDE , B. W. and ANDREW , C. Y. 1980 . Optimal expected time algorithms for the closest point problems . ACM Transactions on Mathematical Software , 6 : 563 – 580 .
   Web of Science ®Google Scholar
• BOISSONNAT , J. D. , DEVILLERS , O. , TEILLAUD , M. and YVINEC , M. 2000 . “ Triangulations in CGAL ” . In Computational Geometry 2000 , 11 – 18 . Hong Kong : ACM Press .
   Google Scholar
• CIGNONI , P. , MONTANI , C. and SCOPIGNO , R. 1992 . A merge-first divide and conquer algorithm for The Delaunay Triangulations , Internal Report C92/16 Pisa : CNUCE-CNR .
   Google Scholar
• ČUK , R. Construction of Voronoi diagrams using Fortune's method: a look on an implementation . 3rd Central European Seminar on Computer Graphics CESCG . pp. 27 – 36 . Budmerice, Slovak Republic .
   Google Scholar
• DE BERG , M. , VAN KREVELD , M. , OVERMARS , M. and SCHWARZKOFF , O. 1997 . Computational Geometry, Algorithms and Applications , Berlin : Springer-Verlag .
   Google Scholar
• DEVILLERS , O. ACM Symposium on Computer Geometry . 1998 . pp. 106 – 115 . Minneapolis : ACM Press .
   Google Scholar
• DWYER , R. A. 1987 . A faster divide-and-conquer algorithm for constructing Delaunay triangulations . Algorithmica , 2 : 137 – 151 .
   Web of Science ®Google Scholar
• ENDL , R. and SOMMER , M. 1994 . Classification of ray-generators in uniform subdivisions and octrees for ray tracing . Computer Graphics Forum , 13 : 3 – 19 .
   Web of Science ®Google Scholar
• FANG , T.-P. and PIEGL , L. 1992 . Algorithm for Delaunay triangulation and convex-hull cmputation using a sparse matrix . Computer Aided Design , 24 : 425 – 436 .
   Web of Science ®Google Scholar
• FANG , T.-P. and PIEGL , L. 1993 . Delaunay triangulation using a uniform grid . Computer & Graphics Applications , 13 : 36 – 47 .
   Web of Science ®Google Scholar
• FARIN , G. and HANSFERD , P. 1998 . The Geometry Toolbox for Graphics and Modelling , Massachussetts : A. K Peters .
   Google Scholar
• FOLEY , J. D. , VAN DAM , A. , FEINER , S. K. and HUGHES , J. F. 1990 . Computer Graphics—Principles and Practice , Reading : Addison-Wesley .
   Google Scholar
• FORTUNE , S. 1987 . A sweep-line algorithm for Voronoi diagrams . Algorithmica , 2 : 153 – 174 .
   Web of Science ®Google Scholar
• FUJIMOTO , A. , TANAKA , T. and IWATA , K. 1986 . ATRS: accelerated ray-tracing system . IEEE Computer Graphics and Applications , 6 : 16 – 26 .
   Web of Science ®Google Scholar
• GARLAND , M. and HECKBERT , P. S. 1995 . Fast Polygonal Approximation of Terrains and Height Fields , Technical Report CMU-CS-95-181 Pittsburgh, , USA : Carnegie Mellon University . accessible on
   Google Scholar
• GUIBAS , L. and STOLFI , J. 1985 . Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams . ACM Transactions on Graphics , 4 : 75 – 123 .
   Web of Science ®Google Scholar
• GUIBAS , L. , KNUTH , D. and SHARIR , M. 1992 . Randomised incremental construction of Delaunay and Voronoi diagrams . Algorithmica , 7 : 381 – 413 .
   Web of Science ®Google Scholar
• HOFFMANN , C. M. 1989 . Geometric & Solid Modelling , San Mateo : Morgan Kaufmann .
   Google Scholar
• HUANG , C.-W. and SHIN , T.-Y. 1998 . Improvements on Sloan's algorithm for constructing Delaunay triangulations . Computers & Geosciences , 24 : 193 – 196 .
   Web of Science ®Google Scholar
• KATAJAINEN , J. and KOPPINEN , M. 1988 . Constructing Delaunay triangulations by merging buckets in quadtree order . Fundamenta Informaticae , 11 : 275 – 288 .
   Google Scholar
• KOLINGEROVÁ , I. and ŽALIK , B. 2002 . Improvements to randomized incremental Delaunay insertion . Computer & Graphics Journal , 26 : 477 – 490 . accepted in
   Web of Science ®Google Scholar
• LAWSON , C. L. 1977 . “ Software for C1 Surface Interpolation ” . In Mathematical Software III , Edited by: Price , J. R. 161 – 194 . New York : Academic Press .
   Google Scholar
• LEE , D. T. and SCHACHTER , B. J. 1980 . Two algorithms for constructing a Delaunay Triangulation . International Journal of Computer and Information Sciences , 9 : 219 – 242 .
   Google Scholar
• MÜCKE , E. P. , SAIAS , L. and ZHU , B. 1996 . “ Fast-randomized point location without preprocessing and two- and three-dimensional Delaunay triangulations ” . In Computational Geometry '96 , 274 – 283 . Philadelphia : ACM Press .
   Google Scholar
• PREPARATA , F. P. and SHAMOS , M. I. 1985 . Computational Geometry: An Introduction , New York : Springer .
   Google Scholar
• SAMET , H. 1989 . The Design and Analysis of Spatial Data Structures , Reading : Addison Wesley .
   Google Scholar
• SAMET , H. 1990 . Applications of Spatial Data Structures , Reading : Addison Wesley .
   Google Scholar
• SHEWCHUK , J. R. 1996 . “ Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator ” . In First Workshop on Applied Computational Geometry , 124 – 133 . Philadelphia : Association of Computing Machinery .
   Google Scholar
• SHEWCHUK , J. R. 2001 . A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator
   Google Scholar
• SKALA , V. and KUCHAŘ , M. 2001 . “ The Hash function and the principle of duality ” . In Computer Graphics International 2001 , 167 – 174 . Hong Kong : IEEE Computer Society .
   Google Scholar
• SLOAN , S. W. 1987 . A fast algorithm constructing Delaunay triangulations in the plane . Advanced Engineering Software and Workstations , 9 : 34 – 55 .
   Web of Science ®Google Scholar
• Su , P. and DRYSDALE , R. L. S. A comparison of sequential Delaunay triangulation algorithms . Proceedings of 11th Annual Symposium on Computational Geometry . pp. 61 – 70 . Vancouver Association of Computing Machinery .
   Google Scholar
• SUNG , K. A DDA octree traversal algorithm for ray tracing . EUROGRAPHICS'91: Proceedings of the European Computer Graphics Conference and Exhibition . pp. 73 – 85 . Vienna : North Holland .
   Google Scholar
• ŽALIK , B. 1999 . A topology construction from line drawing using a uniform plane subdivision technique . Computer Aided Design , 31 : 335 – 338 .
   Web of Science ®Google Scholar