Dept. Phone: (631)-632-8290
FAX: (631)-632-7631
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).
____________________________________________________________________________
Friday
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
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
Saturday
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
2:30-3:15 Mitchell, A Theorem on Subdivision Approximation and Its
Application to Obtaining Polynomial-Time Approximation
Schemes for Geometric Optimization Problems
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
Sunday
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
Here is an informal
_____________________________________________________________________
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.
_____________________________________________________________________
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".
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.
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.
Here are some preprints related to the talk:
_____________________________________________________________________
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.
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.
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.
TITLE : Conformal geometry applied in computer science
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.
_____________________________________________________________________
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. 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'.
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.
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.
_____________________________________________________________________
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).
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.
TITLE: Opportunities in Map-Making.
ABSTRACT in pdf
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.
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.
_____________________________________________________________________
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
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
_____________________________________________________________________
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).
Information on parking can be found at
Several versions of the campus map are available for downloading
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.
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.
Speakers may request to stay
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.
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
