Computing the Continuous Discretely

Last updated
First edition (2007) Computing the Continuous Discretely.jpg
First edition (2007)

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra is an undergraduate-level textbook in geometry, on the interplay between the volume of convex polytopes and the number of lattice points they contain. It was written by Matthias Beck and Sinai Robins, and published in 2007 by Springer-Verlag in their Undergraduate Texts in Mathematics series (Vol. 154). A second edition was published in 2015, and a German translation of the first edition by Kord Eickmeyer, Das Kontinuum diskret berechnen, was published by Springer in 2008. [1]

Contents

Topics

The book begins with a motivating problem, the coin problem of determining which amounts of money can be represented (and what is the largest non-representable amount of money) for a given system of coin values. Other topics touched on include face lattices of polytopes and the Dehn–Sommerville equations relating numbers of faces; Pick's theorem and the Ehrhart polynomials, both of which relate lattice counting to volume; generating functions, Fourier transforms, and Dedekind sums, different ways of encoding sequences of numbers into mathematical objects; Green's theorem and its discretization; Bernoulli polynomials; the Euler–Maclaurin formula for the difference between a sum and the corresponding integral; special polytopes including zonotopes, the Birkhoff polytope, and permutohedra; and the enumeration of magic squares. [2] [3] [4] [5] In this way, the topics of the book connect together geometry, number theory, and combinatorics. [2] [4]

Audience and reception

This book is written at an undergraduate level, and provides many exercises, making it suitable as an undergraduate textbook. [3] [4] [5] Little mathematical background is assumed, except for some complex analysis towards the end of the book. [4] The book also includes open problems, of more interest to researchers in these topics. [3] [5] As reviewer Darren Glass writes, "Even people who are familiar with the material would almost certainly learn something from the clear and engaging exposition that these two authors use." [4]

Reviewer Margaret Bayer calls the book "coherent and tightly developed ... accessible and engaging", [2] and reviewer Oleg Karpenkov calls it "outstanding". [5]

See also

Related Research Articles

<span class="mw-page-title-main">Combinatorics</span> Branch of discrete mathematics

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

<span class="mw-page-title-main">Geometry of numbers</span>

Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in and the study of these lattices provides fundamental information on algebraic numbers. The geometry of numbers was initiated by Hermann Minkowski (1910).

In mathematics, an integral polytope has an associated Ehrhart polynomial that encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a higher-dimensional generalization of Pick's theorem in the Euclidean plane.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Branko Grünbaum</span> Yugoslav American mathematician

Branko Grünbaum was a Croatian-born mathematician of Jewish descent and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel.

<i>Regular Polytopes</i> (book) Geometry book

Regular Polytopes is a geometry book on regular polytopes written by Harold Scott MacDonald Coxeter. It was originally published by Methuen in 1947 and by Pitman Publishing in 1948, with a second edition published by Macmillan in 1963 and a third edition by Dover Publications in 1973. The Basic Library List Committee of the Mathematical Association of America has recommended that it be included in undergraduate mathematics libraries.

Using the Borsuk–Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry is a graduate-level mathematics textbook in topological combinatorics. It describes the use of results in topology, and in particular the Borsuk–Ulam theorem, to prove theorems in combinatorics and discrete geometry. It was written by Czech mathematician Jiří Matoušek, and published in 2003 by Springer-Verlag in their Universitext series (ISBN 978-3-540-00362-5).

<span class="mw-page-title-main">Treks into Intuitive Geometry</span>

Treks into Intuitive Geometry: The World of Polygons and Polyhedra is a book on geometry, written as a discussion between a teacher and a student in the style of a Socratic dialogue. It was written by Japanese mathematician Jin Akiyama and science writer Kiyoko Matsunaga, and published by Springer-Verlag in 2015 (ISBN 978-4-431-55841-5).

<i>A Guide to the Classification Theorem for Compact Surfaces</i> Textbook in topology

A Guide to the Classification Theorem for Compact Surfaces is a textbook in topology, on the classification of two-dimensional surfaces. It was written by Jean Gallier and Dianna Xu, and published in 2013 by Springer-Verlag as volume 9 of their Geometry and Computing series. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries.

Art Gallery Theorems and Algorithms is a mathematical monograph on topics related to the art gallery problem, on finding positions for guards within a polygonal museum floorplan so that all points of the museum are visible to at least one guard, and on related problems in computational geometry concerning polygons. It was written by Joseph O'Rourke, and published in 1987 in the International Series of Monographs on Computer Science of the Oxford University Press. Only 1000 copies were produced before the book went out of print, so to keep this material accessible O'Rourke has made a pdf version of the book available online.

Polyhedra is a book on polyhedra, by Peter T. Cromwell. It was published by in 1997 by the Cambridge University Press, with an unrevised paperback edition in 1999.

David S. Richeson is an American mathematician whose interests include the topology of dynamical systems, recreational mathematics, and the history of mathematics. He is a professor of mathematics at Dickinson College, where he holds the John J. & Ann Curley Faculty Chair in the Liberal Arts.

Euler's Gem: The Polyhedron Formula and the Birth of Topology is a book on the formula for the Euler characteristic of convex polyhedra and its connections to the history of topology. It was written by David Richeson and published in 2008 by the Princeton University Press, with a paperback edition in 2012. It won the 2010 Euler Book Prize of the Mathematical Association of America.

Lectures in Geometric Combinatorics is a textbook on polyhedral combinatorics. It was written by Rekha R. Thomas, based on a course given by Thomas at the 2004 Park City Mathematics Institute, and published by the American Mathematical Society and Institute for Advanced Study in 2006, as volume 33 of their Student Mathematical Library book series.

Convex Polytopes is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics.

Regular Figures is a book on polyhedra and symmetric patterns, by Hungarian geometer László Fejes Tóth. It was published in 1964 by Pergamon in London and Macmillan in New York.

The Geometry of Numbers is a book on the geometry of numbers, an area of mathematics in which the geometry of lattices, repeating sets of points in the plane or higher dimensions, is used to derive results in number theory. It was written by Carl D. Olds, Anneli Cahn Lax, and Giuliana Davidoff, and published by the Mathematical Association of America in 2000 as volume 41 of their Anneli Lax New Mathematical Library book series.

Combinatorics: The Rota Way is a mathematics textbook on algebraic combinatorics, based on the lectures and lecture notes of Gian-Carlo Rota in his courses at the Massachusetts Institute of Technology. It was put into book form by Joseph P. S. Kung and Catherine Yan, two of Rota's students, and published in 2009 by the Cambridge University Press in their Cambridge Mathematical Library book series, listing Kung, Rota, and Yan as its authors. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

Introduction to Lattices and Order is a mathematical textbook on order theory by Brian A. Davey and Hilary Priestley. It was published by the Cambridge University Press in their Cambridge Mathematical Textbooks series in 1990, with a second edition in 2002. The second edition is significantly different in its topics and organization, and was revised to incorporate recent developments in the area, especially in its applications to computer science. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

References

  1. Zbl   1147.52300
  2. 1 2 3 Bayer, Margaret M., "Review of Computing the Continuous Discretely", zbMATH , Zbl   1114.52013
  3. 1 2 3 De Loera, Jesús A. (2007), "Review of Computing the Continuous Discretely", Mathematical Reviews , MR   2271992
  4. 1 2 3 4 5 Glass, Darren (February 2007), "Review of Computing the Continuous Discretely", MAA Reviews, Mathematical Association of America
  5. 1 2 3 4 Karpenkov, Oleg, "Review of Computing the Continuous Discretely", zbMATH , Zbl   1339.52002