Connections between analysis and computational geometry

A workshop at SoCG, June 18 2012, UNC, Chapel Hill NC

ACM Symposium on Computational Geometry

Schedule Monday June 18, 2012

The workshop will follow the SoCG invited talk by Chris Bishop on Mappings and Meshes abstract, slides, webpage

The workshop schedule is
2:20-3:05 Raanan Schul (Stony Brook), The Traveling Salesman Problem, Data Parameterization and Multi-resolution Analysis abstract, slides, webpage
3:05-3:50 Mauro Maggioni (Duke), Multiscale SVD and Geoemtric Multi-Resolution Analysis for noisy point clouds in high dimensions abstract webpage
3:50-4:10 break
4:10-4:55 Arie Israel (Courant), Interpolation by Sobolev functions abstract, slides, webpage
4:55- 5:40 Ken Stephenson (UT Knoxville) Discrete Conformality and Graph Embedding abstract, slides, webpage

5:40-6:10 Open problems and discussion

Classical analysis has always involved geometry in one form or another and in recent years various connections between the techniques of analysis and computational geometry have become more apparent. This workshop will sample a few parts of analysis where the connections are clearest and most important.

Chris Bishop will give a plenary talk at SoCG showing how the medial axis of planar domains is intimately connected to convex hulls in 3-dimensional hyperbolic geometry and how this connection plays a role in the asymptotically fastest known method for computing conformal maps from a disk to a polygon. Conversely, ideas coming from conformal mapping and hyperbolic geometry allow one to prove new theorems about triangulations and quadrilateral meshing of planar domains with optimal angle bounds. The talk discusses results mostly from Nonobtuse triangulatuion of PSLGs (preprint) and Optimal Angle Bounds for Quadrilateral meshes (DCG 2010) and to a lesser extent from Conformal Mapping in Linear Time (DCG 2010) and Quadrilateral meshes for PSLGs (preprint) . The essay A Random Walk in Analysis gives a bit more background to the talk, describing how I (C.B.) was led to work on problems in computational geometry starting from my background in classical analysis (however, the essay was written for an audience of analysts rather than computer scientists, so not much of the analysis jargon is explained).

Raanan Schul will speak on the Analyst's Traveling Salesman Problem. Given a set E (possibly infinite), how can we tell if E lies on any finite length curve? In 1991 Peter Jones answered this when E lies in the plane, giving an infinite series associated to the set that converges if and only if the set lies on a rectifiable curve, and the sum of the series giving a bound (up to a constant factor) of the minimal length curve. This series can be thought of as the analog for a set of a wavelet decomposition of a function. Jones theorem was extended to finite dimensional Euclidean spaces by Okikiolu and to infinite dimension space by Schul. There are also versions for more general metric spaces.

Mauro Maggioni will discuss how to efficiently deal with D-dimensional data that lie on a d-dimensional submanfold, with d much smaller than D, and possibly with noise. If the submanifold was a linear space then the standard thing would be to project onto a d-dimensional space using singular values, but for non-linear submanifolds new methods must be used. Maggioni will show how ideas from classical multiscale analysis can be adapted to this setting, introduce the intrinsic dimension of a data set and discuss geometric multiscale analysis for storing and manipulating data sets.

Arie Israel will speak on a topic dating back at least to the work of Hassler Whitney in the 1930's and 40's: given a function f on a set E in n-dimensional Euclidean space, can f be extended to the whole space in a nice way, e.g., as a differentiable function in some sense. If it can be extended, what are the best bounds on the function and its derivatives that we can deduce from the data? How fast can we construct an extension that is within a bounded factor of the "best" extension? Whitney's initial results lay the foundation for much of modern analysis, but these basic questions lay dormant for many years until Charles Fefferman and his students (including Israel) recently proved a number of elegant and surprising results. Israel will describe the progress so far, and how close they are to complete solutions of these problems. The talk is based on results in A bounded linear extension operator for $L^{2,p}$ (Israel) and Sobolev extension by linear operators (Fefferman, Israel and Luli) and The structure of Soboleve extension operators (Fefferman, Israel and Luli) .

Ken Stephenson literally "wrote the book" on circle packings (his text is the best reference for the area). Whereas classical conformal maps can be thought of as mapping infinitesimal circles to infinitesimal circles, circle packings give rise to a discrete analog of the theory of conformal and holomorphic functions, from which the classical case can be recovered in the limit as the circles shrink (this was conjectured by Thurston and proved by Rodin and Sullivan). In his talk, Stephenson will describe a new application of circle packings to embedding combinatoral graphs into the plane, sphere or disk in a way that is "conformal" in some sense, is easy to compute (even for large graphs) and perserves natural symmetries of the graph. See the figures below.

Some figures by Ken Stephenson (see

Some figures by Chris Bishop:

A simple polygon?
A tesselation of the disk by pentagons
Quadilateral mesh of a hyperbolic polygon
Conformal map on both sides of a snowflake
Approximation of space filling image of snowflake
Group generated by circle reflections
Example of medial axis flow
Example of medial axis flow
Example of medial axis flow
Example of medial axis flow
PSLG generated by random growth
Delaunay triangulation with edges replaced by hyperbolic goedesics
Centered conformal map to snowflake
Off center conformal map to snowflake
Centered conformal map to snowflake with boxes
Angle scaling family 1
Angle scaling family 2
Angle scaling family 3
Angle scaling family 4

Send mail to the organizer: bishop at

A related workshop on Computational and Conformal Geometry was held April 20-22, 2007 at Stony Brook University. Videos from this conference are available on the Stony Brook Math Department Video Archive.