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

French language French ( or ) is a Romance languages, Romance language of the Indo-European languages, Indo-European family. Like all other Romance languages, it descended from the Vulgar Latin of the Roman Empire. French evolved from Northern Old Gallo-R ...

by Jean-Daniel Boissonnat and Mariette Yvinec, 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 was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...

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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

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 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 relationships amo ...

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 explores the relationships between these classifications. A computational problem ...

, 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 performan ...

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 hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...

s and

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

, 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 and objective are represented by linear function#As a polynomia ...

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), tr ...

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. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (calle ...

s, and

Delaunay triangulation In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...

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 Infrastru ...

, 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 pu ...

, 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 Soc ...

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