Computational and Conformal Geometry
April 20-22, 2007
S-240 Math Tower, SUNY Stony Brook

The main topic will be the connections between computational and conformal geometry. We are inviting a combination of experts in computational geometry, conformal and quasiconformal analysis and applied mathematics, and will encourage expositiory talks which emphasize open problems that might (actual or potential) interactions between these areas. or discuss fundamental ideas and open problems (particularly those that might benefit from a different point of view). The organizers are Chris Bishop (Stony Brook) and Steve Vavasis (Waterloo).

Workshop Poster

Videos of Talks

Ken Stephenson, University of Tennessee. Stephenson one of the leading experts on circle packings and discrete analytic mappings. He is the author of well known code for computing conformal maps via circle packings and of the book "Introduction to circle packing: the theory of discrete analytic functions".

Title: Experimental Conformal Geometry via Circle Packing

Abstract: The notion of circle packing, as initiated by Bill Thurston, has developed into a rather sophisticated and comprehensive theory of discrete conformal geometry --- or discrete analytic function theory, depending on your point of view. This talk will concentrate on the broad experimental perspective that comes when one has a capable computational laboratory for conformal geometry (in 2D) at your disposal. A sampling of experiments and the types of open questions they raise will be illustrated, and the software package "CirclePack" will be available for further experiments suggested by participants.

Marshall Bern, Palo Alto Reseach Center. Bern is a well known expert in computational geometry with interests in surface reconstruction, mesh generation, and many other topics.

TITLE: Three Applications of Four-Sided Gaps

ABSTRACT: Circle packing with four-sided gaps (instead of the usual three-sided gaps) provides a way to break polygons and polyhedral surfaces into well-behaved shapes. I will show how to use this tool to solve the following problems: (1) nonobtuse triangulation of polygons, (2) cutting a polygon out of paper with one straight cut, and (3) realizing any piecewise-linear metric 2-manifold (polyhedral surface) as a "flat origami".

Christopher Bishop, SUNY Stony Brook. Bishop is a complex analyst whose work deals with geometric function theory, conformal mappings, harmonic measure and related topics. His most recent work deals with the connections between conformal mappings, hyperbolic geometry and computational geometry.

TITLE: Conformal mapping in linear time

ABSTRACT: Using ideas from hyperbolic geometry and computational geometry, we show that the Riemann map of the disk to a a simply connected domain bounded by an n-gon can be computed in time O(n), with a constant that depends on the desired accuracy (given in terms of the quasiconformal constant of the approximation). More precisely, a (1+\epsilon)-QC approximation can be compute in time C n |log(\epsilon) \log \log \epsilon|. The proof uses a combination of ideas from computational geometry, numerical analysis and hyperbolic geometry. If time permits I will give an application of the method to meshing polygons.

Alan Saalfeld, Civil and Enivormental Engineering and Geodetic Science. Sallfeld is a expert on computational geometry, computer mappings and spatial analysis including applications of topology to algorithms for map making.

TITLE: Opportunities in Map-Making.


David Mumford, Brown University. Mumford's current work deals with pattern theory and the mathematical theory of vision. Among other connections to the theme of the conference, he has used conformal maps and conformal welding to help computers recognize and shapes and and written the book Indra's Pearls with Carloline Series and David Wright which deals with circle packings, Klienian groups and hyperbolic geometry (among other things). Mumford was awarded a Fields medal and McArthur fellowship and recently the received the 2006 Shaw prize. He was just awarded the 2007 Steel prize for mathematical exposition by the AMS

TITLE: Riemann maps, welding and features of 2D shapes

ABSTRACT: The traditional focus of complex analysis has been regions with Weierstrassian non-differentiable boundaries. But computer vision has highlighted the need to understand and categorize plain ordinary simple shapes. In this talk, I want to discuss some of the things this has led to: explicit bounds on the derivatives of the Riemann map at the boundary (Matt Feizsli), a fast welding algorithm and a cell decomposition of the universal Teichmuller space (aka the space of simple closed curves mod translations and scaling).

