Algorithms in combinatorial geometry.

*(English)*Zbl 0634.52001
EATCS Monographs on Theoretical Computer Science, Vol. 10. Berlin etc.: Springer-Verlag. XV, 423 p.; DM 98.00 (1987).

This monograph is devoted to computational geometry, a very active area of modern research that emerged in the early seventies and developed in strong connection with the older field of combinatorial geometry. The author’s intention was “to demonstrate that computational and combinatorial investigations in geometry are doomed to profit from each other”. In the choice of topics, he was guided by the attempt “to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure”; accordung to this, he expresses his belief “that arrangements of hyperplanes are at the very heart of computational geometry...”.

The book consists of three parts: I. Combinatorial geometry; II. Fundamental geometric algorithms; III. Geometric and algorithmic applications.

Part I is a self-contained introduction to the combinatorial geometry of arrangements of hyperplanes in Euclidean spaces. It starts in chapter I with a presentation of the basic facts, including some enumeration formulas, a definition of combinatorial equivalence (which depends on the choice of a distinguished direction in the ambient space), a discussion of the duality between arrangements and configurations of points and some related structures. This is followed in chapter 2 by detailed study of circular sequences of permutations, which serve as a tool for encoding two-dimensional arrangements in the plane. Chapter 3 deals with the relationship between the number of semispaces of configurations with fixed cardinality and the number of faces of levels in arrangements of hyperplanes. Asymptotic lower and upper bounds are established on these numbers, mainly in the two-dimensional case. Chapter 4 contains a treatment of some problems concerning dissections of point sets. Included are proofs of Radon’s and Helly’s theorems and of a discrete version of the ham-sandwich theorem; various methods are developed, which provide results on balanced dissections of two- and three-dimensional point sets. An analysis of the cardinality of zones in arrangements is performed in chapter 5; tight bounds in the plane and asymptotic tight bounds in higher dimensions are derived. Chapter 6 approaches the investigation of the complexity of collections of cells chosen from an arrangement. Euler’s formula and the Dehn-Sommerville relations for polytopes are obtained and used to derive an asymptotic version of the Upper Bound Theorem and various other results concerning upper and lower bounds for collections of cells.

Part II of the book is devoted to the presentation of some fundamental geometric algorithms. One of the most important problems, that of constructing an arrangement of hyperplanes, is treated in chapter 7. A detailed description is given of an algorithm which operates incrementally (addition of one hyperplane at a time). The analysis of the time-complexity of this algorithm provides an upper bound for the number of combinatorially non-equivalent arrangements of n hyperplanes in \(E^ d\). Chapter 8 covers the problem of constructing the convex hull of a finite set of points in \(E^ d\). Two different approaches are described for sets of points in the plane: the beneath-beyond method (which is then generalized to all dimensions), and the divide-and-conquer paradigm (which is extended to dimension 3). Another method is presented in chapter 9, which applies to the construction of more complicated structures in arrangements (skeletons). The algorithm is outlined first for the case of simple arrangements; then, by using the technique of “simulation of simplicity”, it is extended to arbitrary arrangements. Both static and dynamic data structures are described and used. Chapter 10 contains a discussion of linear programming, with applications to other geometric problems. The algorithmic method used is prune-and- search, which is applied first to the 2-dimensional case, then to higher dimensions. Another fundamental geometric problem, that of locating a specific point in a given planar subdivision, is treated in chapter 11. An efficient solution (later improved to an optimal one) is obtained, first for monotone subdivisions, then for general subdivisions by using a refinement procedure.

Part III of the book presents some applications, both algorithmic and combinatorial, of the results from the other two parts. Several problems where the transformation from configurations to arrangements reduces the difficulties encountered are discussed in chapter 12. A representative sample of six problems is presented: the computation of largest convex sets in the plane, the visibility graph for line segments, the determination of minimum measure simplices, two generalizations of sorting to higher dimensions, and a vector-sum maximization problem. Chapter 13 contains a detailed discussion of Voronoi diagrams (classical, higher-order, and with weighted sites), and of many of their applications. A few other applications of earlier results to separation and intersection problems in Euclidean spaces are derived in chapter 14. The final chapter 15 reviews and discusses some of the “design paradigms” from the text. Each of these methods (divide-and-conquer, incremental construction, and prune-and-search) is applied to an appropriate variant of a generic transversal problem defined in the plane (stabbing line segments). Static and dynamic solutions to related search problems are derived.

Each chapter concludes with a collection of exercises and problems which provide results that extend the material presented in the text; some of these are in fact open research problems. Each of these collections is followed by a set of bibliographic notes.

There is some overlap with other texts on computational geometry, such as the book by F. P. Preparata and M. I. Shamos [Computational geometry. An introduction. (1985; Zbl 0575.68059)] and Chapter VIII in K. Mehlhorn’s monograph [Data structures and algorithms 3: Multi- dimensional searching and computational geometry. (1984; Zbl 0556.68003)], but the author offers here alternative approaches, with different methods and proofs.

