Combinatorial optimization in geometry

DOI10.1016/S0196-8858(03)00093-9zbMath1028.52006arXivmath/9907032WikidataQ56765099 ScholiaQ56765099MaRDI QIDQ1408292

Igor Rivin

Publication date: 15 September 2003

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9907032

zbMATH Keywords

linear programmingmoduli spacenetwork flowDelaunay triangulationshyperbolic structuresEuclidean structures

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Combinatorial optimization (90C27)

Related Items

Scribability problems for polytopes ⋮ Geometric angle structures on triangulated surfaces ⋮ Andreev's theorem on hyperbolic polyhedra ⋮ Closed-loop live marked graphs under generalized mutual exclusion constraint enforcement ⋮ Book Review: Ricci flow for shape analysis and surface registration: theories, algorithms and applications ⋮ A note on circle patterns on surfaces ⋮ Characterizations of circle patterns and finite convex polyhedra in hyperbolic 3-space ⋮ Min-cost multiflows in node-capacitated undirected networks ⋮ Combinatorial Ricci flows and the hyperbolization of a class of compact 3-manifolds ⋮ Hyper-ideal circle patterns with cone singularities ⋮ Universality theorems for inscribed polytopes and Delaunay triangulations ⋮ Explicit angle structures for veering triangulations ⋮ Angle structures and normal surfaces ⋮ On circle patterns and spherical conical metrics ⋮ Characterizing the Delaunay decompositions of compact hyperbolic surfaces ⋮ Circle patterns on singular surfaces ⋮ Spectral Experiments+ ⋮ Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree ⋮ Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree ⋮ On an elementary proof of Rivin's characterization of convex ideal hyperbolic polyhedra by their dihedral angles ⋮ Many projectively unique polytopes ⋮ Combinatorial Calabi flow on 3-manifolds with toroidal boundary ⋮ Combinatorial Ricci flows for ideal circle patterns ⋮ A combinatorial curvature flow for compact 3-manifolds with boundary ⋮ QUANTUM TEICHMÜLLER THEORY AND REPRESENTATIONS OF THE PURE BRAID GROUP ⋮ The circle pattern uniformization problem ⋮ A TQFT from quantum Teichmüller theory ⋮ On describing the routing capacity regions of networks ⋮ Discrete conformal maps and ideal hyperbolic polyhedra ⋮ Blowup algebras of square-free monomial ideals and some links to combinatorial optimization problems ⋮ Introducing Regina, The 3-Manifold Topology Software ⋮ Gauss images of hyperbolic cusps with convex polyhedral boundary ⋮ Six Topics on Inscribable Polytopes ⋮ Canonical triangulations of Dehn fillings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Volumes of hyperbolic three-manifolds
• The virtual cohomological dimension of the mapping class group of an orientable surface
• Les surfaces euclidiennes à singularités coniques. (Euclidean surfaces with cone singularities)
• Euclidean decompositions of noncompact hyperbolic manifolds
• The decorated Teichmüller space of punctured surfaces
• Natural triangulations associated to a surface
• Corrigendum: A characterization of compact convex polyhedra in hyperbolic 3-space
• Euclidean structures on simplicial surfaces and hyperbolic volume
• Polyhedra of small order and their Hamiltonian properties
• A characterization of ideal polyhedra in hyperbolic 3-space
• Delaunay partitions
• On geometry of convex ideal polyhedra in hyperbolic 3-space
• Improved Time Bounds for the Maximum Flow Problem
• The Convex Hull Construction for Compact Surfaces and the Dirichlet Polygon
• Singular Euclidean Structures on Surfaces
• A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
• ON CONVEX POLYHEDRA OF FINITE VOLUME IN LOBAČEVSKIĬ SPACE