David Hamilton, University of Maryland, College Park. Hamilton is a well known expert in complex analysis and topics such as quasiconformal and conformal mappings, conformal weldings, conformal dynamics and extremal problems.

TITLE: The Riemann mapping theorem in R^3

ABSTRACT: This is a survey talk on the recent characterization of quasiballs in higher dimensions. Topics to be covered include:
(a) Construction of wild biholder reflection
(b) QC reflections are tame (introduction of method of span)
(c) T is the fixed set of a QC reflection iff T is a uniform sphere (ie its blowups only give immbedded spheres in the limit)
(d) T is a quasisphere iff uniform and quasisymmetric
(e) RMT
Although there is no actual computional algorithms the cases of (c), (d) are explicit and constructive. The general RMT is a little more esoteric, with Gromov metric etc

Toby Driscoll, University of Deleware. Driscoll is an expert on numerical conformal mappings and the author of SC-Toolbox, a MATLAB package for computing conformal mappings via the Schwartz-Christoffel map (and an author of Schwartz-Christoffel Mapping with L.N. Trefethen). In 1999 he was awarded the SIAM prize for outstanding paper.

TITLE: Spectrally accurate solutions to potential theory problems

ABSTRACT: The solution to many potential theory and conformal mapping problems consists of an analytic part and explicitly known singularities. If one chooses or generates a basis for the solution with sufficient care, spectral accuracy can be observed essentially to the extent of machine precision. In a surprising variety of circumstances, one can impose just linear conditions to define the solution, and excellent computational results can be obtained using linear least-squares techniques. This idea is demonstrated for Laplace and Poisson boundary value problems and for Green's functions and conformal maps of multiply connected regions.

Don Marshall, University of Washington. Marshall is a complex analyst and author of the conformal mapping program `zipper' based on conformal welding Loewner's equation and co-author, with John Garnett, of the authoritative text `Harmonic Measure'.

TITLE: The Geodesic Algorithm

ABSTRACT: We will discuss the geodesic variant of the zipper algorithm for conformal mapping, including a brief indication of the proof of convergence and applications to conformal welding and conformal maps of finitely connected domains.

Jack Snoeyink, University of North Carolina. Snoeyink is an expert in discrete and computational geometry and its application to molecular biology and geographic information systems.

TITLE: Bivariate B-splines from Centroid Triangulations

ABSTRACT: This is work with Yuanxin (Leo) Liu, PhD candidate at UNC Chapel Hill.
Univariate B-splines are smooth, piecewise polynomial curves that can be defined on irregularly spaced points (called knots). Because they are also expressive -- they can reproduce all polynomials up to the desired degree -- they are often used in computer-aided geometric design (CAGD) and in function approximation.
All multivariate generalizations of B-splines proposed to date, with one exception, impose restrictions on knot placement -- to grids, tensor-product constructions, or multiple knots. The exception is Neamtu's elegant work, based on higher-order Voronoi diagrams, which we will describe. Even this has limitations when one wishes to consider data-dependent surface constructions because once the knot positions are chosen, their interconnection is fixed.
We observe that the essential property to prove polynomial reproduction in Neamtu's work is a combinatorial property that is satisfied by other triangulations. A generalization of (a dual of) Lee's algorithm for higher order Voronoi diagrams, guarantees the combinatorial property (and thus polynomial reproducability) for a wider class of triangulations.
We prove that the algorithm gives quadratic and cubic splines that include some of the classical multivariate splines. For example, we can use our algorithm to reproduce the classic quadratic box spline basis, the Zwart-Powell element, which means that we can use our splines to blend patches of quadratic box splines while preserving smoothness and polynomial reproducibility.

Joe Mitchell, Stony Brook University. Mitchell is a computational geometer with interests in computer graphics, geographic information systems, virtual reality, manufacturing, approximation algorithms, pattern recognition and OCR.

