Several problems, geometric or of other kinds, use the notion of a polytope in d-dimensional space more or less implicitly. The preceding chapters show how to efficiently build the incidence graph which encodes the whole facial structure of a polytope given as the convex hull of a set of points. Using duality, the same algorithms allow one to build the incidence graph of a polytope defined as the intersection of a finite number of half-spaces. It is not always necessary, however, to explicitly enumerate all the faces of the polytope that underlies a problem. This is the case in linear programming problems, which are the topic of this chapter.

Section 10.1 defines what a linear programming problem is, and sets up the terminology commonly used in optimization. Section 10.2 gives a truly simple algorithm that solves this class of problem. Finally, section 10.3 shows how linear programming may be used as an auxiliary for other geometric problems. A linear programming problem may be seen as a shortcut to avoid computing the whole facial structure of some convex hull. Paradoxically, the application we give here is an algorithm that computes the convex hull of n points in dimension d. Besides its simplicity, the interest of the algorithm is mostly that its complexity depends on the output size as well as on the input size. Here, the output size is the number f of faces of all dimensions of the convex hull, and thus ranges widely from O(1) (size of a simplex) to Θ(n⌊d/2⌋ (size of a maximal polytope).

We have seen in the previous chapter that in some cases completion generates a convergent term rewriting system for a given equational theory, and that such a system can then be used to decide the word problem for this equational theory. A very similar approach has independently been developed in the area of computer algebra, where Gröbner bases are used to decide the ideal congruence and the ideal membership problem in polynomial rings. The close connection to rewriting is given by the fact that Gröbner bases define convergent reduction relations on polynomials, and that the ideal congruence problem can be seen as a word problem. In addition, Buchberger's algorithm, which is very similar to the basic completion procedure presented above, can be used to compute Gröbner bases. In contrast to the situation for term rewriting, however, termination of the reduction relation can always be guaranteed, and Buchberger's algorithm always terminates with success. The purpose of this chapter is, on the one hand, to provide another example for the usefulness of the rewriting and completion approach introduced above. On the other hand, the basic definitions and results from the area of Gröbner bases are presented using the notations and results for abstract reduction systems introduced in Chapter 2.

The ideal membership problem

Let us first introduce the basic algorithmic problems that can be solved with the help of Gröbner bases.

In an arrangement of n lines in the plane, all the cells are convex and thus have complexity O(n). Moreover, given a point A, the cell in the arrangement that contains A can be computed in time Θ(n log n): indeed, the problem reduces to computing the intersection of n half-planes bounded by the lines and containing A (see theorem 7.1.10).

In this chapter, we study arrangements of line segments in the plane. Consider a set S of n line segments in the plane. The arrangement of S includes cells, edges, and vertices of the planar subdivision of the plane induced by S, and their incidence relationships.

Computing the arrangement of S can be achieved in time O(n log n + k) where k is the number of intersection points (see sections 3.3 and 5.3.2, and theorem 5.2.5). All the pairs of segments may intersect, so in the worst case we have k = Ω(n2).

For a few applications, only a cell in this arrangement is needed. This is notably the case in robotics, for a polygonal robot moving amidst polygonal obstacles by translation (see exercise 15.6). The reachable positions are characterized by lying in a single cell of the arrangement of those line segments that correspond to the set of positions of the robot when a vertex of the robot slides along the edge of an obstacle, or when the edge of a robot maintains contact with an obstacle at a point.

This chapter studies the problem of determining whether a TRS is confluent. After a brief look at the (undecidable) decision problem, the rest of the chapter divides neatly into two parts:

The first part deals with terminating systems, for which confluence turns out to be decidable. This is a key result in our search for decidable equational theories: if E constitutes a terminating TRS, we can decide if it is also confluent, in which case we know by Theorem 4.1.1 that ≈E is decidable.

The second part deals with those systems not covered by the first part, namely (potentially) nonterminating ones. The emphasis here is not on deciding ≈E by rewriting, which requires termination, but on the computational content of a TRS. Viewing a TRS as a program, confluence simply means that the program is deterministic. We show that for the class of so-called orthogonal systems, where no two rules interfere with each other, confluence holds irrespective of termination. This result has immediate consequences for the theory and design of functional programming languages.

The decision problem

Just as for termination and most other interesting properties (of term rewriting systems or otherwise), confluence is in general undecidable:

Theorem 6.1.1The following problem is undecidable:

Instance: A finite TRS R.

Question: Is R confluent?

Proof Given a set of identities E such that Var(l) = Var(r) and neither l nor r is a variable for all l ≈ r ∈ E, we can reduce the ground word problem for E to the confluence problem of a related TRS as follows.

Data structures are the keystone on which all algorithmic techniques rely. The definition of basic yet high-level data structures, with precise features and a well-studied implementation, allows the designer of an algorithm to concentrate on the core issues of the problem. For the programmer, it saves the tedious task of creating and administrating each pointer.

Throughout this book, we describe data structures especially designed for representing geometric objects and dealing with them. But computational geometers also make extensive use of data structures that represent subsets or sequences of objects. These structures can be used directly by the algorithms, or modified and augmented for geometric use. The first part of this chapter recalls the terminology and features of each basic data structure used in this book. It is useful to know how these structures can be implemented and what their performances are. The most delicate problem is undoubtedly the one addressed by dictionaries and priority queues, which treat finite subsets of a totally ordered set (the universe). To achieve better efficiency, these structures are usually encoded as balanced binary trees. For instance, the second part of this chapter describes red-black trees, a class of balanced trees that can be used to implement dictionaries and priority queues. Finally, when the universe is finite, dictionaries and priority queues can be even more efficiently implemented by other more sophisticated techniques, the characteristics of which are given without proof in the third part of this chapter.

The original text was written in French. The translator's task was constrained by the fact that most of the French words used in the original text were originally coined by their authors in English publications, or have a commonly accepted translation into English. The problem was thus one of reverse engineering! Fortunately, there are now many textbooks in computational geometry which helped to resolve conflicts in terminology. Whenever possible, the translation conformed to the standard terminology or, for the more specialized vocabulary, to the terminology set up in the original papers.

For graphs, however, the use of the word edge overlapped with that of 1-faces for common geometric structures. Similarly, the word vertex is also used for polytopes in a different meaning than for graphs. The situation is somewhat complicated by the fact that sometimes graphs are introduced whose nodes are edges of a polygon. We have followed the French text in systematically using the words node and arc for the set underlying a graph and the symbolic links between the elements of this set. The terminology related to graphs is recalled in subsection 2.2.1.

We have departed from the French text for the word saillant (meaning salient) to follow the usage with convex vertices/edges, as opposed to reflex. Although a vertex or an edge is always convex in the original meaning of convexity, here it means (as most people would understand it) that the internal angle around the vertex or around the edge is smaller than π.

A randomized algorithm is an algorithm that makes random choices during its execution. A randomized algorithm solves a deterministic problem and, whatever the random choices are, always runs in a finite time and outputs the correct solution to the problem. Therefore, only the path that the algorithm chooses to follow to reach the solution is random: the solution is always the same. Most randomized methods lead to conceptually simple algorithms, which often yield a better performance than their deterministic counterparts. This explains the success encountered by these methods and the important position they are granted in this book. The time and space used when running a randomized algorithm depend both on the input set and on the random choices. The performances of such an algorithm are thus analyzed on the average over all possible random choices made by the algorithm, yet in the worst case for the input. Randomization becomes interesting when this average complexity is smaller than the worst-case complexity of deterministic algorithms that solve the same problem.

The randomized algorithms described in this chapter, and more generally encountered in this book, use the randomized incremental method. The incremental resolution of a problem consists of two stages: first, the solution for a small subset of the data is computed, then the remaining input objects are inserted while the current solution is maintained. An incremental algorithm is said to be randomized if the data are inserted in a deliberately random order.

There are many algorithms that compute the convex hull of a set of points in two and three dimensions, and the present chapter does not claim to give a comprehensive survey. In fact, our goal is mainly to explore the possibilities offered by the divide-and-conquer method in two and three dimensions, and to expand on the incremental method in the case of a planar polygonal line.

In dimension 2, the divide-and-conquer method leads, like many other methods, to a convex hull algorithm that is optimal in the worst case. The main advantage of this method is that it also generalizes to three dimensions while still leading to an algorithm that is optimal in the worst case, which is not the case for the incremental method described in chapter 8. The performances of this divide-andconquer algorithm rely on the existence of a circular order on the edges incident to a given vertex. In dimensions higher than three, such an order does not exist, and the divide-and-conquer method is no longer efficient for computing convex hulls. The 2-dimensional divide-and-conquer algorithm is described in section 9.2, and generalized to dimension 3 in section 9.3. But before these descriptions, we must comment on the representation of polytopes in dimensions 2 and 3, and describe a data structure that explicitly provides the circular order of the edges or facets around a vertex of a 3-dimensional polytope.

The geometric problems encountered in this chapter are again stated in the abstract framework of objects, regions, and conflicts introduced in chapter 4. A dynamic algorithm maintains the set of regions defined and without conflict over the current set of objects, when the objects can be removed from the current set as well as added. In contrast, on-line algorithms that support insertions but not deletions are sometimes called semi-dynamic.

Throughout this chapter, we denote by S the current set of objects and use the notation introduced in the previous two chapters to denote the different subsets of regions defined over S. In particular, F0(S) stands for the set of regions defined and without conflict over S. To design a dynamic algorithm that maintains the set F0(S) is a much more delicate problem than its static counterpart. In the previous chapter, we have shown how randomized incremental methods provide simple solutions to static problems. In addition, the influence graph techniques naturally lead to the design of semi-dynamic algorithms. In this chapter, we propose to show how the combined use of both conflict and influence graphs can yield fully dynamic algorithms.

The general idea behind our approach is to maintain a data structure that meets the following two requirements:

• It allows conflicts to be detected between any object and the regions defined and without conflict over the current subset.

• After deleting an object, the structure is identical to what it would have been, had the deleted object never been inserted.

A polytope is defined as the convex hull of a finite number of points, or also as the bounded intersection of a finite number of half-spaces. Section 7.1 recalls the equivalence of these definitions, and gives the definition of the faces of a polytope. Polarity is also introduced in this section. The polarity centered at O is a dual transform between points and hyperplanes in Euclidean spaces which induces a duality on the set of polytopes containing the center O. Simple and simplicial polytopes are also defined in this section. Section 7.2 takes a close interest in the combinatorics of polytopes. It contains a proof of Euler's relation and the Dehn–Sommerville relations. Euler's relation is the only linear relation between the numbers of faces of each dimension of any polytope, and the Dehn–Sommerville relations are linear relations satisfied by simple polytopes. These relations can be used to show the celebrated upper bound theorem which bounds the number of faces of all dimensions of a d-dimensional polytope as a function of the number of its vertices, or facets. Considering cyclic polytopes shows that the upper bound theorem yields the best possible asymptotic bound. Linear unbounded convex sets enjoy similar properties and are frequently encountered in the rest of this book. Section 7.3 extends these definitions and properties to unbounded polytopes. A simple method to enforce coherence in these definitions is to consider the Euclidean space as embedded in the oriented projective space, an oriented version of the classical projective space.

A new field

Many disciplines require a knowledge of how to efficiently deal with and build geometric objects. Among many examples, one could quote robotics, computer vision, computer graphics, medical imaging, virtual reality, or computer aided design. The first geometric results with a constructive flavor date back to Euclid and remarkable developments occurred during the nineteenth century. However, only very recently did the design and analysis of geometric algorithms find a systematic treatment: this is the topic of computational geometry which as a field truly emerged in the mid 1970s. Since then, the field has undergone considerable growth, and is now a full-fledged scientific discipline, of which this text presents the foundations.

Contents and layout of this book

The design of efficient geometric algorithms and their analysis are largely based on geometric structures, algorithmic data structuring techniques, and combinatorial results.

A major contribution of computational geometry is to exemplify the central role played by a small number of fundamental geometric structures and their relation to many geometric problems.

Geometric data structures and their systematic analysis guided the layout of this text. We have dedicated a part to each of the fundamental geometric structures: convex hulls, triangulations, arrangements, and Voronoi diagrams.

In order to control the complexity of an algorithm, one must know the complexity of the objects that it generates. For example, it is essential to have a sharp bound on the number of facets of a polytope as a function of the number of its vertices: this is the celebrated upper-bound theorem proved by McMullen in 1970.