✦ LIBER ✦

A note on finding nearest neighbours and constructing Delaunay triangulation in the plane

✍ Scribed by Du, Chongjiang

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 135 KB
Volume: 14
Category: Article
ISSN: 1069-8299
DOI: 10.1002/(sici)1099-0887(199809)14:9<871::aid-cnm195>3.0.co;2-6

No coin nor oath required. For personal study only.

✦ Synopsis

This paper deals with the largest interior angle property of the Voronoi nearest neighbours and the Delaunay triangulation in two dimensions. It is indicated that each interior angle opposite to an edge of a Delaunay triangle is the largest of the interior angles opposite the same edge of all possible triangles on the same side. Based on this property, the algorithms for ®nding the Voronoi neighbours of a point (site) and for constructing the Delaunay triangulation are presented. The algorithms are especially useful for the meshless methods developed in recent years.