TITLE: A Theorem on Subdivision Approximation and Its Application to Obtaining Polynomial-Time Approximation Schemes for Geometric Optimization Problems

ABSTRACT: We state and prove a theorem showing that any planar subdivision induced by a network of total edge length L can be approximated by an "m-guillotine" subdivision, for any fixed positive integer m, induced by a network whose edge set is a superset of the original, but has total length at most L+O(L/m). Subdivisions with the m-guillotine property are recursively defined and are ideally suited to optimization via dynamic programming. The consequence is that many geometric optimization problems have a polynomial-time approximation scheme based on solving the problem on the class of m-guillotine subdivisions, which approximate arbitrarily closely an optimal solution to the original problem. We describe some of the NP-hard geometric optimization problems for which this technique naturally leads to a PTAS, such as minimum-weight Euclidean Steiner tree, Euclidean Traveling Salesman Problem and its variants, minimum-weight convex partitions, and many others.

Xianfeng David Gu, Dept. of Computer Science, SUNY Stony Brook. Gu's work involves computing conformal structures on surfaces using the theory of holomorphic forms and Ricci flow. Applications of his work include medical imaging, geometric modeling and computer vision.

TITLE : Conformal geometry applied in computer science

Abstract in pdf

Vladimir Markovic, Warwick and Stony Brook. Markovic is an expert on quasiconformal mappings, hyperbolic geometry and Teichmuller theory. Among other honors, he was awarded an Whitehead prize by the London Math Society in 2004.

TITLE: Convex hull boundaries and extremal problems for conformal mappings

ABSTRACT: In this talk I will explain how some some extremal problems for conformal mappings (important examples are the Brennan conjecture and the Beurling's estimate on the harmonic measure of a disc of small radius) can be geometrically reformulated as questions about convex hull boundaries that live in the hyperbolic three space. I will review the known results including the very recent ones regarding the case of non-simply connected regions.

Lehel Banjai, Institut fur Mathematik, Universitat Zurich. Banjai is numerical analyst with expertise in applications of Schwartz-Chistoffel maps and fast multipole methods to conformal mappping on polygons with many sides (e.g., see this paper ). He has also worked on topics such as the omitted area problem in geometric function theory and eigenvalues of fractal domains.

TITLE: Schwarz-Christoffel mapping for difficult cases

ABSTRACT: We address the problem of conformally mapping the unit disk to two types of regions: polygons with elongations, resulting in the crowding phenomenon, and polygons with many vertices. In both cases we make use of the Schwarz-Christoffel representation of the mapping.
We will show that a simple change to the existing algorithms introduced by Trefethen (1980) makes it feasible to accurately compute conformal maps to polygons even in the presence of extreme crowding. For an efficient algorithm it is essential that a good initial guess is available. A uniformly close initial guess can be obtained from cross-ratios of certain quadrilaterals as introduced in the CRDT algorithm of Driscoll and Vavasis (1998). We present numerical experiments and compare them with the CRDT algorithm.
When the number of vertices N of the polygon becomes large the above mentioned algorithms become infeasible (costs are O(N3)). In LB,Trefethen (2003) it was shown that a combination of the fast multipole method (FMM) and Davis's method for the parameter problem can reduce the costs to O(N log N). We will briefly describe the methods involved and discuss limitations and open problems.

Mark Braverman, University of Toronto, Braverman works on computational complexity of real computation such as computation of Julia sets and conformal mappings.

TITLE: On the computational complexity of Riemann mapping

ABSTRACT: We study the computational complexity of computing the Riemann mapping of a simply-connected planar domain. The goal is to use Complexity Theory to pinpoint the complexity of the problem.
In particular, we obtain a space-efficient algorithm for computing the Riemann mapping. While space efficiency is not always directly tied to time-wise performance, it is closely related to parallelizability. We also give a (weaker) lower bound on the complexity of the problem.
Joint work with Ilia Binder and Michael Yampolsky.