A new insertion sequence for incremental Delaunay triangulation

Jian Fei Liu, Jin Hui Yan, S. H. Lo

Research output: Contribution to journalArticlepeer-review


Incremental algorithm is one of the most popular procedures for constructing Delaunay triangulations (DTs). However, the point insertion sequence has a great impact on the amount of work needed for the construction of DTs. It affects the time for both point location and structure update, and hence the overall computational time of the triangulation algorithm. In this paper, a simple deterministic insertion sequence is proposed based on the breadth-first-search on a Kd-tree with some minor modifications for better performance. Using parent nodes as search-hints, the proposed insertion sequence proves to be faster and more stable than the Hilbert curve order and biased randomized insertion order (BRIO), especially for non-uniform point distributions over a wide range of benchmark examples.

Original languageEnglish (US)
Pages (from-to)99-109
Number of pages11
JournalActa Mechanica Sinica/Lixue Xuebao
Issue number1
StatePublished - Feb 1 2013
Externally publishedYes


  • Incremental Delaunay triangulation algorithms
  • Insertion sequences
  • Kd-tree

ASJC Scopus subject areas

  • Computational Mechanics
  • Mechanical Engineering

Fingerprint Dive into the research topics of 'A new insertion sequence for incremental Delaunay triangulation'. Together they form a unique fingerprint.

Cite this