''Algorithmic Geometry'' is a textbook on

computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

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

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 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 A university press is an academic publishing hou ...

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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

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 efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

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

, 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 or 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 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 points ...

, 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 function#As a polynomial function, li ...

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 (geometry), plane (when \mathcal is a set of points i ...

for two- and three-dimensional data,

arrangements of hyperplanes In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set ''A'' of hyperplanes in a linear, affine, or projective space ''S''. Questions about a hyperplane arrangement ''A'' generally concern geometrical, top ...

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

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

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 mathematics, pure and applied mathematics, produced by the Berlin office of FIZ Karlsruhe – Leibniz Institute for Informa ...

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

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