Principal Investigator: Christopher Bishop
The principal investigator will study the geometric properties of conformal and quasiconformal maps, with an emphasis on the connections with other areas such as numerical analysis, computational geometry, complex dynamics and geometric measure theory. He will continue his work on fast conformal mapping algorithms, including the class of Schwarz-Christoffel iterations. These include Davis' method and the CRDT algorithm of Driscoll and Vavasis as special cases, and other methods involving the medial axis and quasiconformal mappings. One of the basic themes is to start with certain quasiconformal maps that approximate the desired conformal map, but are easier to compute and have better properties. These maps have natural connections to several well known problems such as Brennan's conjecture, and the PI will investigate these connections. The PI will also continue his work on various related problems involving optimal meshing algorithms, diffusion limited aggregation, the geometry of Brownian motion, the quasiconformal Jacobian problem and conformal welding.
A fundamental problem of mathematics and engineering is to quickly and accurately solve various differential equations related to fluid flow, heat conduction and wave propagation on complex regions. For 2-dimensional surfaces, a standard method is to use a conformal mapping (i.e., angle preserving on small scales) to replace the region with a simpler one, such as a disk or rectangle. This approach has been studied for over 150 years, but not until the 1980's did computers made conformal mapping practical for highly complex regions. The PI will investigate how to improve existing methods and develop new ones that are faster and more reliable. He will also investigate the theoretical behavior of conformal maps on extremely complex domains such as fractals and the connections between conformal maps and probability theory. The PI has already applied the insights gained from these problems to meshing. This is the process of dividing a complex region into simple pieces such as triangles. Meshing is a basic part of most numerical methods and the usefulness of a mesh in applications depends on the number of pieces (fewer is better) and their shapes (better to avoid small and large angles). It is difficult to construct a mesh which is good in both respects, but PI has used non-Euclidean geometry to construct 2-dimensional quadrilateral meshes with optimal size and shapes for simple polygons and is working to extend this to more general domains. Greater generality is needed in various problems involving crack formation, interfaces between materials and computer learning. Efficient meshing also has numerous applications in high-performance computing such as modeling surfaces for engineering and computer graphics. This award is jointly funded by the programs in Analysis and Geometric Analysis.
The project used ideas from complex analysis and hyperbolic geometry to solve some long standing open problems about how to divide a planar polygonal domain into simple shapes (triangles and quadrilaterals) with good control of the angles. In earlier work the PI had used results from discrete geometry to give a fast algorithm for computing conformal (angle preserving) maps between a disk and a polygon. Such maps have been the subject of investigation for over 150 years due to their central place in mathematical analysis and a large number of connections to areas such as fluid flow, probability theory, electrostatics and shape recognition. In the current work, the direction is reversed and ideas from conformal analysis are used to resolve questions about discrete mathematics, namely, optimal meshing. A polygonal domain in the plane is one that is bounded by a finite number of line segments (but the boundary need not be connected; it may have holes or cracks that run through it). A simple polygon is one where the boundary is a single connected polygonal curve. For various applications, such as numerically solving a partial differential equation, it is desirable to lay a grid over domain. The elements might be triangles (giving a triangulation) or quadrilaterals (giving a quad mesh) and we wish these pieces to exactly fill up the domain without overlapping each other or the boundary. For computational reasons, it is also highly desirable to use angles that are not too large (they should bounded strictly below 180 degrees) and for efficiency we wish to use as few pieces as possible. It turns our that the best upper angle bound that is practical is 90 degrees and it has been known for about 20 years that domains with simple polygonal boundaries can be efficiently triangulated using angles with maximum size 90 degrees. In the more general case of polygons with holes or cracks (which can be used to model the interface between different materials) it has been known since the 1990's how to efficiently triangulate with angles less than 132 degrees. The current work improved this to the optimal 90 degrees, giving the first polynomial time algorithm for doing non-obtuse triangulation in this generality. Several other open problems involving meshes and triangulations were also solved in this project, e.g., it was shown how to create a quad-mesh for a general polygonal domain with N sides that uses at most about N^2 pieces and so that all angles are less than 120 degrees and all new angles are bigger than 60 degrees (smaller angles in the domain boundary must remain but are not subdivided). Both the angle estimates and the size of triangulations are sharp, i.e., there are examples that show that these estimates cannot be improved in general. At present the algorithms described above are mostly theoretical in nature, giving worst case limits that practical implementations will try to meet or beat. However, there are a variety of applications (e.g., numerical solution of differential equations) where high quality meshes improve the accuracy and speed of the calculation, and the meshing results above, even if only partially implemented, could improve on current methods used in practice. In addition to the meshing problems described above, the PI also obtained new results in the theory of quasiconformal maps (maps that distort angles by a limited amount). He gave new examples of quasiconformal maps related to fractal behavior and used the theory of quasiconformal maps to build new examples of holomorphic maps, resolving by counter-examples some open long standing open problems in holomorphic dynamics.
