AF: Small: Subdivision Methods: Correctness and Complexity

Clemson University, Clemson SC

Investigators

Abstract

Subdivision-based algorithms can solve problems from a wide variety of applications in mathematics, computer science, and the sciences. For example, these types of algorithms are used in computer graphics, mathematical biology, computational geometry, mathematical modeling, robotics, machine learning, and mathematical computation. Subdivision-based algorithms are popular because they are relatively easy to describe and implement on a computer, and they are often efficient in practice. The work in this project is to quantify and improve the effectiveness of these types of algorithms. By studying the efficiency and providing algorithms to approximate solutions to problems which are typically considered intractable, the results of this project provide techniques which can be applied to practical problems throughout the sciences. Subdivision-based algorithms recursively and adaptively subdivide a given domain into smaller regions until, in each smaller region, the behavior of a problem-specific feature can be determined. Subdivision-based algorithms are frequently used because they are parallelizable, recursive, and adaptive. More precisely, they use weak local tests and perform more subdivisions only near difficult features. These features that make subdivision-based algorithms practical, however, also make them challenging to study. For example, local tests make global topological correctness difficult and adaptive (non-uniform) subdivisions make the number of subdivisions difficult to bound. This project addresses both of the important questions of complexity and correctness for subdivision-based algorithms in the following two ways: (1) Using continuous amortization as a uniform method to compute the complexity of subdivision-based algorithms. (2) Developing topologically certified subdivision-based algorithms for geometric applications on algebraic varieties. This project extends the technique of continuous amortization to many different types of algorithms including iterative and two-dimensional subdivisions; additionally, the project develops subdivision-based algorithms to approximate previously intractable problems such as the medial axis and intersections of surfaces.