The goal of this research is to solve algorithmic problems from application areas by visualizing the problem data in terms of a related geometric space, using this visualization to develop an improved mathematical understanding of these problems, and combining this understanding with the techniques of computational geometry to develop efficient algorithms for the problems. Particular problem domains targeted by this project include (1) generation of unstructured quadrilateral and cuboid meshes for the finite element method; (2) robust methods for fitting hyperplanes or other geometric shapes to sets of data points; and (3) adaptive user interface problems, for example tuning the relative weights of parameters such as distance, travel time, or scenic value in a vehicle routing system, to make it produce routes that more closely match driver preferences. All of these areas relate to fundamental geometric problems of partitioning spaces by arrangements of curves or surfaces. A further connecting theme in the proposed research is the use of topological methods to separate global shape properties from local geometric attributes, and to provide a precise language for discussing these properties. The investigator will apply a conscious focus on computational topology to accelerate progress in geometric computing.
