×

Combinatorial optimization in geometry. (English) Zbl 1028.52006

Summary: We extend and unify the author’s results in [Ann. Math. 143, 51-70 (1996; Zbl 0874.52006), here cited by [*] and ibid. 139, 553-580 (1994; Zbl 0823.52009), here cited by [**]]. As a consequence, the results of [*] are generalized from the framework of ideal polyhedra in \(\mathbf H^3\) to that of singular Euclidean structures on surfaces, possibly with an infinite number of singularities (by contrast, the results of [*] can be viewed as applying to the case of non-singular structures on the disk, with a finite number of distinguished points). This leads to a fairly complete understanding of the moduli space of such Euclidean structures and thus, by the results of R. C. Penner, Commun. Math. Phys. 113, 299-339 (1987; Zbl 0642.32012); D. B. A. Epstein and R. C. Penner, J. Differ. Geom. 27, 67-80 (1988; Zbl 0611.53036); M. Näätänen and R. C. Penner, Bull. Lond. Math. Soc. 23, 568-574 (1991; Zbl 0743.30038) and the author [*] and Lect. Notes Pure Appl. Math. 156, 275-291 (1994; Zbl 0823.52008), and others, further insights into the geometry and topology of the Riemann moduli space.
The basic objects studied are the canonical Delaunay triangulations associated to the aforementioned Euclidean structures.
The basic tools, in addition to the author’s results in [**] and combinatorial geometry, are methods of combinatorial optimization – linear programming and network flow analysis; hence the results mentioned above are not only effective but also efficient. Some applications of these methods to three-dimensional topology are also given (to prove a result of Casson’s).

MSC:

52B55 Computational aspects related to convexity
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahuja, K.; Orlin, J. B.; Tarjan, R. E., Improved time bounds for the maximum flow problem, SIAM J. Comput., 18, 939-954 (1989) · Zbl 0675.90029
[2] Andreev, E. M., On convex polyhedra of finite volume in Lobachevskii space, Math. USSR-Sb., 12, 255-259 (1970) · Zbl 0252.52005
[3] A. Casson, private communication; A. Casson, private communication
[4] M.B. Dillencourt, private communication; M.B. Dillencourt, private communication
[5] Dillencourt, M., Polyhedra of small order and their Hamiltonian properties, J. Combin. Theory Ser. B, 66, 1, 87-122 (1996) · Zbl 0847.52008
[6] Bowditch, B. H.; Epstein, D. B.A., Natural triangulations associated to a surface, Topology, 27, 1, 91-117 (1988) · Zbl 0649.32017
[7] Bowditch, B. H., Singular Euclidean structures on surfaces, J. London Math. Soc., 44, 3, 553-565 (1991) · Zbl 0748.57003
[8] Epstein, D. B.A.; Penner, R. C., Euclidean decompositions of non-compact hyperbolic manifolds, J. Differential Geom., 27, 67-80 (1988) · Zbl 0611.53036
[9] Haken, W., Theorie der Normalflächen, (German), Acta Math., 105, 245-375 (1961) · Zbl 0100.19402
[10] Hemion, G., The Classification of Knots and 3-Dimensional Spaces (1992), Oxford University Press: Oxford University Press New York · Zbl 0771.57001
[11] Harer, J., The virtual cohomological dimension of the mapping class group of an orientable surface, Invent. Math., 84, 1, 157-176 (1986) · Zbl 0592.57009
[12] Hodgson, C. D.; Rivin, I.; Smith, W. D., A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere, Bull. Amer. Math. Soc., 27, 3 (1992) · Zbl 0759.52010
[13] Jaco, W., Lectures on Three-Manifold Topology. Lectures on Three-Manifold Topology, CBMS Regional Conf. Ser. in Math., 43 (1980), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0433.57001
[14] Näätänen, M.; Penner, R. C., The convex hull construction for compact surfaces and the Dirichlet polygon, Bull. London Math. Soc., 6, 568-574 (1991) · Zbl 0743.30038
[15] Neumann, W. D.; Zagier, D., Volumes of hyperbolic 3-manifolds, Topology, 24, 3, 307-332 (1985) · Zbl 0589.57015
[16] Penner, R. C., The decorated Teichmüller space of punctured surfaces, Comm. Math. Phys., 113, 2, 299-339 (1987) · Zbl 0642.32012
[17] Rivin, I.; Hodgson, C. D., A characterization of compact convex polyhedra in hyperbolic 3-space, Invent. Math., 111, 1 (1993) · Zbl 0798.52009
[18] Rivin, I., On geometry of convex ideal polyhedra in hyperbolic 3-space, Topology, 32, 1 (1993) · Zbl 0784.52014
[19] Rivin, I., Intrinsic geometry of convex ideal polyhedra in hyperbolic 3-space, analysis, algebra, and computers in mathematical research, (Proceedings of the Nordic Congress of Mathematicians, Luleaa, 1992. Proceedings of the Nordic Congress of Mathematicians, Luleaa, 1992, Lecture Notes in Pure and Appl. Math., 156 (1994), Dekker)
[20] Rivin, I., Euclidean structures on simplicial surfaces and hyperbolic volume, Ann. of Math., 139, 3 (1994) · Zbl 0823.52009
[21] Rivin, I., A characterization of ideal polyhedra in hyperbolic 3-space, Ann. of Math., 143, 1 (1996) · Zbl 0874.52006
[22] I. Rivin, Personal communication; I. Rivin, Personal communication
[23] Steiner, J., Systematische Entwicklung der Abhängigkeit Geometrischer Gestalten von Einander (1832), Reimer: Reimer Berlin, appeared in J. Steiner’s Collected Works, 1881
[24] Steinitz, E., Über isoperimetrische Probleme bei konvexen Polyedern, J. Reine Angew. Math., 159, 133-143 (1928) · JFM 54.0527.04
[25] Troyanov, M., Les surfaces euclidiennes à singularites coniques, Enseign. Math., 32, 1-2, 79-94 (1986) · Zbl 0611.53035
[26] W.P. Thurston, Geometry and topology of 3-manifolds, Unpublished Princeton Lecture Notes for 1978, distributed by MSRI, Berkeley; W.P. Thurston, Geometry and topology of 3-manifolds, Unpublished Princeton Lecture Notes for 1978, distributed by MSRI, Berkeley
[27] van Lint, J.; Wilson, R. M., A Course in Combinatorics (1992), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0769.05001
[28] Veech, W., Delaunay partitions, Topology, 36, 1, 1-28 (1997) · Zbl 0954.32009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.