The present paper deals about the use of normal surface theory in 3-dimensional computational topology: see Kneser’s foundational paper ([Jahresbericht D. M. V. 38, 248-260 (1929; JFM 55.0311.03)]), together with the developments by Haken and Jago-Oertel ([Acta Math. 105, 245-375 (1961; Zbl 0100.19402)], [Math. Z. 80, 89-120 (1962; Zbl 0106.16605)], [Topology 23, 195-209 (1984; Zbl 0545.57003)]). In particular, the author faces the crucial problem of enumerating normal surfaces in a given (triangulated) 3-manifold, via the underlying procedure of enumerating admissible vertices of a high-dimensional polytope (admissibility being a powerful but non-linear and non-convex constraint). The main results of the present paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices (see [J. ACM 46, No. 2, 185-211 (1999; Zbl 1065.68667)], [B.A.Burton, The complexity of the normal surface solution space, in: SCG’10: Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, ACM Press, 2010, pp.201-209] and [Math. Comput. 79, No. 269, 453-484 (2010; Zbl pre05776230)]). To achieve these results, the author examines the layout of admissible points within polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system. These points are proved to correspond to well-behaved substructures of the face lattice, and the properties of the corresponding “admissible faces” are studied. Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above.

REVIEW OF: "Burton Benjamin A., Maximal admissible faces and asymptotic bounds for the normal surface solution space, J. Comb. Theory, Ser. A 118, No. 4, 1410-1435 (2011)". [DE058788316] / Casali, Maria Rita. - In: EXCERPTS FROM ZENTRALBLATT MATH. - ISSN 2190-3484. - ELETTRONICO. - Zbl pre05878831:(2012), pp. .-...

REVIEW OF: "Burton Benjamin A., Maximal admissible faces and asymptotic bounds for the normal surface solution space, J. Comb. Theory, Ser. A 118, No. 4, 1410-1435 (2011)". [DE058788316]

CASALI, Maria Rita
2012

Abstract

The present paper deals about the use of normal surface theory in 3-dimensional computational topology: see Kneser’s foundational paper ([Jahresbericht D. M. V. 38, 248-260 (1929; JFM 55.0311.03)]), together with the developments by Haken and Jago-Oertel ([Acta Math. 105, 245-375 (1961; Zbl 0100.19402)], [Math. Z. 80, 89-120 (1962; Zbl 0106.16605)], [Topology 23, 195-209 (1984; Zbl 0545.57003)]). In particular, the author faces the crucial problem of enumerating normal surfaces in a given (triangulated) 3-manifold, via the underlying procedure of enumerating admissible vertices of a high-dimensional polytope (admissibility being a powerful but non-linear and non-convex constraint). The main results of the present paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices (see [J. ACM 46, No. 2, 185-211 (1999; Zbl 1065.68667)], [B.A.Burton, The complexity of the normal surface solution space, in: SCG’10: Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, ACM Press, 2010, pp.201-209] and [Math. Comput. 79, No. 269, 453-484 (2010; Zbl pre05776230)]). To achieve these results, the author examines the layout of admissible points within polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system. These points are proved to correspond to well-behaved substructures of the face lattice, and the properties of the corresponding “admissible faces” are studied. Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above.
2012
.
..
Casali, Maria Rita
REVIEW OF: "Burton Benjamin A., Maximal admissible faces and asymptotic bounds for the normal surface solution space, J. Comb. Theory, Ser. A 118, No. 4, 1410-1435 (2011)". [DE058788316] / Casali, Maria Rita. - In: EXCERPTS FROM ZENTRALBLATT MATH. - ISSN 2190-3484. - ELETTRONICO. - Zbl pre05878831:(2012), pp. .-...
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1061899
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact