Computational and Conformal Geometry

April 20-22, 2007 (Friday-Sunday)

S-240 Math Tower, SUNY Stony Brook

Mathematic Department Webpage
SUNY Stony Brook webpage

Dept. Phone: (631)-632-8290
FAX: (631)-632-7631

send email to conference organizers, ccg2007 at

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


Schedule of Talks (and slides)

10:00 welcome
10:15-11:00 Stephenson, Experimental Conformal Geometry via Circle Packing pdf slides
11:15-12:00 Bern, Three Applications of Four-Sided Gaps Power point slides
12:00-1:30 lunch
1:30-2:15 Bishop, Conformal mapping in linear time pdf slides
2:30-3:15 Saalfeld, Opportunities in Map-Making Power point slides
3:15-3:45 tea
3:45-4:30 Mumford, Riemann maps, welding and features of 2D shapes Power point slides
4:45-5:45 problem session
6:00-8:00 dinner

9:15-10:00 Hamilton, The Riemann mapping theorem in R^3 pdf slides
10:15-11:00 Driscoll, Spectrally accurate solutions to potential theory problems pdf slides
11:15-12:00 Marshall, The Geodesic Algorithm pdf slides
12:00-1:30 lunch
1:30-2:15 Snoeyink, Bivariate B-splines from Centroid Triangulations Power point slides
2:30-3:15 Mitchell, A Theorem on Subdivision Approximation and Its Application to Obtaining Polynomial-Time Approximation Schemes for Geometric Optimization Problems Power point slides
3:15-3:45 tea
3:45-4:30 Gu, Conformal geometry applied in computer science Power point slides - Applications and pdf slides - Theory
4:45-5:45 problem session

9:15-10:00 Markovic, Convex hull boundaries and extremal problems for conformal mappings Power point slides
10:15-10:00 Banjai, Schwarz-Christoffel mapping for difficult cases Power point slides
11:15-12:00 Braverman, On the computational complexity of Riemann mapping


If you are interested in coming, please register by sending an email to register to attend We appreciate this so we can get an accurate headcount.

Here is an informal announcement in pdf suitable for posting on your door or bulletin board.



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. Banjai's homepage

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.

pdf slides for Banjai's talk


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. Berns's homepage

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

Power point slides for Berns's lecture


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. Bishop's homepage

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.

pdf file for lecture slides

Here are some preprints related to the talk:
Conformal mapping in linear time
Quadrilateral meshes with optimal angle bounds
Bounds for the CRDT algorithm
A fast QC mapping theorem for polygons
A central set of dimension 2
Quasiconformal Lipschitz maps, Sullivan's convex hull theorem and Brennan's conjecture
An explicit bound for Sullivan's convex hull theorem
Conformal welding and Koebe's theorem
An A_1 weight not comparable to any QC Jacobian


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

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.
Work joint with Ilia Binder and Michael Yampolsky.


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. Driscoll's homepage

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.
pdf slides


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. Gu's homepage

TITLE : Conformal geometry applied in computer science abstract in pdf

Power point slides for Gu's lecture - Applications-
Power point slides for Gu's lecture - Theory-


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.

pdf slides


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. Markovic's Warwick homepage

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. Power point slides for Markovc's talk


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'. Marshall's homepage

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.

pdf slides for Marshall's talk


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. Mitchell's homepage

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.

Power point slides for Mitchell's talk


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 Steep prize citation {/l>, Mumford's homepage, Wikipedia entry for David Mumford

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

Power point slides for Mumford's talk


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. Saalfeld's homepage

TITLE: Opportunities in Map-Making.

Power point slides


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. Snoeyink's homepage

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.
Power point slides


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''. For more information about the book and for many beautiful pictures involving circle packings, see Stephenson's homepage, and Figures from Stephenson's book

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.

pdf slides for Stephenson's lecture


Links to local and travel information

The talks will be held in S-240. This is a medium sized lecture room in the basment (S-level) of the math building. Half the room is set up for the lecture area, and the other half has couches, tables and blackboards for conversation and smaller group discussions.

If you are driving, parking is limited on campus, but there is a parking garage you can use for all day parking, or meters for shorter term ($1 per hour in quaters, some with 2 hour limit).
Stony Brook Campus Map --- parking garage highlighted

Information on parking can be found at Stony Brook Parking including fees for the parking garage and a list of visitor's parking lots.

Several versions of the campus map are available for downloading
Stony Brook Campus Map --- Back and White PDF version for printing
Stony Brook Campus Map --- Fancier color version
Stony Brook Campus Map --- online `zoom-able' version

Directions to visit Stony Brook Campus --- plane, car, ferry, trains

Stony Brook Campus with hand annotations circling trains station, math building and parking lot, campus parking garage and Jasmine restaurant.

near the bottom center (and is marked by name).

For all hotels, the blocked rooms are held until 30 days prior to the first night. Confirmed out-of-town speakers have a reservation at Danfords. A speaker who would prefer to stay elsewhere should contact the organizers. Others wishing to come should make their own reservations, but may request the university rate. 5 extra rooms have been blocked at Danfords, 20 at the Holdiay Inn.

The organizers will make resevations for the speakers at Danford's Inn in Port Jefferson. This is on the waterfront in Port Jefferson, next to the ferry to Bridgeport, CT and is within walking distance of many restaurants and shops. The Danfords webpage . The phone number for Danfords is 1-800332-6367 or 631-928-5200. It is about 4 miles from the campus, but the Suffolk County bus runs from there to the student center on campus (Mon-Sat). We will also try to arrange rides as needed. For non-speakers the university rate is $163.60. There is a restaurant, but breakfast is not included with the room.

Here are websites for some bed-and-breakfasts in Port Jefferson: Golden pineapple.
Holly Berry .
White House .

An earlier version of this webpage indicated that speakers would stay at the Three Village Inn, but due to a mix-up with the reservations, we had to switch to Danfords. Sorry for any inconvenience this may cause. The Three Village Inn. A few rooms may be available there; if you prefer this (it is closer to campus; about 1.5 miles but walkable) let me know and I will try to get you in.

Speakers may request to stay Holiday Inn Express (about two miles south of SUNYSB on Rt 347, a little east of intersection of 347 and Nicholls Rd). For speakers we will direct bill. Others can request the University rate which is $129 and the code is GEO. Please mention "Geometry Conference" to get the unviersity rate. It includes breakfast and a complimentary shuttle to campus.

Islip Airport

Long Island Railroad schedule from Penn Station NYC to Stony Brook

You can take the LIRR from Penn station in New York on the Port Jefferson line. Port Jeffereson is the last stop and the train station is abou a mile from the hotel (just follow the Rt 112 downhill towards the water until you reach the ferry and Danfords is on the right); taxis should be available at the station. The Stony Brook campus the next to last stop on the Port Jefferson line. If you are coming early on Thursday (or even Friday morning) you can get off there; Math-Physics is the first large (6 story) building you can see from the station, on the other side of the physical plant. It is about a 5-10 minute walk from the train station to the math department.

Bridgeport - Port Jefferson Ferry

Stony Brook campus map

About 2 miles from campus is Stony Brook Village. There are a variety of small shops and restaurants and an 140 acre park and nature preserve Avalon which is nice place to take a quiet walk.