Surveys on discrete and computational geometry: twenty years later: AMS-IMS-SIAM Joint Summer Research Conference Discrete and Computational Geometry - Twenty Years Later, June 18-22, 2006, Snow Bird, Utah / ed. by J.E.Goodman, J.Pach, R.Pollack. - Providence: American Mathematical Society, 2008. - viii, 556 p.: ill. - (Contemporary mathematics; 453). - Incl. bibl. ref. - ISBN 978-08218-4239-3; ISSN 0271-4132  Место хранения:   013 | Институт математики СО РАН | Новосибирск | Библиотека

Оглавление / Contents

Preface Jacob E. Goodman, János Pach, and Richard Pollack .......... vii Musings on discrete geometry and "20 years of Discrete and Computational Geometry" Branko Grünbaum .............................................. 1 State of the union (of geometric objects) Pankaj K. Agarwal, János Pach, and Micha Sharir .............. 9 Metric graph theory and geometry: a survey Hans-Jürgen Bandelt and Victor Chepoi ....................... 49 Extremal problems for convex lattice poly topes: a survey Imre Bárány ................................................. 87 On simple arrangements of lines and pseudo-lines in 2 and 2 with the maximum number of triangles Nicolas Bartholdi, Jérémy Blanc, and Sébastien Loisel ...... 105 The computational complexity of convex bodies Alexander Barvinok and Ellen Veomett ....................... 117 Algorithmic semi-algebraic geometry and topology-recent progress and open problems Saugata Basu ............................................... 139 Expansive motions Robert Connelly ............................................ 213 All polygons flip finitely ... right? Erik D. Demaine, Blaise Gassend, Joseph O'Rourke, and Godfried T. Toussaint ...................................... 231 Persistent homology—a survey Herbert Edelsbrunner and John Harer ........................ 257 Recent progress on line transversals to families of translated ovals Andreas Holmsen ............................................ 283 An improved, simple construction of many halving edges Gabriel Nivasch ............................................ 299 Unfolding orthogonal polyhedra Joseph O'Rourke ............................................ 307 The discharging method in combinatorial geometry and the Pach-Sharir conjecture Radoš Radoičić and Géza Tóth ............................... 319 Pseudo-triangulations—a survey Günter Rote, Francisco Santos, and Ileana Streinu .......... 343 Line problems in nonlinear computational geometry Frank Sottile and Thorsten Theobald ........................ 411 On empty hexagons Pavel Valtr ................................................ 433 k-sets and k-facets Uli Wagner ................................................. 443 An Erdös-Szekeres type problem for interior points Xianglin Wei and Ren Ding .................................. 515 The kissing number, blocking number and covering number of a convex body Chuanming Zong ............................................. 529 Open problems Edited by János Pach ....................................... 549