High-quality parametrization and quadrangualation

Day - Time: 10 September 2012, h.14:00
Place: Area della Ricerca CNR di Pisa - Room: C-29
  • Denis Zorin (New York University)

Nico Pietroni


In this talk I will review recent progress in global parametrization and quadrangulation algorithms, focusing on our recent work emphasizing optimization of parametrization quality. We have pursued several directions, the two main ones being the choice of topological structure of the global parametrization to minimize distortion, and the second one is controlling conformal and more generally isometric distortion locally. Global parametrization of surfaces requires singularities (cones) to keep distortion minimal. In general, the problem of choosing cone locations and associated cone angles minimizing distortion is a special case of a general nonlinear mixed-integer problem which does not admit efficient computational solutions. We have designed an approximate method based on the idea of evolving the metric of the surface, starting with the original metric so that a growing fraction of the area of the surface is constrained to have zero Gaussian curvature; the curvature becomes gradually concentrated at a small set of vertices which become cones. We demonstrate that the resulting parametrizations have significantly lower metric distortion compared to previously proposed methods. The second direction is aiming to design efficient algorithms for controlling local distortion, specifically, deviation of the map from conformality. Our approach is based on the theory of extremal quasiconformal maps, i.e. maps, that for given set of constraints (e.g. fixed boundaries or points in the interior) minimize the worst-case distortion. Remarkably such maps are unique in many relevant cases, and have a number of properties that allows us to compute them efficiently.