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).
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
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
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.