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

Region approximation techniques based on constructions from sample data points, 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. The expression takes the formERMS=kdS4+lo232Slc2lo2-1,where S is the average point spacing, lo is the length of region boundary being approximated (the optimum length for the construction), and lc the length of the constructed line approximating the boundary. The constant kd accounts for the non-uniform spacing of the points in the distribution and has a value of about 1.1 for a random 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.