In my talk I will attempt to draw some connections between complex analysis and computational geometry, particularly between conformal mappings, hyperbolic geometry, the medial axis and optimal meshing. The Riemann mapping theorem says that there is a conformal (angle preserving) map of the unit disk, D, to the interior Ω of any simple n-gon. How much work is needed to compute this map? Theorem 1: [1] We can compute the conformal map f : D → Ω to within error e in time O(n · log 1/∈ log log 1/∈). The proof uses an iteration that converges quadratically to f, but it needs a good initial guess that is close to the correct answer. The medial axis allows us to quickly construct a map Ω → D that is close to Riemann's map with precise estimates. This gives our starting point, and the time estimates in the theorem depend on time needed to compute the medial axis (linear by work of Chin, Snoeyink and Wang). Conversely, the proof of Theorem 1 uses ideas from analysis that may be of interest in CG. For example, the dome of a planar domain Ω is the surface in R_+~3 given by the upper envelope of all hemispheres whose base on R~2 is a medial axis disk of Ω. Domes arise in the study of 3-manifolds, and a fundamental result of Dennis Sullivan about convex sets in hyperbolic 3-space lies at the heart of Theorem 1. The proof of Theorem 1 also introduces the thick-thin decomposition of a polygon, inspired by the thick-thin decomposition of a hyperbolic manifold. The thin parts correspond to "long, narrow" pieces of the polygon (but not in the obvious way; the precise definition uses a conformal invariant called extremal length). This decomposition plays in important role in proving: Theorem 2: [2] Any simple n-gon has a O(n) quadiilateml mesh with all angles < 120° and all new angles > 60°. The sharp upper bound is due to Bern and Eppstein; the lower bound is the novel part here. The result is also true for PSLGs with at most n edges and vertices, although simple examples show the O(n) must be replaced by O(n~2): Theorem 3: [4] Every PSLG has an O(n~2) quadrilateral mesh with all angles < 120° and all new angles > 60°. Only O(n/∈) angles satisfy |0 - 90° | > ∈, for any ∈ > 0. Adding diagonals to the quadrilaterals gives a triangulation with all angles < 120°, improving results of S. Mitchell (157.5°) and Tan (132°). Applying thick-thin decompositions directly to triangulations gives an even better result: for any ∈ > 0. a PSLG has a O(n~2) triangulation with angles < 90° + ∈ (but the constant blows up as c ↘ 0). For e — 0, a more intricate construction shows: Theorem 4: [3] Every PSLG has a O{n~(2.5)) nonobtuse triangulation. No polynomial bound was previously known, and I strongly suspect n~(2.5) can be improved to n~2 (known sharp). The triangles may be taken to be either all acute or all right. Some consequences of Theorem 4 and its proof include 1. Every PSLG has a O(n~(2.5)) conforming Delaunay triangulation (improves O(n~3) by Edelsbrunner and Tan). 2. Any triangulation of an n-gon has a O(n~2) nonobtuse refinement (improves O(n~4) by Bern and Eppstein). Most of the algorithms I will describe seem too complex to implement (at least for me), and are strongly 2-dimensional, but I hope the audience will have some suggestions for getting around these problems.
展开▼
