''Algorithmic Geometry'' is a textbook on computational geometry. It was originally written in the

French language French ( or ) is a Romance language of the Indo-European family. It descended from the Vulgar Latin of the Roman Empire, as did all Romance languages. French evolved from Gallo-Romance, the Latin spoken in Gaul, and more specifically in ...

Jean-Daniel Boissonnat Jean-Daniel Boissonnat (born 18 May 1953) is a French computer scientist, who works as a director of research at the French Institute for Research in Computer Science and Automation (INRIA). He is an invited professor of computational geometry at ...

and

Mariette Yvinec Mariette Yvinec is a French researcher in computational geometry at the French Institute for Research in Computer Science and Automation (INRIA) in Sophia Antipolis. She is one of the developers of CGAL, a software library of computational geomet ...

, and published as ''Géometrie algorithmique'' by Edusciences in 1995. It was translated into English by Hervé Brönnimann, with improvements to some proofs and additional exercises, and published by the

Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambr ...

in 1998.

Topics

The book covers the theoretical background and analysis of

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

s in computational geometry, their implementation details, and their applications. It is grouped into five sections, the first of which covers background material on the design and analysis of algorithms and

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...

s, including

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, and techniques for designing

randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performa ...

s. Its subsequent sections each consist of a chapter on the mathematics of a subtopic in this area, presented at the level of detail needed to analyze the algorithms, followed by two or three chapters on algorithms for that subtopic. The topics presented in these sections and chapters include convex hulls and

convex hull algorithms Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of poin ...

, low-dimensional randomized

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

point set triangulation A triangulation of a set of points \mathcal in the Euclidean space \mathbb^d is a simplicial complex that covers the convex hull of \mathcal, and whose vertices belong to \mathcal. In the plane (when \mathcal is a set of points in \mathbb^2), tri ...

for two- and three-dimensional data, arrangements of hyperplanes, of line segments, and of triangles,

Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...

s, and

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...

Audience and reception

The book can be used as a graduate textbook, or as a reference for computational geometry research. Reviewer

Peter McMullen Peter McMullen (born 11 May 1942) is a British mathematician, a professor emeritus of mathematics at University College London. Education and career McMullen earned bachelor's and master's degrees from Trinity College, Cambridge, and studied at ...

calls it "a welcome addition to the shelves of anyone interested in algorithmic geometry".

References

{{reflist, refs= {{citation, title=none, first=S., last=Stifter, journal=

zbMATH zbMATH Open, formerly Zentralblatt MATH, is a major reviewing service providing reviews and abstracts for articles in pure and applied mathematics, produced by the Berlin office of FIZ Karlsruhe – Leibniz Institute for Information Infrastructur ...

, zbl=0917.68212 {{citation, title=none, last=Hecker, first=Hans-Dietrich, journal=

Mathematical Reviews ''Mathematical Reviews'' is a journal published by the American Mathematical Society (AMS) that contains brief synopses, and in some cases evaluations, of many articles in mathematics, statistics, and theoretical computer science. The AMS also ...

, year=1999, mr=1631175 {{citation, last=McMullen, first=Peter, authorlink=Peter McMullen, date=November 1999, doi=10.1112/blms/31.6.758, issue=6, journal=

Bulletin of the London Mathematical Society The London Mathematical Society (LMS) is one of the United Kingdom's learned societies for mathematics (the others being the Royal Statistical Society (RSS), the Institute of Mathematics and its Applications (IMA), the Edinburgh Mathematical ...

, pages=758–759, title=none, volume=31 Computational geometry Mathematics textbooks 1995 non-fiction books 1998 non-fiction books