Ariel Herbert-Voss, University of Utah
Mathematical Sciences
A typical problem in numerical analysis is finding a smooth interpolation of a given data set such that information at extended positions can be evaluated. When extended to higher dimensions, there are few such algorithms available for practical use. Drawing from techniques used in geometric modeling we developed a practical algorithm with improved complexity by implementing the techniques in a query model as part of a MATLAB software package. From initial input data the algorithm builds a d-dimensional cell complex using Delaunay triangulation. Each cell has an associated interpolation function that satisfies Lipschitz continuity for each new point. During query time the user specifies a query point and the algorithm returns the interpolated function value. To reduce complexity related to point location within the cell complex, we implemented a binary tree search based on hyperplane decision criteria. Efficiency analysis completed using benchmark data sets indicated that the decision tree algorithm improved the efficiency from O(N) to O(N log N). This algorithm is the first of its kind that can be used on actual data sets and is the first implemented as a MATLAB package.