Comparison of region approximation techniques based on Delaunay triangulations and Voronoi diagrams

Michael Barclay and Antony Galton

Computers, Environment and Urban Systems, Volume 32 (2008), 261-267.

Abstract

Region approxiation techniques based on constructions from sample data ponts, i.e., points whose position is known and which are known to be inside or outside the region of interest, can be advantageous in a variety of applications. This paper compares two different constructions and presents results from a Monte Carlo model that shows that the construction based on mid points of edges in a Delaunay triangulation produces the lowest errors. These errors are some 10% less than those produced by the Voronoi diagram construction which appears to be more widely used at present. A consideration of the basic geometries of the different constructions leads to an expression for approximating the expected error in the case of a random point distribution. ... Predictions from this expression agree well with the results from the Monte Carlo model. The case of finite as well as infinite radius of curvature is considered and some possible improvements on the constructions modelled are suggested.


Antony Galton
Last modified: Mon Mar 29 13:05:08 BST 2010