Review of Computational Geometry: Algorithms and Applications (2nd ed.) by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf
Computational Geometry is a wide-ranging introductory text which exposes readers to the main themes in modern computational geometry. Each chapter introduces a subfield of computational geometry, via natural problems and basic algorithms; exercises and ...
Review of Parameterized Complexity by R. Downey and M. Fellows
One of the most pervasive critiques of Computational Complexity, coming from the applied Computer Science community, is that it is an abstract, largely irrelevant field, that fails to capture the various intuitions concerning the complexity of "real-...
Review of: Modern Graph Theory by Béla Bollobás
Graph Theory is still a relatively young subject, and debate still rages on what material constitutes the core results that any introductory text should include. Bollobás has chosen to introduce graph theory - including recent results - in a way ...
A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions
This issue's column, Part II of the article started in the preceding issue, is about progress on the question of whether NP has sparse hard sets with respect to weak reductions.Upcoming Complexity Theory Column articles include A. Werschulz on ...
Principles of distributed computing: an exciting challenge
The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, ...
Computational geometry column 40
It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NP-complete. Their 3SAT-reduction proof is discussed.