The book covers a lot of advanced material and leads the reader to very recent results and current research. It is certainly a valuable contribution towards the development and systematization of the area of computational geometry.

The book consists of three parts: I. Combinatorial geometry; II. Fundamental geometric algorithms; III. Geometric and algorithmic applications.

Part I is a self-contained introduction to the combinatorial geometry of arrangements of hyperplanes in Euclidean spaces. It starts in chapter I with a presentation of the basic facts, including some enumeration formulas, a definition of combinatorial equivalence (which depends on the choice of a distinguished direction in the ambient space), a discussion of the duality between arrangements and configurations of points and some related structures. This is followed in chapter 2 by detailed study of circular sequences of permutations, which serve as a tool for encoding two-dimensional arrangements in the plane. Chapter 3 deals with the relationship between the number of semispaces of configurations with fixed cardinality and the number of faces of levels in arrangements of hyperplanes. Asymptotic lower and upper bounds are established on these numbers, mainly in the two-dimensional case. Chapter 4 contains a treatment of some problems concerning dissections of point sets. Included are proofs of Radon’s and Helly’s theorems and of a discrete version of the ham-sandwich theorem; various methods are developed, which provide results on balanced dissections of two- and three-dimensional point sets. An analysis of the cardinality of zones in arrangements is performed in chapter 5; tight bounds in the plane and asymptotic tight bounds in higher dimensions are derived. Chapter 6 approaches the investigation of the complexity of collections of cells chosen from an arrangement. Euler’s formula and the Dehn-Sommerville relations for polytopes are obtained and used to derive an asymptotic version of the Upper Bound Theorem and various other results concerning upper and lower bounds for collections of cells.

Part II of the book is devoted to the presentation of some fundamental geometric algorithms. One of the most important problems, that of constructing an arrangement of hyperplanes, is treated in chapter 7. A detailed description is given of an algorithm which operates incrementally (addition of one hyperplane at a time). The analysis of the time-complexity of this algorithm provides an upper bound for the number of combinatorially non-equivalent arrangements of n hyperplanes in \(E^ d\). Chapter 8 covers the problem of constructing the convex hull of a finite set of points in \(E^ d\). Two different approaches are described for sets of points in the plane: the beneath-beyond method (which is then generalized to all dimensions), and the divide-and-conquer paradigm (which is extended to dimension 3). Another method is presented in chapter 9, which applies to the construction of more complicated structures in arrangements (skeletons). The algorithm is outlined first for the case of simple arrangements; then, by using the technique of “simulation of simplicity”, it is extended to arbitrary arrangements. Both static and dynamic data structures are described and used. Chapter 10 contains a discussion of linear programming, with applications to other geometric problems. The algorithmic method used is prune-and- search, which is applied first to the 2-dimensional case, then to higher dimensions. Another fundamental geometric problem, that of locating a specific point in a given planar subdivision, is treated in chapter 11. An efficient solution (later improved to an optimal one) is obtained, first for monotone subdivisions, then for general subdivisions by using a refinement procedure.

Part III of the book presents some applications, both algorithmic and combinatorial, of the results from the other two parts. Several problems where the transformation from configurations to arrangements reduces the difficulties encountered are discussed in chapter 12. A representative sample of six problems is presented: the computation of largest convex sets in the plane, the visibility graph for line segments, the determination of minimum measure simplices, two generalizations of sorting to higher dimensions, and a vector-sum maximization problem. Chapter 13 contains a detailed discussion of Voronoi diagrams (classical, higher-order, and with weighted sites), and of many of their applications. A few other applications of earlier results to separation and intersection problems in Euclidean spaces are derived in chapter 14. The final chapter 15 reviews and discusses some of the “design paradigms” from the text. Each of these methods (divide-and-conquer, incremental construction, and prune-and-search) is applied to an appropriate variant of a generic transversal problem defined in the plane (stabbing line segments). Static and dynamic solutions to related search problems are derived.

Each chapter concludes with a collection of exercises and problems which provide results that extend the material presented in the text; some of these are in fact open research problems. Each of these collections is followed by a set of bibliographic notes.

There is some overlap with other texts on computational geometry, such as the book by F. P. Preparata and M. I. Shamos [Computational geometry. An introduction. (1985; Zbl 0575.68059)] and Chapter VIII in K. Mehlhorn’s monograph [Data structures and algorithms 3: Multi- dimensional searching and computational geometry. (1984; Zbl 0556.68003)], but the author offers here alternative approaches, with different methods and proofs.

The book covers a lot of advanced material and leads the reader to very recent results and current research. It is certainly a valuable contribution towards the development and systematization of the area of computational geometry.

Reviewer: J.Weinstein

##### MSC:

52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |

52A35 | Helly-type theorems and geometric transversal theory |

68Q25 | Analysis of algorithms and problem complexity |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |

68P10 | Searching and sorting |

68R10 | Graph theory (including graph drawing) in computer science |

05A15 | Exact enumeration problems, generating functions |

05B30 | Other designs, configurations |