Delaunay Triangulation for Outlier Detection and Determining Smoothness

Spatial outlier detection is a method used to filter data before processing. There are many different techniques to solving this problem of detection. In this paper we will look specifically at a technique using Delaunay triangulation to both filter the data and give a rough estimate of its smoothness. Outliers skew data and produce unreliable datasets and are caused by a variety of factors. Removing outliers is easily done in one, two, and even three dimensions as you can visualize them. But what about 4-dimensions or even higher? Delaunay triangulation is an algorithm used primarily in mathematics and computational geometry which connects a set of n-dimensional data points in such a way to create a mesh of evenly spaced, non-overlapping triangles. This was used in a paper by Min-qi Zheng in 2008, which used this method to calculate and detect spatial outliers in a data set, which he called DT_SOF, or Delaunay Triangulation Spatial Outlier Factor. My research has been implementing an algorithm to find a way to determine the smoothness of a set of data. There were different methods tested such as projection using the cross product of vectors, the random cut algorithm, standard deviation, but in the end all failed. To achieve the smoothness factor of a dataset, the data is first pre-processed through the DT_SOF algorithm and then calculated using the sum of Delaunay edges divided by the number of data points, which has proven to be the best way to calculate smoothness so far. Winner, College of the Sciences Presentation Award