# S-240 Math Tower, SUNY Stony Brook

## Mathematic Department Webpage SUNY Stony Brook webpage

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

____________________________________________________________________________

## Schedule of Talks (and slides)

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

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

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

## Speakers

_____________________________________________________________________

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.

_____________________________________________________________________

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

_____________________________________________________________________

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.

_____________________________________________________________________

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

_____________________________________________________________________

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

_____________________________________________________________________

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.

_____________________________________________________________________

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.

_____________________________________________________________________

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.

_____________________________________________________________________

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

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 Avalon which is nice place to take a quiet walk.