Algorithmic Geometry
Algorithmic Geometry
Boissonnat
M. Yvinec
Algorithmic
Geometry
2LVI~tl I
A1
A / ;4
/1A, " ~
Zj
J?'
fi <I
/.
Algorithmic geometry
Algorithmic Geometry
Jean-Daniel Boissonnat
Mariette Yvinec
INRIA Sophia-Antipolis, France
.wl CAMBRIDGE
v UNIVERSITY PRESS
PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE
The Pitt Building, Trumpington Street, Cambridge CB2 1RP, United Kingdom
CAMBRIDGE UNIVERSITY PRESS
The Edinburgh Building, Cambridge CB2 2RU, United Kingdom
40 West 20th Street, New York, NY 10011-4211, USA
10 Stamford Road, Oakleigh, Melbourne 3166, Australia
A catalogue record for this book is available from the British Library
4.i*
To Bertrand,
Martine,
Cecile,
Clement,
Alexis,
Marion,
Quentin,
Romain,
Eve,
and the others...
Table of contents
Preface xv
Acknowledgments xxi
References 492
Notation 508
Index 513
Preface
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.
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 struc-
tures: convex hulls, triangulations, arrangements, and Voronoi diagrams.
In order to control the complexity of an algorithm, one must know the com-
plexity 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. Combinatorial geometry plays an essential role in this book and the
first chapters of each part lay the mathematical grounds and prove the basic
combinatorial properties satisfied by the corresponding geometric structures.
xvi Preface
At the same time as geometric data structures of general interest were be-
ing studied, new algorithmic techniques were devised. To general algorithmic
paradigms, computational geometry added its own geometric techniques. The
first purely geometric paradigm in the history of the field, the sweep method,
was originally used by Bentley and Ottmann in an algorithm that computes the
intersection of a set of line segments in the plane. Subsequent developments of
general techniques soon encountered important theoretical difficulties which led
to quite sophisticated variants and theoretical constructions without truly affect-
ing the practice of the field. As a reaction against this tendency, a few authors
decided it was more desirable to look for simple algorithms which were efficient
on the average, rather than algorithms whose good behavior in the worst case
did not guarantee good behavior in practical instances of the problem.
The recent body of work on randomization gave the most significant answer
in this direction. An algorithm is said to be randomized if, after making ran-
dom choices during its execution, it gives the solution to a purely deterministic
problem. No probabilistic assumptions are made about the input objects, and
randomness is used only to choose the path that the algorithm will follow to the
solution. Randomized algorithms are often simple to conceive and to program,
and their average complexity (over all the random choices made during the exe-
cution) is usually very good, often even optimal. Randomization leads to general
methods for the design and analysis of algorithms, and allows efficient compu-
tation of geometric structures, both in theory and practice. For these reasons,
randomization holds a central position in this book. The first three chapters in the
first part contain all the generic material related to randomization, and instances
of randomized algorithms are presented throughout the subsequent chapters.
The goal of this book is twofold. In the first place, it aims at giving a coherent
exposition of the field rather than a collection of results, and at presenting only
methods that possess a certain degree of generality. The algorithms presented in
this book have been selected to work in all dimensions whenever this was possible:
the case of dimension 2 only receives special treatment when particular methods
lead to significant improvement, which happens surprisingly seldom.
In the second place, this book aims at presenting solutions which, while theoret-
ically efficient and relevant, remain relatively simple and applicable in practical
situations. Most of these algorithms have been implemented by their authors and
their practical behavior has turned out to agree with the analyses developed in
this book.
Nevertheless, this book does not claim to be a comprehensive treatment of the
whole field of computational geometry. In particular, the reader will find mention
Preface xvii
This book assumes no particular knowledge from the reader and should be ac-
cessible to any enthusiastic geometer. Its contents have been taught in several
graduate courses both in mathematics and in computer science. It is aimed both
at mathematicians interested in a constructive approach to geometry, and at
computer scientists in need of an accurate treatment of computational geometry.
Students, researchers, and engineers in more practical fields will find here a useful
methodology and practical algorithms.
There is more than one way to read this book. The authors have tried to respect
xviii Preface
1In his essay Comme un Roman, the French writer Daniel Pennac describes the unalienable
rights of the reader as:
1. The right not to read.
2. The right to jump ahead.
3. The right not to finish a book.
4. The right to read again.
5. The right to read anything.
6. The right to Bovarysm (textually transmissible disease).
7. The right to read here and there.
8. The right to thesaurize.
9. The right to read aloud.
10. The right not to say anything.
Translator's Preface
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! For-
tunately, 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 ter-
minology 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 7r. Luckily, this definition is never used
for higher-dimensional faces, and therefore should not create confusion.
Vertical decompositions as they are introduced in this book have also been
called by various names, such as trapezoidal maps, vertical partitions, and verti-
cal visibility maps. As with other authors, we have preferred the phrase vertical
decomposition or even decomposition for short, in order to emphasize the rela-
tion with other geometric decomposition schemes, for example decompositions of
arrangements, polygons, or polyhedra into simplices (also called triangulations).
We should properly speak of the decomposition of the plane induced by a set of
segments. The reader will forgive us for using the phrase decomposition of (a set
of) line segments.
xx Translator'spreface
This book benefited from the joint work of researchers of the PRISME project at
INRIA and is inspired by much common work with Panagiotis Alevizos, Andre
CGrezo, Olivier Devillers, Katrin Dobrindt, Franco Preparata, Micha Sharir, Boaz
Tagansky, and Monique Teillaud. To proofread the manuscript, Jean Berstel and
Franck Nielsen provided their help with an unfailing friendship. The translation
has been carried out by Herv6 Br6nnimann who not only translated but also
corrected the original manuscript in many places. Many thanks to all of them! A
book about geometry could not exist without drawings, and a book about com-
putational geometry could not exist without computer generated drawings. The
Jrdraw software provided the ruler and compass, and together with its designer
Jean-Pierre Merlet it played an essential role in the conception of this book.
Part I
Algorithmic tools
The first part of this book introduces the most popular tools in computational
geometry. These tools will be put to use throughout the rest of the book.
The first chapter gives a framework for the analysis of algorithms. The concept
of complexity of an algorithm is reviewed. The underlying model of computation
is made clear and unambiguous.
The second chapter reviews the fundamentals of data structures: lists, heaps,
queues, dictionaries, and priority queues. These structures are mostly imple-
mented as balanced trees. To serve as an example, red-black trees are fully
described and their performances are evaluated.
The third chapter illustrates the main algorithmic techniques used to solve
geometric problems: the incremental method, the divide-and-conquer method,
the sweep method, and the decomposition method which subdivides a complex
object into elementary geometric objects.
Finally, chapters 4, 5, and 6 introduce the randomization methods which have
recently made a distinguished appearance on the stage of computational geom-
etry. Only the incremental randomized method is introduced and used in this
book, as opposed to the randomized divide-and-conquer method.
Chapter 1
Notions of complexity
scribed in the algorithm. Likewise, the spatial complexity describes how many
memory units are needed in order to store all the data required for the execution
of the corresponding program.
The model of computation underlying all the algorithms given in this book is
the so-called real RAM model. In this model, each memory unit can hold the
representation of a real number, and accessing a memory location takes constant
time, that is, time independent of the particular location to be accessed. The
machine can work on real numbers of arbitrary precision for the same cost. The
elementary operations are:
1. the comparison of two real numbers,
2. the four arithmetic operations,
3. all the usual mathematical functions, such as logarithm, exponential, trigo-
nometric functions, etc.
4. the integer part computation.
The assumption that all numbers can be represented exactly allows us to ignore
all the problems related to numerical accuracy, as they occur in the real world. In
particular, the otherwise very relevant problems of robustness of these algorithms
in relation to rounding and numerical inaccuracies are not mentioned in this book.
Output-sensitive complexity
An algorithm that solves a given problem usually builds, for a given input, a
result called the output, which embodies the solution to the problem. The size
of the output equals the number of memory units needed to store this result.
Obviously, the size of the output depends on the size of the input, but also on
the input itself.
For a given problem, the worst-case output size, or output size in the worst
case, is the function s(n) that upper bounds the output size for all inputs of
size n. The algorithm under consideration needs to at least write the output,
therefore the size of the output in the worst case is an elementary lower bound
on the running time complexity in the worst case.
For a given problem and a given input size, however, the output size can some-
times change a lot depending on the actual input given to the algorithm. For
instance, consider the problem of computing all the intersecting pairs of a set
of line segments in the plane. For a set of n segments, the input consists of 4n
real numbers, two for each endpoint. There might be as few as no intersections,
and as many as n(n)2 In this case it is interesting to have at hand adaptive
algorithms whose time complexity is a function of the output size. The number
of elementary operations executed by such an algorithm depends on the size of
the output for the instance of the problem, and not on the size of the output in
the worst case. For instance, in the problem of reporting all pairs of intersecting
line segments, the number of elementary operations carried out by the algorithm
should be a function of the number of intersecting pairs, which is not true of the
naive algorithm that tests all the pairs for intersection.
An adaptive algorithm can be analyzed in terms of both variables n and s,
6 Chapter 1. Notions of complexity
the respective sizes of the input and the output. The worst-case complexity of
an adaptive algorithm is the function f (n, s) that upper bounds the number of
elementary operations needed for solving all the instances of the problem with
input size n and output size s. Likewise, the average-case complexity of such
an algorithm is the function g(n, s) that upper bounds the number of operations
carried out by the algorithm, averaged over all the instances of the problem with
input size n and output size s.
In this book, the reader will find many randomized algorithms, that is, algorithms
whose execution is to some extent random. Such an algorithm will make ran-
dom choices during its execution, and these choices will influence its subsequent
behavior. In all cases, the algorithm will output the correct answer to the given
problem, but the number of elementary operations needed for this will greatly
depend on the random choices. The efficiency of a randomized algorithm is then
evaluated as an average over all possible random choices. The analysis is then
called a randomized analysis. However, such an analysis by no means involves
any statistical hypothesis on the data itself. Rather, the complexity is averaged
over all possible executions of the algorithm in the worst case for the input.
It happens frequently that we have to answer many different questions of the same
kind about a given set of data. For example, given a set of lines in the plane, the
questions might ask for some kind of localization. Each query consists of a point
in the plane, and the question asks for the enclosing cell in the subdivision of the
plane induced by the lines. In cases such as this, it often pays off to compute
a data structure during a preprocessing phase, which in turn will be queried
repeatedly for all the different requests. The analysis therefore concerns both
the complexity of the preprocessing phase and that of answering the requests. In
some cases, the data structure is semi-dynamic, which means that it is possible
to add more data on-line; it may also be fully dynamic, meaning that deletions
as well as insertions are allowed. Each type of operation (insertion, deletion,
query) has its own associated cost. Sometimes, the cost of a single operation
is hard to evaluate, but one may estimate the compounded cost of a number of
these operations. The complexity of such a sequence divided by the number of
operations gives the amortized complexity of one operation. Such an analysis is
then called an amortized analysis.
1.1. The complexity of algorithms 7
Al (n) = 2n
Ak(n) = An (I),
where Akn) is the function obtained by composing the function Ak with itself
n times. Henceforth, we will write A(n) for An(n). The Ackermann function is
increasing, and its rate of growth is very fast. Here are the first values of this func-
tion: A(1) = 2, A(2) = 4, A(3) = 16, A(4) is a tower of 65,536 powers of 2. The
functional inverse of this function, defined by a(n) = min{p > 1 : A(p) > n},
'The notation log stands for the logarithm in base 2, which in this book will be assumed as
the base for all logarithm functions unless otherwise stated.
8 Chapter 1. Notions of complexity
lim f( )=0.
n-~oog(n)
the complexity g(n) of algorithm B, that is f(n) = O(g(n)). The latter asymp-
totic statement implies that, from a certain input size on, algorithm A will beat
its competitor B in terms of running time. Nothing is said, however, about the
threshold beyond which this is the case (the value of this threshold depends on
the constants no and c concealed by the big-oh notation). One must therefore
refrain from choosing, for a particular practical situation, the algorithm whose
asymptotic analysis yields a complexity with the smallest order of magnitude.
The elegance and simplicity of an algorithm are both likely to lower the order of
magnitude of the concealed constants, and should be taken into consideration if
appropriate. For these reasons, this book usually presents several algorithms for
solving the same problem.
Sorting n numbers according to the natural (increasing) order is one of the rare
problems whose complexity can be found by direct reasoning. Given a finite
sequence of n numbers, X = (xl,...,xx), all in some totally ordered set (for
instance, N or R), to sort them is to determine a permutation a of {1,..., n}
such that the sequence
Proof. The proof of this theorem is based on the idea of a decision tree. One
can always assume that the sequence under consideration does not contain the
same element twice; thus all the numbers in the sequence are distinct. For lack of
other information on the input data, the algorithm can only perform comparisons,
then branch accordingly, depending on the result of this comparison. Branching
is a binary process since there can be only two results to the comparison. The
execution of such an algorithm can be represented by a binary tree, the decision
tree. Each leaf represents a possible output from the algorithm; in our case,
an output is one of the n! possible permutations of the set {1,...,n}. Each
internal node represents some state of the algorithm, at which the algorithm will
perform a comparison. Depending on the result of this comparison and on its
current state, the algorithm will then branch to its right or left descendant in the
tree, and subsequently perform the comparison stored at that node, or output
the corresponding permutation if it reaches a leaf. All computations begin at the
root of the tree, and each execution therefore corresponds to a path from the root
to a leaf of the tree. The number of comparisons performed by the algorithm in
the worst case is thus the height of the decision tree. A possible decision tree
sorting three elements a, b, c is shown in figure 1.1. For our sorting problem, the
1.2. Optimality, lower bounds 11
ri (n)
Problem A Problem B
73 (n)
decision tree has at least n! leaves, and its height h is thus at least log(n!) which,
according to Stirling's approximation formula, 2 is Q(n log n). 0
1. the input to problem A can be converted into an input suitable for problem
B, using r7i(n) elementary operations,
2. it is possible to convert the solution to problem B on the latter input
into a solution to problem A on the former input, using T3(n) elementary
operations, and
3. ri(n) + r 3 (n) = 7(n).
2
Stirling's approximation formula states that n! = 7 (n)fn (1 + 1 + o( )) where e
stands for the base of natural logarithms.
12 Chapter 1. Notions of complexity
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 rep-
resenting 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 terminol-
ogy 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 bi-
nary 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 sole purpose of this chapter is to present, as far as data structures are
concerned, the information necessary for a thorough understanding of the forth-
coming algorithms. In particular, the authors by no means claim to present a
comprehensive account of this topic, and the interested reader is urged to refer
to the references given in the bibliographical notes.
14 Chapter 2. Basic data structures
Em-- FE---
in the list, which is called the top of the stack: to stack an element means to
insert it as the last element of the list, and to pop consists of deleting the element
that was stacked the most recently. Stacks are therefore particularly suited to
process the elements of a set in the LIFO order, which stands for "last in, first
out."
In the case of a queue, all insertions occur at the end of the list, whereas all
deletions take place at the beginning of the list. Queues are therefore well suited
to process elements in the FIFO order, which stands for "first in, first out." This
is the normal order for a waiting line, or queue, hence the name given to this
data structure.
Stacks or queues can always be implemented as general lists. There are more
specific methods to implement these data structures but we will not expand on
them in this book.
We call a dictionaryany data structure that can perform queries, insertions and
deletions. If it supports searching for the minimum as well, we call it a priority
queue. If it supports all the operations detailed above, we call it an augmented
dictionary.
Priority queues and dictionaries can be implemented using lists or arrays. When
the universe is totally ordered, it is often more efficient to use balanced data
structures such as red-black trees, described below.
A branchof the tree is a path that stretches from the root to a leaf of the tree.
A tree is considered to be balanced if all its branches have approximately the
same length. This property, to be made precise below, ensures the efficiency of
the data structure but complicates the insertion and deletion operations. Indeed,
after each such operation, the structure must be rebalanced. There are several
kinds of balanced trees, such as AVL trees, 2-3 or 2-3-4 trees, or even red-
black trees. There are also many ways in which these variants can be used
to implement dictionaries and priority queues. All the performances of these
solutions are equivalent and optimal: if the set S stored in the data structure has
n elements, the data structure occupies O(n) space and any insertion, deletion, or
query takes O(log n) time. For instance, the next section describes how to achieve
these performances using red-black trees, and analyzes the corresponding cost of
these operations.
1. The paths from the root to all the leaves have the same number of black
arcs.
3. There cannot be two consecutive red arcs along a path from the root to a
leaf.
All the nodes have a level, which is the number of arcs on the path from the root
to that node, and a black level, which is the number of black arcs on that path.
The number of black arcs on a path from the root to a leaf is called the black
height of the tree, since it does not depend on the particular leaf.
It is easy to see that a red-black tree is approximately balanced: the longest
branch cannot have more than twice as many arcs as the shortest.
We propose to show how such a data structure can be used to implement a
dictionary on a finite set S drawn from a totally ordered universe U. The red-
black tree is used as a searching data structure: to each node corresponds a key
and two pointers towards its children. The keys attached to the leaves serve to
represent the elements of S. The keys attached to the internal nodes serve as a
guide for the searching operations. The key attached to an internal node must
be greater than or equal to all the keys stored in its left subtree-the subtree
rooted at its left child, and smaller than all the keys stored in its right subtree.
18 Chapter 2. Basic data structures
For instance, the key attached to an internal node can be systematically set to
the greatest of the keys stored in its left subtree. A left-hand depth-first traversal
of the tree visits all the nodes of the tree in the following order: the root first,
then recursively the nodes in the left subtree, and finally the nodes in the right
subtree. Such a traversal visits the leaves of the tree in the order of the elements
of S.
Along with the key and the pointers to its children, the information stored at
a node contains a special field to mark the color, either red or black, of the arc
linking this node to its parent. To simplify the exposition, the color of an arc is
often transferred to the node as well, and so we call a node black if it is linked
to its parent by a black arc, and red if it is linked to its parent by a red arc. By
convention, the root of the tree is always colored black. From now on, we denote
by the same letter N, 0, P, Q, R, S.... both the node and the key stored at that
node.
Storage
Queries
To find out whether or not an element S of the universe U belongs to the set
S, we need only follow a branch of the tree. At each internal node N, the next
node in the branch is identified using a comparison between N and the key S
that we are searching for. If S < N, the search goes through the left child of
N; if S > N the search goes instead through the right child of N. The search
always ends up at a leaf S' of the tree: the answer is that S is present if S' = S,
and that S is missing from S if S' = S. In the latter case, S' is the element
of S that immediately precedes or follows S according to the order on U. The
following theorem shows that, if there are n elements in S, such a search visits
only E(log n) nodes of the tree, and therefore runs in E(log n) time.
Lemma 2.2.1 If a red-black tree has n leaves, any path from the root to a leaf
has at least 2 log n and at most 2 log n arcs.
Proof. The easiest proof of this result is to refer to a different kind of tree, the
2-3-4 tree. A 2-3-4 tree is a tree whose nodes have either 2, 3, or 4 descendants,
and all the paths from the root to the leaves have the same length, which is the
height of the 2-3-4 tree. From a red-black tree, it is easy to make a 2-3-4 tree by
merging all the nodes that are linked through red arcs (see figure 2.2). The height
2.2. Balanced search trees 19
2.2.Balaced
tres earc 1
AQ
XQ
QR
Figure 2.2. The correspondence between red-black trees and 2-3-4 trees.
In this and the subsequent pictures, the black arcs of red-black trees are
represented in bold, the circles stand for internal nodes, rectangles for the
leaves, and triangles stand for arbitrary subtrees.
h of this 2-3-4 tree is exactly the same as the black height of the corresponding
red-black tree.
The red-black tree and its associated 2-3-4 tree have the same number of
leaves, n, and the height h of the 2-3-4 tree satisfies
2h <rn < 4h
From this, it follows that the number h of black arcs on any branch is at least
2 log n and at most log n. The total number of arcs on such a branch cannot be
less than h, nor can it be more than 2h. El
20 Chapter 2. Basic data structures
Insertions
~~> PA
left (resp. right) rotation if Q and R are both right (resp. left) children;
double right-left (resp. left-right) rotation if Q is a right child and R a left
child (resp. Q is a left child and R is a right child). Figure 2.4 shows only
a simple left rotation and a double right-left rotation. We leave it to the
reader to represent the symmetric rotations.
2. Should P have two red children, then the algorithm colors both children
black and colors P red instead (see figure 2.5), unless P is the root of the
tree in which case it is left black and nothing else is done. If the parent
of P is black or at the root of the tree, then the third constraint has been
restored, and the whole rebalancing task is over. If the parent of P is red,
then the default in the third rule has been carried up two levels towards
the root of the tree. Nodes R and Q are popped from the stack and the
next step takes over with node P, its parent, and its grandparent.
) A
) A
>1 Mo.
Figure 2.6. Red-black trees: deletions.
the third stage, only O(log n) nodes may need to be recolored, and only as many
(simple or double) rotations may need to be performed. Red-black trees therefore
allow a new element to be inserted in time O(logrn).
Deletions
Third stage. We rebalance the tree obtained by the removal in the second
stage. This operation is carried out in steps. At the current step, the tree contains
one and only one short node: this is a node X such that the black height of the
subtree rooted at X is one arc smaller than that of other subtrees rooted at the
same black level in the tree. In the first step, the only short node is S'. Let X be
the current short node, Q its parent, and R the other child of Q. Node X being
the only short node, R cannot be a leaf of the tree.
1. Should R be black with two red children, then rebalancing can be obtained
by performing the rotation depicted in figure 2.7, case 1.
2. Should R be black with both a black and a red child, rebalancing can be
obtained by the double rotation depicted in figure 2.7, case 2.
3. Should R be black with two black children, two cases may arise. If node Q,
the parent of X and R, is red, then the tree can be rebalanced by changing
the colors as shown in figure 2.7, case 3a: Q is recolored in black and R in
red. If Q is black, the tree cannot be rebalanced in a single step. Changing
the colors as shown in figure 2.7, case 3b, makes the parent of Q become
the short node, and the next step takes over with this node as the short
node.
(1)>
(2)
(3a)>
(3b)>
(4)>
set of these n numbers. The tree can be built in O(nlogn) time, uses O(n)
space, and the elements can be enumerated in order by performing a left-hand
depth-first traversal of the tree. The only operation on the numbers used in this
algorithm is comparison. Taking into account theorem 1.2.1, we have proved the
following:
Sometimes, the size of the underlying universe is just too big for this method
to be practical. Hashing methods can then be used as a replacement.
Perfect dynamic hashing is a method that stores the dictionary over a finite,
albeit huge, universe. In this method, random choices are made by the algorithm
during the execution of the insertion and deletion operations. Such algorithms
are called randomized below. The cost of these operations (insertions, deletions)
depends on the random choices made by the algorithm and can only be evaluated
on the average over all possible choices. Such an analysis is also said to be
randomized. Moreover, it is impossible to bound the cost of a single operation.
26 Chapter 2. Basic data structures
Finally, by combining both stratified trees and perfect dynamic hashing, one
may build a data structure that performs well on all the operations of an aug-
mented dictionary. Henceforth, this combination of data structures, a data struc-
ture in its own right, will be referred to as an augmented dictionary on a finite
universe. The theorem below summarizes its characteristics.
Table 2.1 summarizes further the performances of the different data structures
discussed here that may be used to implement a dictionary or a priority queue.
2.4 Exercises
Exercise 2.1 (Segment trees) Segment trees were created to deal with a collection of
intervals on the one-dimensional real line. Intervals may be created or deleted, provided
2.4. Exercises 27
that the endpoints belong to a set known in advance. The endpoints are sorted, and
thought of as the integers {1, . . . , n} via a one-to-one correspondence that preserves the
order. The associated segment tree is a balanced binary tree, each leaf of which represents
an elementary interval of the form [i, i + 1]. Each node of the tree therefore corresponds
to an interval which is the union of all the elementary intervals associated with the leaves
of the subtree rooted at that node. Intervals of this kind will be called standardintervals,
and we will speak of a node instead of its associated standard interval.
The intervals of the collection are stored at the nodes of the tree. An interval I is
stored in the structure at a few nodes of the tree: a node V stores I only if its associated
standard interval is contained in I, but the standard interval of the parent of V is not.
1. Let 1, resp. r, be the left, resp. right, endpoint of I. Let VI be the standard
elementary interval whose left endpoint is 1, and let Vr be the standard elementary
interval whose right endpoint is r. Let Vf be the smallest standard interval containing
both VI and Vr. The node Vf is the nearest common ancestor to both V1 and Vr, and it
is called the fork of I. Show that the nodes which are marked as storing I are precisely
the right children of the nodes on the path joining Vf to VI in the tree, together with
the left children of the nodes on the path joining Vf to Vr in the tree. Deduce from this
that the nodes that store I correspond to a partition of I into O(log n) standard disjoint
intervals, with at most two intervals at each level of the tree.
2. At each node, a secondary data structure accounts for the set of intervals stored
by that node. According to the application, the data structure may list the intervals or
simply maintain in a counter the number of these intervals. To add an interval to the
segment tree simply consists of adding it to each of the secondary data structures of the
nodes storing this interval, or incrementing the counter at these nodes. Deletions are
handled similarly. Assume that only a counter is maintained. Show that an insertion or
deletion can be performed in time O(log n). Show that the segment tree can be used to
count the number of intervals containing a given real number x, in time O(log n).
Exercise 2.2 (Range trees) Given a set of n points S in Ed, we wish to build a data
structure to efficiently answer queries of the following kind: count the number of points
inside an axis-oriented hyper-rectangle, or report them. One solution consists of building
a range tree, a data structure particularly suited to this kind of query, which we describe
now.
* The first level of the structure is a segment tree T1 (see exercise 2.1) built on
the first coordinates of the points in S, that is on the set {xi(P) : P e S}. For
each node V of T1 , we denote by Sd(V) the set of those points P of S whose first
coordinate x 1 (P) belongs to the standard interval of V. The set Sd- (V) is the
projection of Sd(V) onto Ed-1 parallel to the x1 -axis.
. If d > 2, every node V of T1 has a pointer towards a range tree for the set of points
Sd-l(V) in Edl.
1. We first assume that the queries ask for the number of points in S inside a given
hyper-rectangle Rd (the counting problem). Let q(S, Rd) be the time it takes to answer a
query on the hyper-rectangle Rd. Let V1 stand for the collection of all the nodes storing
the projection of Rd onto the x1 -axis, and Rd-, be the projection of Rd parallel to the
28 Chapter 2. Basic data structures
From this, show that the maximum amount of time that a query can take on a set of n
points in d dimensions is
Show that a query in the reporting case can be answered in 0 ((log n)d + k) time if k is
the number of points to be reported.
2. Show that the preprocessing space requirement and time are both 0 (n(log n)d).
Exercise 2.3 (Stratified tree) Let S be a subset of a finite, totally ordered universe
U. Let u be the number of elements of U, and without loss of generality assume that
u = 2 k. For convenience, we identify the set of possible keys with {0, 1, . .. , 2k - 1}. A
stratified tree ST(U, S) that implements an augmented dictionary on S is made up of:
* a doubly linked list which contains the elements of U. Each record in this list
has three pointers sub, super, and rep, and a boolean flag marker to identify the
elements of S.
* a representative R with two pointers to the maximal and minimal elements in S,
and a boolean flag to detect whether S is empty or not.
* stratified trees ST(Uj, Si) for the sets Si = Sn Ui and the universes Ui =
2 [k/21
i 2[k/2j + {O,1, . . ., 2Lk/2j - 1}, with i ranging from 0 to 2 fk/21 -1. Depending on
the parity of k, each sub-universe Ui contains \/6 or vfi elements of U.
* A stratified tree ST(U', 1?) for the set of representatives of ST(Ui, Si). The rep-
resentative Ri of ST(Ui, Si) is the element whose key equals i in the set U' =
{0,1,..., 2 rk/21-1}. Depending on the parity of k, the size of U' is u or /u.
The trees ST(Ui, Si) and the tree ST(U', %) are called the sub-structures of ST(U, S).
In turn, ST(U, S) is called a super-structureof those trees. Pointers sub and super keep
a link between a record in the list and the corresponding record in the list of the sub-
structure (resp. super-structure). The pointer rep points toward the representative of
the structure.
1. Show that the stratified tree ST(U, S) can be stored in space O(uloglogu), and
can be built for an empty set S in time 0(u log log u).
2. Show that each operation: insertion, deletion, location, minimum, predecessor,
successor, can be performed in time 0(log log u).
Exercise 2.4 (Stratified trees and segment trees) Let U be a totally ordered, fi-
nite universe with u = 2 k elements. Consider a complete and balanced binary tree C3T
whose leaves are associated with the elements of U. Consider further the set {0, 1 ... , k}
of levels of that tree, and build a segment tree T on this set. Show that you can do it
in such a way so that each sub-structure of the stratified tree built on the universe U
corresponds to a standard interval on T.
2.4. Exercises 29
Shamos [192]. Persistent data structures as described in exercise 2.7 are due to Sarnak
and Tarjan [196]. Several geometric applications of persistent trees will be given in the
exercises of chapter 3.
The perfect dynamic hashing method (see exercise 2.6) was developed by Dietzfel-
binger, Karlin, Mehihorn, auf der Heide, Rohnert, and Tarjan [84] and the augmented
dictionary on a finite universe is due to Mehlhorn and Nhher [165]. See also the book by
Mehlhorn [163] for an extended discussion on hashing.
Chapter 3
Deterministic methods
used in geometry
The goal of this and subsequent chapters is to introduce the algorithmic methods
that are used most frequently to solve geometric problems. Generally speaking,
computational geometry has recourse to all of the classical algorithmic techniques.
Readers examining all the algorithms described in this book from a methodolog-
ical point of view will distinguish essentially three methods: the incremental
method, the divide-and-conquer method, and the sweep method.
The incremental method is perhaps the method which is the most largely em-
phasized in the book. It is also the most natural method, since it consists of
processing the input to the problem one item at a time. The algorithm initiates
the process by solving the problem for a small subset of the input, then maintains
the solution to the problem as the remaining data are inserted one by one. In
some cases, the algorithm may initially sort the input, in order to take advantage
of the fact that the data are sorted. In other cases, the order in which the data are
processed is indifferent, sometimes even deliberately random. In the latter case,
we are dealing with the randomized incremental method, which will be stated
and analyzed at length in chapter 5. We therefore will not expand further on the
incremental method in this chapter.
The divide-and-conquermethod is one of the oldest methods for the design of
algorithms, and its use goes well beyond geometry. In computational geometry,
this method leads to very efficient algorithms for certain problems. In this book
for instance, such algorithms are developed to compute the convex hull of a set of
n points in 2 or 3 dimensions (chapter 8), the lower envelope of a set of functions
(chapter 16), a cell in an arrangement of segments in the plane (exercise 15.9), or
even the Voronoi diagram of n points in the plane (exercise 19.1). In this chapter,
the principles underlying the method are outlined in section 3.1, and the method
is illustrated by an algorithm that has nothing to do with geometry: sorting a
sequence of real numbers using merging (the so-called merge-sort algorithm).
3. 1. The divide-and-conquer method 33
Dividing. Divide the problem into simpler subproblems. Such problems have
a smaller input size, that is, if the input data are elementary, the input to
these problems is made up of some but not all of the input data.
Solving. Separately solve all the subproblems. Usually, the subproblems are
solved by applying the same algorithm recursively.
Merging. Merge the subproblem solutions to form the solution to the original
problem.
The performance of the method depends on the complexities of the divide and
merge steps, as well as on the size and number of the subproblems. Assume that
each problem of size n is divided into p subproblems of size n/q, where p and q
are some integer constants and n is a power of q. If the divide and merge steps
perform O(f(n)) elementary operations altogether in the worst case, then the
time complexity t(n) of the whole algorithm satisfies the recurrence
Usually, the recursion stops when the problem size is small enough, for instance
smaller than some constant no. Then k = [logq(n/no)] is the depth of the
recursive calls (logq stands for the logarithm in base q), and the recurrence solves
to
t(n) =0 ( +Epf
k-1 3
In this expression, the first term corresponds to the time needed to solve all
the elementary problems generated by the algorithm. The second term reflects
the time complexity of all the merge and divide steps taken together. If f is a
multiplicative function, i.e. such that f(xy) = f(x)f(y) (which in particular is
true when f(n) = n' for some constant a), then t(n) satisfies
t(n) = O )
* If p= f (q), then t(n) = 0 (nlogP/ logqlog n), and further if f (n) = n", then
t(n) = O(n log n).
* If p < f (q), then t(n) = 0 (n1og f (q)/1ogq), and further if f (n) n', then
t(n) = 0 (n').
1. the information stored in Y is related to the position of the sweep line, and
changes when this line moves,
The event queue X stores the sequence of events yet to be processed. This
sequence can be entirely known at the beginning of the algorithm, or discovered
on line, i. e. as the algorithm processes the events. The sweep algorithm initializes
the structure Y for the leftmost position x = -x of the sweep line, and the
sequence X with whatever events are known from the start (in increasing order of
their abscissae). Each event is processed in turn, and Y is updated. Occasionally,
new events will be detected and inserted in the queue X, or, on the contrary, some
events present in the queue X will no longer have to be processed and will be
removed. When the event is processed, the queue X gives access to the next
event to be processed.
When all the events are known at the start of the algorithm, the queue X may
be implemented with a mere simply linked list. However, when some events are
to be known only on line, the event queue must handle not only the minimum
operation, but also queries, insertions, and sometimes even deletions: it is a
priority queue (see chapter 2).
3.2. The sweep method 37
The choice of the data structure Y depends on the nature of the problem and
may be handled through multiple components. More often than not, each of these
components must handle a totally ordered set of objects, and the corresponding
operations: query, insertion, deletion, sometimes even predecessor or successor.
The appropriate choice is that of a dictionary, or an augmented dictionary (see
chapter 2).
The sweep method can sometimes be useful in three or more dimensions. The
generalization consists of sweeping the space Ed by a hyperplane perpendicular
to the xd-axis. The state of the sweep is stored in a data structure Y associated
with the sweep hyperplane, and the set of events is the set of positions of the
sweep hyperplane at which the state of the sweep Y changes. The data structure
Y often maintains a representation of a (d - 1)-dimensional object contained in
the sweep hyperplane. The sweep method in higher dimensions, therefore, often
consists of replacing a d-dimensional problem by a sequence of (d- 1)-dimensional
problems.
Figure 3.1. Computing the intersections of a set of line segments using the sweep method.
which intersect the vertical sweep line A. Such segments are said to be active at
the current position of the sweep line. The structure Y stores the active segments
in the order of the ordinates of their intersection point with the line A. The order
of the sequence, or the sequence itself, is modified only when the line sweeps over
the endpoint of a segment or over an intersection point.
1. If A sweeps over the left endpoint of a line segment S (that is to say, the
endpoint with the smaller abscissa), this segment S is added to the structure
Y.
2. If A sweeps over the right endpoint of a line segment S (that is to say, the
endpoint with the greater abscissa), this segment S is removed from the
structure Y.
3. If A sweeps over the intersection of two segments S and S', these segments
S and S' switch their order in the sequence stored in Y.
The set of events therefore includes the sweep line passing over the endpoints
of the segments of S, and over the intersections. The abscissae of the endpoints
are known as part of the input, and we wish to compute the abscissae of the
intersection points. A prospective intersection point I is known when two active
segments become consecutive in the sequence stored in Y. The corresponding
event is then stored in the event queue X. The state of the event queue is shown
for a particular position of A on figure 3.1: each event is marked by a point on
the x-axis.
At the beginning of the algorithm, the queue X stores the sequence of endpoints
of the segments in S ordered by their abscissae. The data structure y is empty.
., I
3.2. The sweep method 39
Case 1. the event is associated with the left endpoint of a segment S. This
segment is then inserted into Y. Let pred(S) and succ(S) be the active
segments which respectively precede and follow S in Y. If pred(S) and S
(resp. S and succ(S)) intersect, their intersection point is inserted into X.
Case 2. the event is associated with the right endpoint of a segment S. This seg-
ment is therefore queried and removed in the structure Y. Let pred(S) and
succ(S) be the active segments which respectively preceded and followed
S in Y. If pred(S) and succ(S) intersect in a point beyond the current
position of the sweep line, this intersection point is queried in the structure
X and the corresponding event is inserted there if it was not found.
Case 3. the event is associated with an intersection point of two segments S
and S'. This intersection point is reported, and the segments S and S' are
exchanged in Y. Assuming S is the predecessor of S' after the exchange,
S and its predecessor pred(S) are tested for intersection. In the case of
a positive answer, if the abscissa of their intersection is greater than the
current position of the sweep line, this point is queried in the structure X
and the corresponding event is inserted there if it was not found. The same
operation is performed for S' and its successor succ(S').
To prove the correctness of this algorithm, it suffices to notice that every in-
tersecting pair becomes a pair of active consecutive segments in Y, when the
abscissa of the sweep line immediately precedes that of their intersection point.
This pair is always tested for intersection at this point, if not before, therefore
the corresponding intersection point is always detected and inserted into X, to
be reported later.
It remains to see how to implement the structures Y and X. The structure Y
contains at most n segments at any time, and must handle queries, insertions,
deletions, and predecessor and successor queries: it is an augmented dictionary
(see section 2.1). If this dictionary is implemented by a balanced tree, each
query, insertion, and deletion can be performed in time O(log n), and finding
predecessors and successors takes constant time.
The event queue X will contain at most O(n + a) events, if a stands for the
number of intersecting pairs among the segments in S. This structure must
handle queries, insertions, deletions, and finding the minimum: it is a priority
queue (see section 2.1). Again, a balanced binary tree will perform each of these
operations in O(log(n + a)) = O(log n) time.
The global analysis of the algorithm is now immediate. The initial step that
sorts all the 2n endpoints according to their abscissae takes time O(n log n). The
40 Chapter 3. Deterministic methods used in geometry
structure X is initialized and built within the same time bound. Next, each of the
2n + a events is processed in turn. Each event requires only a constant number
of operations to be performed on the data structures X and Y and is therefore
handled in time 0(log n). Overall, the algorithm has a running time complexity
of 0((n + a) log n) and requires storage 0(n + a).
The algorithm can be slightly modified to avoid using more than 0(n) storage.
It suffices, while processing any of cases 1 to 3, to remove from the event queue
any event associated with two active but non-consecutive segments. In this way,
the queue X contains only 0(n) events at any time, and yet the event immediately
following the current position of the sweep line is always present in X. Indeed,
this event is associated either with an endpoint of a segment in S, or with two
intersecting segments which therefore must be consecutive in X. Some events
can be inserted into and deleted from X several times before they are processed,
but this does not change the running time complexity of the algorithm, as the
above scheme can be carried out using only a constant number of operations in
the data structures X and Y at each step.
Theorem 3.2.1 The intersection points of a set of segments in the plane can be
computed using the sweep method. If the set of n segments in general position
has a intersecting pairs, the resulting algorithm runs in 0((n+a)logn) time and
0(n) space.
I I I I I i I
I I I I
I I I
I IPI
I I
I I I I
I I I I I I I I I I I I
i I I I I i I I I I I I
I I
I I
I I I
(a) (b)
Figure 3.2. (a)The vertical decomposition Dec(S) of a set of line segments S in the plane.
(b) Its simplified decomposition Dec, (S).
are vertical. Some degenerate ones are triangular (with only one vertical side),
or semi-infinite (bounded at top or bottom by a segment portion with two semi-
infinite walls on both sides), or doubly infinite (a slab bounded by two vertical
lines on either side), or even a half-plane (bounded by only one vertical line).
It is easy to modify the above algorithm to compute not only the intersection
points, but also the vertical decomposition of the given set of line segments.
3.4 Exercises
Exercise 3.1 (Union, intersection of polygonal regions) By a polygonal region,
we mean a connected area of the plane bounded by one or more disjoint polygons (a
polygonal region may not always be simply connected, and may have holes). Show how
to build the union or intersection of k polygonal regions using a sweep algorithm. Show
that if the total complexity of the regions (the number of sides of all the polygons that
bound it) is n, and the number of intersecting pairs between all the sides of all the
polygonal regions is a, the algorithm will run in 0((n + a) logn) time.
Exercise 3.2 (Detecting intersection) Show that to test whether any two segments
in a set S intersect requires at least time £Q(n log n). Show that the sweep algorithm can
be modified to perform this test in time 0 (n log n).
Exercise 3.3 (Computing the intersection of curved arcs) Modify the sweep al-
gorithm described in subsection 3.2.2 so as to report all the intersection points in a family
of curved arcs. The arcs may or may not be finite. We further assume that any two arcs
have only a bounded number of intersection points, which may be computed in constant
time.
Hint: Do not forget to handle the events where the arcs have a vertical tangent.
Exercise 3.4 (Arbitrary sets of segments) Sketch the changes to be made to the
sweep algorithm so that it still works on arbitrary sets of segments, getting rid of the
assumptions about general position. The algorithm should run in time O((n + a) log n)
where a is the number of intersecting pairs.
Exercise 3.5 (Location in a planar map) A planar map of size n is a planar subdi-
vision of the plane E2 induced by a set of n segments which may intersect only at their
endpoints. To locate a point in the planar map is to report the region of the subdivision
that this point lies in. Show that a data structure may be built in time 0(n log n) and
space 0(n) to support location queries in time O(log n).
Hint: The vertical lines passing through the endpoints of the segment divide the plane
into vertical strips ordered by increasing abscissae. The segments that intersect a strip
form a totally ordered sequence inside this strip, and two sequences corresponding to two
consecutive strips differ only in a constant number of positions. A sweep algorithm may
use persistent structures (see exercise 2.7) to build the sequence of such lists.
Hint: The algorithm proceeds by using the divide-and-conquer method. Each merge
step computes the union of two polygonal regions and can be performed using the sweep
method. Each intersection between the edges of these regions is a vertex of their union,
therefore there can be at most a linear number of such intersections.
44 Chapter 3. Deterministic methods used in geometry
Exercise 3.7 (Selecting the k-th element) Let S be a set of n elements, all belong-
ing to a totally ordered universe. A k-th element of S is any element S of S such that
there are at most k - 1 elements in S strictly smaller than S and at least k elements
smaller than or equal to S. Show that it is possible to avoid sorting S yet still compute
a k-th element in time 0(n).
To analyze the complexity of such an algorithm, observe that IS1 < 3n and that
IS21 < 3n. Then, if n > 50, show that the time complexity of the algorithm satisfies the
recurrence
t(n) > t(n/5) + t(3n/4) + cn,
where c is a constant. Show that this recurrence solves to t(n) = 0(n).
Hint: One may use a sweep algorithm that maintains the intersection of the union of the
rectangles with the sweep line, using a segment tree (see exercise 2.1). The perimeter or
the area can be obtained in time O(n log n), and the complete description of the boundary
in time 0((n + k) log n) if this boundary has k edges.
pairs, the induced vertical decomposition in optimal O(n log n + a) time. In degenerate
cases, the number b of intersection points can be much lower than a, and Burnikel,
Mehlhorn and Schirra [40] have shown that it still is possible to compute the vertical
decomposition in O(n log n + b) time. In chapter 5, we describe a randomized algorithm
(that is, an algorithm which makes random choices during its execution) which runs in
time 0 (n log n + a) on the average over all possible random choices it can make.
Persistent data structures and the idea of using them for locating a point in a planar
map (as in exercise 3.5) are due to Sarnak and Tarjan [196]. Segment trees (see exer-
cise 2.1) are especially suitable for solving many problems on rectangles. The solution
to exercise 3.8 can be found in the book by Preparata and Shamos [192].
Chapter 4
Random sampling
4.1 Definitions
4.1.1 Objects, regions, and conflicts
In the framework presented here, any geometric problem can be formulated in
terms of objects, regions, and conflicts between these objects and regions.
Objects are elements of a universe 0, usually infinite. The input to some
problem will be a set S of objects of 0. The objects under consideration are
typically subsets of the Euclidean space Ed such as points, line segments, lines,
half-planes, hyperplanes, half-spaces, etc.
A region is a member of a set F of regions. Each region is associated with two
4.1. Definitions 47
sets of objects: those that determine it, and those that conflict with it.
The set of objects that determine a region is a finite subset of (9, of cardinality
bounded by some constant b. The constant b depends on the nature of the
problem, but not on the actual instance nor on its size. This restriction is required
for all the probabilistic theorems to be expressed within the framework.
The set of objects that conflict with a given region is usually infinite and is
called the domain of influence of the region.
Let S be a set of objects. A region F of F is defined over S if the set of objects
that determines it is contained in S. A region F is said to be without conflict
over S if its domain of influence contains no member of S, and otherwise is said
to have j conflicts over S if its domain of influence contains j objects of S.
For each geometric application, the notions of objects, regions, and conflicts
are defined in such a way that the problem is equivalent to finding all the regions
defined and without conflict over S.
Let us immediately discuss a concrete example. Let S be a set of n points
in the d-dimensional Euclidean space Ed. The convex hull of S is the smallest
convex set containing S; suppose we wish to compute it. Assume the points are in
general position'. The convex hull conv(S) is a polytope whose special properties
will be studied further in chapter 7. For now, it suffices to notice that, in order
to compute the convex hull, we have to find all the subsets of d points in S such
that one of the half-spaces bounded by the hyperplane passing through these d
points contains no other point that belong to S (see figure 4.1). In this example,
the objects are points, and the regions are open half-spaces in Ed. Every set of
d points determines two regions: the open half-spaces whose boundaries are the
hyperplane passing through these points. A point is in conflict with a half-space
if it lies inside it. To find the convex hull, one must find all the regions determined
by points of S and without conflict over S.
The preceding definitions call for a few comments.
Remark 1. A region is determined by a finite and bounded number of objects
and this restriction is the only fundamental condition that objects, regions, and
conflicts must satisfy. Nevertheless, we do not demand that all the regions be
determined by exactly the same number of objects. In the case of the convex hull
of n points in Ed, all the regions are determined by exactly d points. One may
envision other settings (as in the case of the vertical decomposition of a set a line
segments in the plane, discussed in subsection 5.2.2), where the regions can be
determined by a variable number i of objects, provided that 1 < i < b for some
constant b.
Remark 2. A region does not conflict with the objects that determine it. This
'A set of points is in general position if every subset of k + 1 < d + 1 points is affinely
independent, or in other words if it generates an affine subspace of dimension k.
48 Chapter 4. Random sampling
j.*. . . *.
* 0
simple convention greatly simplifies the statements and proofs of the theorems
below, and does not modify their meaning. In the case of the convex hull, this
can be easily achieved by defining the domain of influence of a region as an open
half-space.
Remark 3. A region is characterized by two sets of objects: the set of objects
that determine it, and the set of objects that conflict with it. Regions determined
by different objects will be considered as different, even if they share the same
domain of influence. In this context, a set S of objects is in general position
precisely if any two regions determined by different subsets of S have distinct
domains of influence.
Remark 4. A set of b or fewer objects may determine one, or more, or zero
regions. Usually, the number of regions determined by a given set of (less than b)
objects is bounded by a constant. For instance, in the case of convex hulls, every
subset of d points determines exactly two regions. In this case, the total number
of regions defined over a set of cardinality n is 0(nb).
If S is a finite set of objects, say with n elements, we denote by J'-(S) the set
of regions defined over S and, for each integer j in [0, n], we denote by Fj(S)
the set of all regions defined over S that have j conflicts over S. In particular,
.Fo(S) is the set of those regions that are defined over S and without conflict over
S. Furthermore, we denote by ;F-k(S) the subset of regions defined over S that
have at most k conflicts over S.
When the regions are determined by a variable number i of objects (I < i < b),
the preceding notation may be refined to denote by Ej(S), P<k(S)7 Yik(S), the
subsets of those regions defined by exactly i objects of S, with (respectively)
exactly, at most, at least, k conflicts with the objects of S.
4. 1. Definitions 49
* F-
*i
From now on, we are primarily interested in the regions defined over a random
sample 7 from S. Generally speaking, if g(1R) is a function of the sample 7,
we denote by g(r, S) the expected value of g(7Z) for a random r-sample of S. In
particular, the following functions are defined: We denote by fj(7?.) the number
of regions defined and with j conflicts over a subset R of S (in mathematical
notation, fj(1?) = lFj(1?)I). Following our convention, fM(r,S) denotes the ex-
pected number of regions defined and with j conflicts over a random r-sample of
S. Likewise, fJ.(7?) stands for the number of regions defined by i objects of 7?
and with j conflicts over 7R (in mathematical notation, fj(1Z) = ~j(R?) I). Then
fjt(r, S) is the expected number of such regions for a random r-sample of S.
50 Chapter 4. Random sampling
In this section, we prove two probabilistic theorems, the sampling theorem and
the moment theorem. These two theorems lay the foundations for our analysis
of randomized algorithms as described in chapters 5 and 6. The reader mostly
interested in the algorithmic applications of these theorems may skip this section
in a first reading. In order to understand the results, it would be enough to
memorize the definition of a moment, to look up lemma 4.2.5, and to admit
corollary 4.2.7.
The probabilistic theorems below are based on certain combinatorial properties
of the geometric objects. The probabilities involved concern mainly random
samples from the input data. In particular, these theorems do not make any
assumptions on the statistical distribution of the input data. The theorems are
stated in the formal framework introduced in the preceding section. Nevertheless,
to shape the intuition of the reader, we start by stating them explicitly for the
specific problem of computing the convex hull of a set of points in the plane.
Let S be a set of n points in the plane, assumed to be in general position,
let k be an integer smaller than n and let 7? be a random sample of S of size
r = Ln/k]. The sampling theorem links the number of half-spaces defined over
S and containing at most k points of S, with the expected number of half-spaces
defined and without conflict over 7Z, which is precisely the number of edges of
the convex hull conv(7Z). Let A and B be points of S. Segment AB is an edge of
the convex hull conv(IZ) if and only if A and B are points of 7? and also one the
half-planes HZB and HXB bounded by the line AB does not contain any points
of 7R. The sampling theorem relies on the fact that the segment AB joining two
points of S is an edge of the convex hull conv(IZ) with a probability that increases
as the smallest number of points in either H+B or HiB decreases.
The moment theorem concerns the number of points in S and in its sample 1?
that belong to some half-plane. If the size of 1Z is large enough, the sample is
representative of the whole set, and the number of points of 7? in a half-plane is
roughly the number of points of S in this half-plane scaled by the appropriate
factor r/n.
In fact, the moment theorem is a little more restrictive and concerns only
those half-planes defined and without conflict over the sample. Any edge E of
conv(7Z) corresponds to a region defined and without conflict over 7Z: the half-
plane H-(E) bounded by the line supporting E that contains no point of R?.
The first moment of R relative to S, or moment of order 1, is defined to be the
sum, over all edges E of the convex hull conv(7Z), of the number of points of S
lying inside H- (E). In other words, the moment of order 1 of 7Z with respect to
S counts each point of S \ 7? with a multiplicity equal to the number of edges
of conv(7R) whose supporting lines separate it from conv(7?) itself. Figure 4.3
4.2. Probabilistictheorems 51
indicates the multiplicity of each point, and the first-order moment of the sample
is 16.
The moment theorem shows that, if the size of the sample is big enough, the
expected moment of order 1 is at most n - r.
The sampling theorem yields an upper bound on the number of regions defined
and with at most k conflicts over a set S of n elements. This bound depends
on the expected number of regions defined and without conflict over a random
Ln/kJ-sample of S. The proof of this theorem relies on the simple idea that,
the fewer objects in conflict with a region, the more likely this region is to have
no conflict with a random sample 1R of S. The proof uses the two fundamental
lemmas below.
Lemma 4.2.1 Let S be a set of n objects and F a region in conflict with j objects
of S and determined by i objects of S. If 7? is a r-sample of S, the probability
P3 ,k(r) that F be a region defined and with k conflicts over 7? is
pi k(r) = (
V k
r
r -i-j
pi (r)iJ
n-oin--j
fk(r, S) = , P3(S) I kJ r- kJ
j=o ( )
Proof. The expected number of regions in the set rk(IZ) is the sum, over all the
regions determined by i objects of S, of the probability that this region belongs
to the set P7k(7Z). This probability is given by the lemma 4.2.1 above. 0
Proof. For each i, 1 < i < b, we shall prove the following inequality bounding
the number of regions determined by i objects:
Then the theorem can be easily proved by summing over all the values of i between
1 and b.
4.2. Probabilistictheorems 53
n-i (nij)(nik
( n-i-k) 1
r-i > 1
n A 4(b + 1)iki
(r)
Indeed,
(( r-i
n)
J r!
(r -i)!
(n-i)! (n-r)! (n-i-k)!
n! (n-r-k)! (n - i)!
rJ
We compute
(n-r)! (n-i-k)! > (n-r-k+1 k
(n-r-k)! (n-i)! - in-i-k+1J
> (n-n/k-k+1)k
- ~~ nk - J
> (1 - l/k)k
> 1/4 (if 2 < k),
and
r! (n -i)! dr-l jjjtr+l-l
(r-i)!
- n! 1=0
n-I - 1=1
n
fn/kl > b)
> ;( nb > (1n)
Remark 1. The sampling theorem deals with the numbers I.F<k(S)I of regions
with at most k conflicts, for values of k between 2 and b
For the case of regions without or with at most one conflict, however, it is
possible to prove the following bound
F I(S)I
I-Fo(S)I I< < In 2(S)| < 4(b+ 1)2 bfo(Ln/21 ,S),
valid whenever n > 2(b + 1).
Moreover, for values of k close to n, there is always the trivial bound
IY<k(S)I < I-F(S)l = O(nb)
if, as in remark 4 of subsection 4.1.1, we suppose that each subset of size at most
b determines at most q regions, for a constant number q that depends on the
interpretation of objects and regions.
Remark 2. The sampling theorem yields a deterministic combinatorial result
when an upper bound on fo( [n/k , S) can be derived. For instance, in chapter 14,
we will use an upper bound on the number of faces of a d-dimensional polytope
to yield, via the sampling theorem, an upper bound on the number of faces at
level at most k in an arrangement of hyperplanes.
The following corollary is very useful for analyzing the average performance of
randomized algorithms. It shows that the expected number of regions defined and
with one or two conflicts over a random r-sample of a set S is of the same order
of magnitude as the expected number of regions defined and without conflict over
such a sample.
Corollary 4.2.4 Let S be a set of n objects, with n > 2(b + 1). For each integer
r such that n > r > 2(b + 1), we have
fl (r, S) < 3fo( Lr/2j, S)
f 2 (r,S) < /fo(Lr/2J S)
where fj (r, S) is the expected number of regions defined and with j conflicts over
a random r-sample of S, and 3 is the real constant
/3 = 4(b + 1)b2b.
Proof. Let 7t be a subset of S of size r, such that 2(b + 1) < r. Applied to 7?,
remark 1 following theorem 4.2.3 yields
.F1(1Z)I < 4(b+ 1)b 2 bfo(Lr/2J ,1?).
The first inequality is obtained by taking expectations on the two members of
this equation. Indeed, fo ( Lr/2J , 7) is the expected number of regions defined and
without conflict over a random Lr/2]-sample of 7?, and the expectation of this
expected number when 1R itself is a random r-sample of S is simply fo( [r/2J , S).
The second inequality can be proved in much the same way. D
4.2. Probabilistictheorems 55
Proof. Recall that p (r) stands for the probability that a given region F of
Yj (S) be defined and without conflict over a random r-sample of S, whence
mk(r, S) = b ni ( j )p.(r).
i=1 i=O FEFti(S)
Proof. According to the previous lemma 4.2.5, and to lemma 4.2.1 which gives
the expression for the probability p1 (r), we have
b n-iji
mk(r,S) = b S)
(t j (n)
(Ik n)
t-
- (n) - (n-j-r)! (r-i)!
IP3S)
(
) (i- ) (
(n
)
k n-
rA i- k
nA
rJ
is nothing else but the probability A(r)
Pk that a region F of PFJ(S) belong to
.k (7?), whence
Corollary 4.2.7 Let S be a set of n objects. There exists a real constant -y and
an integer ro, both independent of n, such that for each n > r > ro,
where mk(r, S) is the expected number of the k-th moment of a random r-sample
of S, and fo(r, S) is the expected number of regions defined and without conflict
over a random r-sample of S.
and the upper bound is a consequence of corollary 4.2.4. The second inequality
can be proved very much the same way. E
4.3 Exercises
Exercise 4.1 (Backward analysis) In this exercise, regions are determined by at most
b objects of a set S. Let fi (r,S) be the expected number of regions defined and without
conflict over a random r-sample of S. Corollary 4.2.4 to the sampling theorem proves that
fi (r, S) = O(fo (r, S)). Backward analysis can be used to prove this without invoking the
sampling theorem.
Let 7? be a subset of S of cardinality r, and Jo (r -1, ?) the expected number of regions
defined and without conflict over a random sample of 1 of size r - 1. Show that
Hint: Backward analysis consists in observing that a random (r - 1)-sample 7?' of 1Z can
be obtained by removing one random object from R. Any region in Fo(7?') is defined
over RZ and belongs either to Fo (R) or to Fl (7). A region F that belongs to Fo (7)
determined by i objects is a region of Fo(7?') if the removed object is not one of the i
objects that determine F; this happens with probability r A region F that belongs to
FF1 (7) is a region of Fo (7') if the removed object is precisely the one that was removed
from 7?, which happens with probability 1. To show that fi(r,S) = O(fo(r,S)), it
suffices to take expectations in equation 4.2 over all r-samples of S and to assume that
fo(r, S) is a non-decreasing function of r.
Exercise 4.2 (The moment theorem, using backward analysis) Let R be a ran-
dom r-sample of a set S of n objects, and 0 a random object of S \ R?. Show that the
expected number of regions defined and without conflict over 1Z but conflicting with 0
is 0 ( $ fl(r + 1,S)). From this, show that the expected value ml(r,S) of the moment
of order 1 with respect to S of a random r-sample is O(n~r fl(r + 1,S)). From this,
deduce an alternative proof of the moment theorem by using the result of the previous
exercise or corollary 4.2.4 to the sampling theorem.
Hint: Note that 7? U {O} is a random (r + 1)-sample of S and that a region of Fo(7?)
that conflicts with 0 is a region of Fl (1Z U {0}) that conflicts with 0.
Exercise 4.3 (An extension of the moment theorem) A function w is called con-
vex if it satisfies, for all x, y in R and all a in [0, 1],
Wk(Z) = E (w(IS(F)I))
FE.FO()
where To(RZ) is the set of regions defined and without conflict over 7R and IS(F)l is the
number of objects in S that conflict with F. Let wk (r, S) stand for the expected value
of Wk(Z) for a random r-sample of S. Show that
wkr,) (n -r -k)! (r -b -k)! fk(r, S)\
Wk(r, S)<fo(r,S) w( (n - r)! (r - b)! fo(r, S)
Exercise 4.4 (Non-local subset of regions) We still work with the framework of ob-
jects, regions, and conflicts, each region being determined by at most b objects. In this
exercise, we are mostly interested, for a subset 1Z of objects in S, in a subset g0 (1?) of
regions defined and without conflict over R. The definition of g0 (Rz) is not necessarily
local, however: a region F of Fo (7) belongs to go (1) depending on all the elements of
7, not only those in conflict with F or that determine F. Nevertheless, suppose that the
subsets of the form g0 (1R) satisfy the following property: If F is a region of g0 (7Z), 7?'
a subset of 7?, and if 7t' contains the elements that determine F, then F is a region of
E IS(F) Ik
FE 5 (7)
4
wk(r,S) = o ( go(rS))
where go(r, S) is the expected number of regions in go(1R) for a random r-sample of S.
Hint: 1. Let p(r, F) be the probability that F be a region of go0(R) for a random r-sample
1 of S. Show that, for all t < r <n,
nS(F)- p(r,F).
4.3. Exercises 59
r2b 2,)Sr + I
p(ri,F) + E -p(r,F) >p(rF).
rI+1 rl
and that
Wk (r, S) < 'Yk go (r, S),
rk
where -y and -Yk are constants depending only on k.
Exercise 4.5 (Tail estimates) Let b be the maximum number of objects that deter-
mine a single region. Suppose again that a set of at most b objects determine at most
q regions, q being a constant, or that the number of regions determined by a set S of n
objects is 0 (nrb).
1. Let S be a set of n objects and R a random r-sample of S. Let a be a real constant
in ]0, 1[. Let 7ro(a, r) denote the probability over all samples 7? that some region defined
and without conflict over R have at least Fan] conflicts with S. Show that, for r big
enough,
tro(a, r) = 0 (r(1- n)r).
2. Show that for any constant A > b, the probability 7ro(A log r/r, r) that some region
F, defined and without conflict over X, have at least An log r/r conflicts with S decreases
to 0 as r increases.
Then show that, if a(r) = Alog r/r and m(r) = log r/ log log r,
lii
l r -0 (a ()
m(r) r)) = 0.
Exercise 4.7 (An upper bound on fo(S)) Consider the set F(S) of regions defined
over a set S, each region being determined by at most b objects. Let fj (S) be the number
of regions defined and having j conflicts with S, and fo(n) be the maximum of fo(S) over
all sets S of n objects. Suppose that there is a relation between the number of regions
defined and without conflict over S on one hand, and the number of regions defined over
S and conflicting with one element of S on the other. Suppose further that this relation
is of the type
cfo(S) < f1 (S) + d(n) (4.3)
where c is an integer constant and d(n) a known function of n. Let t = b -c. Show then
that
fo(n) = ( 0+) )
In particular,
Hint: Combining equation 4.2, written for a random (n-1)-sample of S, and equation 4.3
yields
n-b+
n__
cfo(S) = n-foS
n
+bfo
n
n -b 1
< -fo(S) +-(fi(S) + d(n))
n n
1
< fo(n- 1,S) + -d(n).
n
Hint: Each vertex of the union belongs to a bounded number of faces of the union. Hence
it suffices to bound the number of vertices of the union to bound the total complexity.
The proof works by induction on d. The proof is trivial in dimension 1, and easy in
dimension 2.
In dimension d, each cube has 2d pairwise parallel facets. Let us denote by Fjt(C)
the facet of the cube C that is perpendicular to the xi-axis with maximal j-coordinate,
and by Fj- (C) the facet of the cube C that is perpendicular to the xj-axis with minimal
4.3. Exercises 61
j-coordinate. Let C be a set of axis-parallel cubes in Ed, and denote by U(C) the union of
these cubes and A(C) their arrangement, that is, the decomposition of Ed induced by the
cubes (see part IV for an introduction to arrangements). Each vertex of U(C) or of A(C)
is at the intersection of d facets of cubes, one perpendicular to each axis direction. Such
a vertex P is denoted by (Ci', C22,..., Cd") if at the intersection of facets F'j (Cj), for
=1,.. , d and ej = + or-. The vertex P is called outer if it belongs to a (d - 2)-face
of one of the cubes (then not all the cubes Cj are distinct). It is called an inner vertex if
it is at the intersection of d facets of pairwise distinct cubes. A vertex of A(C) is at level
k if it belongs to the interior of k cubes of C. The vertices of the union are precisely the
vertices at level 0 in the arrangement A(C). Let Wk (C) be the number of inner vertices of
A(C) at level k, and Vk(C) be the number of outer vertices at level k, and vk(n, d) (resp.
Wk(n, d)) the maximum of Vk(C) (resp. of 'Wk(C)) over all possible sets C of n axis-parallel
hypercubes in Ed.
1. The maximum number vo(n,d) of outer vertices of the union is 0(nrd/2l) (and
0(nLd/2]) when the cubes have same size). Indeed, any outer vertex of U(C) belongs to
a (d - 2)-face H of one of the cubes in C and is a vertex (either outer or inner) of the
union of all (d - 2)-cubes C n aff(H), where aff(H) is the affine hull of H. Consequently,
vo (n, d) < 2nd(d - 1)(bo(n -1, d -2) + woo(n - 1,d- 2)),
where 6O(n - 1, d - 2) and bo(n - 1, d -2) respectively stand for the maximum numbers
of outer or inner vertices in the union of n - 1 cubes in a (d - 2)-dimensional space lying
inside a given (d - 2)-cube.
2. Applying the sampling theorem (theorem 4.2.3) and its corollary 4.2.4, we derive a
similar bound on the maximum number v, (n, d) of outer vertices at level 1.
3. To count the number of inner vertices, we use the following charging scheme. For
each vertex P = (C11 2, ,Cdd) of U(C), and each direction j = 1,.. .d, slide along
.C2
the edge of A(C) that lies inside the cube Cj (this edge is nij FjiE (Ci)) until the other
vertex P' of this edge is reached.
If P' belongs to the facet F7Ej (Cj) of cube Cj, we do not charge anything. This case
cannot happen unless the cubes have different side lengths and Cj is the smallest of the
cubes intersecting at P.
If P' belongs to a (d - 2)-face of one of the cubes Ci (i 34 j) intersecting at P, P' is an
outer vertex at level 1, and is charged one unit for P. Note that P' cannot be charged
more than twice for this situation.
If P' belongs to another cube C' distinct from all the Ci intersecting at P, then P' is
an inner vertex at level 1, and is charged one unit for P. Any inner vertex P' of this type
may be charged up to d times for this situation. However, when it is charged more than
once, say m times, we may redistribute the extra m - 1 charges on the outer vertices at
level 0 or 1, and these vertices will only be charged once in this fashion.
In the case of cubes with different sizes, the induction is
(d - 1)wo(C) < wi(C) + 3v 1(C) + vo(C).
In the case of cubes with identical sizes, we obtain
dwo(C) < wi(C) + 3v1 (C) + vo(C).
It suffices to apply exercise 4.7 to conclude.
62 Chapter 4. Random sampling
Randomized algorithms
processed objects and let us call step r the step during which we process the r-th
object.
Let 0 be the object processed in step r. From the already computed set of
regions defined and without conflict over 7?, we compute in step r the set of
regions defined and without conflict over 1? U {O}.
* The regions of .Fo(Z) that do not belong to Yo(R U {O}) are exactly those
regions in Fo(QR) that conflict with 0. These regions are said to be killed
by 0, and 0 is their killer.
* The regions of Fo(1Z U {0}) that do not belong to Fo(1Z) are exactly those
regions .Fo(1Z U {0}) that are determined by a subset of R U {0} that
contains 0. These regions are said to be created by 0.
created by 0 are found. The complexity of each incremental step is thus at least
bounded from below by the number of regions that are killed or created during
this step, and by the number of conflict arcs that are removed or added during
this step.
1. updating the set of regions defined and without conflict over the current
subset can be carried out in time proportional to the number of regions
killed or created during this step, and
2. updating the conflict graph can be carried out in time proportional to the
number of conflict arcs added or removed during this step.
2. The probability p' (r) that F be one of the regions created by the algorithm
during step r is
p~i(r) rp (r).
In these expressions, p (r) stands for the probability that a region F of JFj(S) be
defined and without conflict over a random r-sample of S, as given in subsec-
tion 4.2.1.
If we replace pj (r) by its expression in lemma 4.2.1, we obtain (see also exer-
cise 5.1) that the probabilities p', and p' (r) satisfy the relation
n
r~1
determine F are processed before any of the j objects of S that conflict with F.
Since all permutations of these objects are equally likely, this case happens with
probability
i!j!
(i+j)!'
proving the first part of the lemma. Let 7? be the set of objects processed in the
steps preceding and including step r. For a region F to be created during step
r, we first require that F be defined and without conflict over 1R, which happens
precisely with probability pj (r). If so, F is created at step r precisely if the object
0 processed during step r is one of the i objects of 2 that determine F. This
happens with conditional probability i/r. El
0 ( fo(r, S))
r=1
2. The expected total number of conflict arcs added to the conflict graph by the
algorithm is
0 (n n; Mo r, S))
3. If the algorithm satisfies the update condition, then its complexity (both in
time and in space) is, on the average,
In these expressions, fo(r, S) denotes the expected number of regions defined and
without conflict over a random r-sample of S.
Thus, if fo(r, S) behaves linearly with respect to r (fo(r, S) = O(r)), the total
number of created regions is O(n) on the average, the total number of conflict arcs
is 0(n log n) on the average, and the complexity of the algorithm is 0(n log n) on
the average. If the growth of fo(r, S) is super-linear with respect to r (fo(r, S) =
O(r') for some a > 1), then the total number of created regions is O(n') on
the average, the total number of conflict arc is O(n') on the average, and the
complexity of the algorithm is O(n') on the average.
68 Chapter 5. Randomized algorithms
Proof.
1. We obtain the expectation v(S) of the total number of regions created by the
algorithm by summing, over all regions F defined over S, the probability that
this region F be created by the algorithm:
b n-i b n-i n
V~(S) Ip"
~~~ E JP
E|(S)| Iz p.(r).
i=1 j=O i=1 j=O r=1
2. Let e(S) be the expected total number of arcs added to the conflict graph.
To estimate e(S), we note that if a region F in conflict with j objects of S is a
region created by the algorithm, then it is adjacent to j conflict arcs in the graph.
Therefore,
bo n-i bo n-i n .
(S) ,E,|er 3(S) i PI';=
i=1 j=o
,E,£,|j(S)l 3lp(r)'
i=1 j=O r=1
Apart from the factor i/r, we recognize in this expression the moment of order 1
of a random r-sample (lemma 4.2.5). Applying corollary 4.2.7 to the moment
theorem, we get
e(A bE ml (r S)
r=l r-
3. A given region is killed or created at most once during the course of the
algorithm and, likewise, a given conflict arc is added or removed at most once. A
randomized incremental algorithm which satisfies the update condition thus has
an average complexity of at most
v(S)+e(S) = ° r2S)
2
l l
I I
The algorithm
* For each segment S of S \ 7?, the data structure stores a list £(S) repre-
senting the set of trapezoids of Dec,(7?) intersected by S. The list L:(S) is
ordered according to which trapezoids are encountered as we slide along S
from left to right.
* For each trapezoid F of Dec8 (7), the algorithm maintains the list £'(F) of
the segments in S \ 7? that conflict with F.
5.2. Off-line algorithms 71
£(S)
L'(F)
In the initialstep, the algorithm builds the decomposition Dec5 (R.) for a subset
7? of S that contains only a single segment. This decomposition consists of four
trapezoids. It also initializes the lists that represent the conflict graph. The
initial decomposition is built in constant time, and the initial conflict graph in
linear time.
The current step processes a new segment S of S \ I7: it updates the decom-
position and the conflict graph accordingly.
Updating the decomposition. The conflict graph gives the list £(S) of all
the trapezoids of Dec5 (1?) that are intersected by S. Each trapezoid is split into
at most four subregions by the segment S, the walls stemming from the endpoints
of S, and the walls stemming from the intersection points between S and the other
segments in R (see figure 5.3).
These subregions are not necessarily trapezoids of Dec, (1 U { S}). Indeed, S
intersects some vertical walls of Dec5 (1?), and any such wall must be shortened:
the portion of this wall that contains no endpoint or intersection point must be
removed from the decomposition, and the two subregions that share this portion
of the wall must be joined into a new trapezoid of Dec,(1Z U {S}) (see figure 5.4).
Thus, any trapezoid of Dec, (7? U {S}) created by S is either a subregion, or
the union of a maximal subset of subregions that can be ordered so that two
consecutive subregions share a portion of a wall to be removed. The vertical
adjacency relationships in the decomposition that concern trapezoids created by
S can be inferred from the vertical adjacency relationships between the subregions
and from those between the trapezoids of Dec,(7R) that conflict with S.
Updating the data structure that represents the decomposition Dec8 (R) can
therefore be carried out in time linear in the number of trapezoids conflicting
with S.
Updating the conflict graph. When a trapezoid F is split into subregions
Fi (i < 4), the list L'(F) of segments that conflict with F is traversed linearly,
and a conflict list V'(Fi) is set up for each of the subregions Fi. During this
72 Chapter 5. Randomized algorithms
72 Captr 5.Ranomied agorthm
I
So
Figure 5.3. Decomposing a set of segments: splitting a trapezoid into at most four new
trapezoids.
traversal, the list £(S') of each segment S' in £'(F) is updated as follows: each
node pointing to F in such a list is replaced by the sequence of those subregions
Fi that intersect S', in the left-to-right order along S'.
Consider now a sequence F 1 , F2 , .. ., Fk of subregions that have to be joined
to yield a trapezoid F' of Dec, (R U {S}) created by S. We assume that the
subregions are encountered in this order along S. To build the list £'(F'), we
must merge the lists L'(Fi) while at the same time removing redundant elements.
To do this, we traverse successively each of the lists V'(Fi). For each segment
S' that we encounter in £'(Fi), we obtain the entry corresponding to Fi in the
list L(S') by following the bidirectional pointer in the entry corresponding to
S' in the list £'(Fi). The subregions that conflict with S' and that have to be
joined are consecutive in the list C(S'). The nodes that correspond to these
regions are removed from the list L(S'), and for each entry Fj removed from
the list £(S'), the corresponding entry for S' in L'(Fj) is also removed. (This
process is illustrated in figure 5.5.) In this fashion, we merge the conflict lists of
a set of adjacent subregions while visiting each node of the conflict lists of these
subregions once and only once. Similarly, the corresponding nodes in the conflict
lists of the segments are visited once and only once. This ensures that the time
taken to update the conflict graph is linear in the number of arcs of the graph
that have to be removed.
(a) (b)
I
.I
: I : . :
: : I .
.I.
(c) (d)
condition 5.2.1. We may therefore quote theorem 5.2.3 to show that the average
running time of the algorithm, given a set of n segments with a intersection
points, is
O fo (rS))
1<r<n
L'(F2 )
J'(F3 )
]L'(F4)
Figure 5.5. Decomposing a set of line segments: merging the conflict lists.
(zr-2) (r)
Remark 2. The expected storage of the algorithm is O(n log n + a). In the
variant mentioned in the above remark, it is possible to simplify the conflict
graph: for each segment, we retain only a single conflict arc, for instance the
conflict with the trapezoid which contains the left endpoint of the segment. We
can still update the conflict graph in linear time, therefore the average running
time is unchanged and still O(n log n +a), but the expected storage is lowered to
O(n + a) (see exercise 5.4).
Algorithms that use a conflict graph are incremental but static, that is, they
require initial knowledge of all the segments to be inserted. In contrast, on-line
(or semi-dynamic) algorithms maintain the solution to the problem as the input
objects are inserted, with no preliminary knowledge of the input data. A possible
way to transform an algorithm that uses a conflict graph into an on-line algorithm
is to replace the conflict graph by a different kind of structure that can detect
conflicts between any object and the regions defined and without conflict over
the current set of objects. The influence graph is such a structure.
The influence graph is a structure that stores the history of the incremental con-
struction and depends on the order in which the objects have been processed
by the algorithm. This graph represents the regions created by the algorithm
during the incremental construction, and can be used to detect the conflicts
between these regions and a new object. When the algorithm uses a conflict
graph, the set of data is known in advance, and the algorithm may then com-
pute the objects in S that conflict with a given region. However, an on-line
algorithm does not assume any knowledge of the objects to be processed. Thus
it must be able to describe the entire domain of influence of a region which, as
we recall, is the subset of all the objects in the universe that conflict with this
region.
The influence graph is a directed, acyclic, and connected graph. It possesses
a single root, and its nodes correspond to the regions created by the algorithm
during its entire history. Therefore, a node corresponds to a region that was
defined and without conflict over the current set of objects at some point during
the execution of the algorithm. Properly speaking, this graph is not a tree: a
node might have several parents. Nevertheless, the terminology of trees will be
quite useful for describing it. In particular, a leaf is a node that has no children.
The influence graph must possess two essential properties.
76 Chapter 5. Randomized algorithms
Property 5.3.1 1. At each step of the algorithm, a region defined and without
conflict over the current subset is associated with a leaf of the influence
graph.
2. The domain of influence of a region associated with a node of the influence
graph is contained in the union of the domains of influence of the regions
associated with the parents of that node.
The algorithm
The algorithm is incremental and maintains the set Fo(7) of regions defined
and without conflict over the current set RZ, together with the influence graph
corresponding to the chronological sequence of objects in R?.
The initial step processes a small set of ro objects. For instance, ro can be
the minimal number of objects needed to determine a region. The algorithm
computes the regions defined and without conflict over the set Ro of these ro
objects. The influence graph is initialized by creating a root node, corresponding
to a fictitious region whose influence domain is the universe 0 of objects in its
entirety. A node whose parent is the root is created for each of the regions of
F(Ro).
In the current step, the object 0 is added to R?. The work can be divided into
two phases: we first locate 0 and then update the data structures.
Locating. In this phase, we must find all the regions in Fo(1Z) that conflict
with the new object 0. Starting from the root of the influence graph, we recur-
sively visit all the nodes that conflict with 0, and their children. The regions of
.To(7?) that conflict with 0 are said to be killed by 0.
Updating. We now have to update the data structure that represents the set
of those regions defined and without conflict over the current subset of objects
(To( Z) becomes Fo(UU{O})). We also have to update the influence graph. A leaf
of the influence graph is created for each of the regions in To(7? U {0}) \ .Fo(R).
These are the regions created by 0. Each of these leaves is linked to enough
parents to satisfy property 2 of the influence graph. We never remove a node
from the graph.
The details of the implementation of these steps naturally depend on the prob-
lem. Typically, the set of regions created by 0 can be derived from the set of
regions killed by 0, and the parents of the leaves corresponding to created regions
5.3. On-line algorithms 77
Theorem 5.3.2 Let an on-line algorithm use an influence graph to process a set
S of n objects. The expected number v(S) of nodes in this influence graph is
(E (r, S))
In this expression, fo(r,S) denotes the expected number of regions defined and
without conflict over a random r-sample of S.
To carry the analysis further, we must also be able to bound the number of
arcs in the influence graph, since this number gives the time and storage taken
78 Chapter 5. Randomized algorithms
to update the set of regions without conflict and the influence graph itself, as
is done in the second phase of each insertion step of the algorithm. We also
need a special assumption to control the complexity of testing whether there is
a conflict between an object and a region.' The triple update condition stated
below is actually satisfied by a large class of practical problems.
1. the existence of a conflict between a given region and a given object can be
tested in constant time.
2. the number of children of each node of the influence graph is bounded by a
constant, and
3. the parents of a node created by an object 0 are nodes that are killed by 0,
and updating the influence graph takes time linear in the number of nodes
killed or created at each step.
o (E fo(r, S))
r=1
o (En fo(rS))
0 (E fo(r2S))
4. The expected time complexity of the updating phase at step k is
1 Note
that such an assumption is implicitly contained in the update condition 5.2.1 when
the algorithm uses a conflict graph.
5.3. On-line algorithms 79
As always, fo(r, S) denotes the expected number of regions defined and without
conflict over a random r-sample of S.
Thus, the expected time complexity of an on-line algorithm that uses an influence
graph is identical to that of a similar incremental algorithm that uses a conflict
graph, as long as the respective update conditions are satisfied.
If fo(r, S) behaves linearly with respect to r (fo(r, S) = 0(r)), the complex-
ity of the algorithm is O(nlogn) on the average, and the expected storage is
O(n). Introducing the n-th object takes time O(logn) for the locating phase,
and constant time for updating the data structure and the influence graph.
If the growth of fo(r, S) is super-linear with respect to r (fo(r, S) = 0(r 0 ) for
some a > 1), the expected storage is O(n'). Introducing the n-th object takes
time 0(n'l) for the locating and updating phases.
Proof.
1. The upper bound on the expected storage is a direct consequence of theo-
rem 5.3.2, which bounds the number of nodes in the influence graph, and of the
second clause in the update condition, which bounds the number of children of
each node.
2. The contribution to the running time complexity of the updating phases is
proportional to the number of regions created, because of the third clause of the
update condition. From theorem 5.2.3, we know that this number is
0 (E fo(r, S)
kr=1
We still must evaluate the cost of the locating phases. From the first clause
of the update condition, we derive that the complexity of locating an object 0
is proportional to the number of nodes visited to locate 0. If every child has a
constant number of descendants (second clause in the update condition), however,
the number of nodes visited during the locating phase of 0 is at most proportional
to the nodes of the influence graph that conflict with 0. The overall cost of the
locating phases is therefore proportional to the total number of conflicts detected
during the algorithm.
Let F be a region of P.(S). If this region is created at some step of the al-
gorithm, the corresponding node in the influence graph will be visited j times
in the subsequent steps, and this happens each time we insert one of the j ob-
jects that conflict with F. For a given permutation of the input, an algorithm
that uses an influence graph will not only create the same regions as another
that uses a conflict graph, but will also detect a conflict with a given region
as many times as there are conflict arcs incident to this region in the conflict
graph.
80 Chapter 5. Randomized algorithms
b n-i k-1
w(k,S) = EIv ( E - piZ(r) -
i=1 j=0 r=1 r n-
If we recognize the expression for the first order moment of a random r-sample
of S given in lemma 4.2.5, and bound the sum above by using corollary 4.2.7 to
the moment theorem, we obtain
b k-1
w(k, S) = Za,(r)m l(rS)
4. Now, updating the data structure and the influence graph at step k takes time
proportional to the number of nodes created or killed by Ok. Let v(k, S) be the
expected number of regions created at step k. From lemma 5.2.2, we derive
b n-i
v(k,S) = ZZY(S) jpp(k)
i=i j=0
fo(k, S)
k
Let now v'(k, S) be the expected number of regions killed at step k. We denote
by Sk-1 the current subset immediately prior to step k. A region F in P, (S) is a
region killed at step k if it is a region of FO(Sk-1) that conflicts with Ok, which
happens with probability
pj (k -1) -+l.
5.3. On-line algorithms 81
The update condition 5.3.3 is not mandatory and it is often possible to analyze
an on-line algorithm that does not satisfy all of its clauses.
1. For instance, if the first clause is not satisfied, the cost of testing the conflicts
may be added to the analysis. If this cost can be bounded, this bound appears
as a multiplicative factor in the cost of the locating phases.
2. The analyses of on-line algorithms developed above and in the remainder
of this section are still valid for less restrictive statements of the third clause.
We may assume only that the cost of the update phase is proportional to the
number of regions created or killed. We have preferred, however, to assume that
the parents of nodes created by some object are killed by the same object. This
assumption is satisfied by most of the algorithms given in this book, and it greatly
simplifies the analysis of dynamic on-line algorithms given in the next chapter.
3. Lastly, the second clause can also be relaxed. Indeed, in order to bound the
space needed to store the influence graph, it suffices to bound the total number of
arcs in the entire graph and not necessarily the out-degree of each node. We may
then generalize the analysis of the locating phase by using the notion of a biregion
(see exercise 5.7). In particular, such an analysis applies to the case when the
number of parents of a node is bounded, but not the number of children. We
illustrate this situation in the case of the on-line computation of convex hulls (see
exercise 8.5).
decomposition for short. The notions of objects, regions, and conflicts are defined
as in subsection 5.2.2.
The trapezoids in the current decomposition are the regions defined and with-
out conflict over the current set of segments and are linked to the corresponding
nodes in the influence graph. An internal node of this graph is associated with
a trapezoid which was in the current decomposition at some previous step of the
algorithm. In addition to the set of pointers that take care of the parent-child
relationships between the nodes, each node contains the following information:
* A description of the corresponding trapezoid and a list of the (at most four)
segments that determine it.
* At most four pointers for the adjacency relationships through the vertical
walls. As long as the node is a leaf of the influence graph, the corresponding
trapezoid F belongs to the current decomposition and is adjacent to at most
four leaves in the graph, each of which shares a vertical wall with F. When
the node corresponding to F becomes an internal node, these pointers are
not modified any more.
|- D
A -
a5D
E F H D
I
I I :
G I:
Each internal node of the influence graph has at most four children, and the
running time needed to carry out all the operations described in the previous
paragraph is clearly proportional to the number of trapezoids in £(S). The
update condition is therefore satisfied.
From lemma 5.2.4, we know that the expected number of trapezoids in the
vertical decomposition of a random r-sample is O(n + ar2 /n 2 ), if n is the num-
ber of segments in S and a is the number of intersecting pairs of segments.
Theorem 5.3.4 therefore shows that the on-line algorithm just described has an
expected complexity of O(n log n + a) and uses expected storage O(n + a). The
average complexity of the n-th insertion is O(log n + a/n).
84 Chapter 5. Randomized algorithms
84 Chapter 5. Randomized algorithms
E :F A a
D
EFO I
,N . .:
Q
I I
Ir IVP
I IS w s I
oG
l l - l
[ ' n '
i
I
.1 D
N
, SI Q
I : A , Q .
. I
E: F :AI S U Vaw D
I HI p
I, I -
I I '
X YA
i . l,
r=k+l
Proof. The conflict graph at step k can be augmented, for each object 0 in
S \ Sk, by a list of pointers to the nodes of the influence graph which correspond
to a region of FO(Sk) that conflicts with 0. In order to locate the object 01
at step 1, the algorithm may start to traverse the influence graph not from the
root, but from the nodes of the influence graph which correspond to a region of
Fo(Sk) that conflicts with Oj. If the update condition is satisfied, the number
of children of each node is bounded by a constant, and the number of nodes
visited is proportional to the number of regions F created between steps k + 1
and 1 - 1 that conflict with 01. A region F in 4J(S) is created at step r with
probability 'pj(r). Given this, the conditional probability that F conflicts with
a given object 01 is g The expected number w(l,S) of nodes visited while
locating 01 is thus
I-1 b n-b9
w(l,S) = ZE ZYi(S)Ipi(r.i).
r=k+li=lj=O
In this expression we recognize the first order moment (lemma 4.2.5). Using
corollary 4.2.7 to the moment theorem, we obtain
Proof. The conflict graph is computed at steps nk = [n/ log(k) nj, for k = 1,...,
log* n. The conflict graph is therefore computed log* n times overall, accounting
5.4. Accelerated incremental algorithms 87
for an expected complexity of 0 (n log* n). The locating phases, between step nk
and step nk+1, have a total average complexity of
nk+1 nk+1
The total contribution of the locating phases to the running time is therefore, on
the average, O(n log* n). This fact combined with theorem 5.3.4 proves that the
average complexity of the accelerated algorithm is O(n log* n). cl
this decomposition, and the total complexity of following these edges is domi-
nated by the size O(nk) = O(n) of this decomposition. In the latter case, the
cost of following these edges is proportional to the number of conflicts between
these edges and the trapezoid of the decompositions Dec,(S(nk)).2 From the-
orem 4.2.6 and its corollary 4.2.7, the expected number of conflicts reported at
step nk is exactly the first order moment of the current subset of edges at step
nk. From corollary 4.2.7, this number is 0 (fo(Lnk/2j , S)), which is 0(n) for
non-intersecting segments, as is the case for the edges of a polygon.
The hypotheses of theorem 5.4.2 are thus satisfied, which yields:
Theorem 5.4.3 A randomized incremental algorithm can build the vertical de-
composition of a simple polygon with n edges in expected time O(n log* n).
Remark. The algorithm relies on two facts: the edges are connected, and do not
intersect except possibly at common endpoints. The same algorithm therefore
works as well in the more general cases of a polygonal line, or a connected set of
segments whose pairwise interiors are disjoint.
5.5 Exercises
Exercise 5.1 (Probabilities) Prove that
ii (n
n-i
i-i-j
J i!j!
E~srr n = (i + j)!
V rr
Then show that the probabilities p' and p'; (r) defined in section 5.2 satisfy the following
relation: n
plX ,pt'(r).
r=l1
Hint: The expected number of regions killed or created during step k of a randomized
incremental algorithm is estimated in the proof of theorem 5.3.4. It remains to estimate
the expected number of conflict arcs added or removed during step k.
Hint: We may redefine the notions of regions and conflicts as follows: A region defined
on 7t is a paddle with two components, a trapezoid F in the decomposition Dec(JZ), and a
wall butting on the floor or ceiling of F. A paddle is determined by at most six segments.
It conflicts with a segment if the interior of the trapezoid intersects the segment. The
problem is now to find an upper bound on the number of paddles defined and without
conflict with a segment of S \ RZ.
Exercise 5.4 (Storage) Consider the incremental algorithm that uses a conflict graph
as in subsection 5.2.2 in order to compute the decomposition of a set S of n segments.
Show that if a is the number of intersecting pairs, the storage needed by the algorithm
at step k is, on the average,
mi(k, S) =0 (n +a ).
Using the result of the previous exercise, show that we may reduce the storage to O(n)
by storing only one conflict for each non-inserted segment, say with the trapezoid that
contains its left endpoint, without affecting the running time of the algorithm.
Exercise 5.5 (Decomposing a set of curves) Show how to generalize the notion of
a decomposition for a set of curves supported by algebraic curves of bounded degree.
Two such curves intersect at only a constant number of points, which we assume may be
computed in constant time. Show that both algorithms given in subsections 5.2.2 and
5.3.2 may be extended to build the decomposition of a set of such curves.
Hint: Do not forget to trace walls from each point where the curves have a vertical
tangent.
Exercise 5.6 (Backward analysis) Backward analysis (see also exercises 4.1 and 4.2)
gives an alternative proof of the results of this chapter without using the explicit expres-
sions for p. (r) and p.(r).
90 Chapter 5. Randomized algorithms
For instance, we show how backward analysis can be used to estimate the number
v(k, S) of regions created at step k by an incremental algorithm. Note that if Sk is the
current subset immediately after inserting object Ok at step k, the regions created by Ok
during this step are the regions of FO(Sk) determined by a subset of Sk that contains
Ok. Since Ok, which has chronological rank k, may be any of the objects in Sk with
uniform probability k, a region of .FO(Sk) is created at step k with probability at most
b/k. Therefore, v(k, S) is at most the expectation of IFo(Sk)I over all possible Sk.
Similarly, a region that is killed during step k is a region of F1 (Sk) that conflicts with
Ok. Any region of -F (Sk) conflicts with Ok with probability I/k. The expected number
v'(k, S) of regions killed during step k is therefore at most the expectation of k 1F1(Sk)
over all possible Sk.
It is possible to compute in this fashion the expected numbers v(k,S) and v'(k,S)
of regions created or killed during step k. Show how to use backward analysis to
prove the other results in this chapter, for instance, to bound the number of conflict
arcs that are added to or removed from the conflict graph, or to bound the number
of conflicts detected during a locating phase by an algorithm that uses an influence
graph.
Exercise 5.7 (Biregions) The notion of biregion introduced in this exercise can be
used to analyze the average complexity of some algorithms that use an influence graph,
but do not satisfy the update condition 5.3.3. A biregion is pair of regions which can
have a parent-child relationship in the influence graph for at least one permutation of
the data. A biregion is determined by a set of at most 2b objects, those that determine
the parent region and those that determine the child region. Exactly one of the objects
that determine the child region conflicts with the parent region. We can extend the
notion of conflict to biregions in the following way: an object conflicts with a biregion
if it conflicts with at least one of its two regions and does not belong to the set of
objects that determine the biregion. A biregion can then be considered as a region in
the framework described in chapter 4.
1. Let S be a set of n objects. Show that a biregion, determined by i objects of S and
in conflict with j objects of S, is defined and with k conflicts over a random r-sample of
S with the probability p k(r) given by lemma 4.2.1.
2. From this, extend both the sampling theorem and the moment theorem to the case
of biregions.
3. In essence, the difference between biregions and regions resides in the following fact.
Let FF be a biregion determined by i objects and conflicting with j objects of S. For
FF to correspond to an arc in the influence graph built for S, it is not enough that the
i objects that determine FF be inserted before any of the j objects that conflict with
FF; it must also be the case that the i objects that determine i be processed in a certain
order. This order has to meet several criteria. These criteria depend on the algorithm.
At the very least, one of the objects that determine the child region, more precisely the
one that conflicts with the parent region, must be inserted after all the objects that
determine the parent region.
Show that the probability that FF correspond to an arc of the influence graph is eap'j,
where p"t is given
do in lemma
t 5.2.2, and a is a constant
t that satisfies 1 - o< a <
- and
that depends only on the particular criteria that the insertion order has to meet. Then
5.5. Exercises 91
show that the probability that the biregion FF correspond to an arc of the influence
graph that is created at step r is a p. (r), where p3 (r) is defined in subsection 4.2.1.
4. Our goal is now to give a randomized analysis of an on-line algorithm that uses an
influence graph in which a node can have arbitrarily many children. We thus forget about
the second clause in the update condition 5.3.3, and relax the third one by assuming that
the parents of a region created by 0 are either killed by 0, or still have no conflict after
the insertion of 0. In this way, regions defined and without conflict with the current
subset may not be leaves of the influence graph, but could have many children before they
are killed. The complexity of the update phase is still assumed to take time proportional
to the number of arcs added to or removed from the influence graph. For instance, the
algorithm that computes convex hulls described in exercise 8.5 meets these conditions.
Let ffo (r, S) stand for the expected number of biregions defined and without conflict
over a random r-sample of S. Show that the number of arcs in the influence graph built
for S is, on the average,
e (nffo(r, S))
Or= 1
0 (n E ffo (r, S) )
5. Assume now that the influence graph built for a random r-sample of S has an
expected number of arcs at most g(r,S), where g is a known function. For instance,
when each node of the influence graph has at most a bounded number of children, we
may choose
g(r, S) = 0( fo(aS))
j=l 3
Show that the n-th incremental step of the on-line algorithm has an average complexity
of
0 g(S) + n (r S)
O n +E
r=1
S1 C S2 C ... C Slogs n = S-
The algorithm computes a simplified description of the decomposition Dec8 (P), using
log* n steps. Step i computes the decomposition Dec8 (Si) from Dec (Si- 1).
92 Chapter 5. Randomized algorithms
In the initial step, we build Dec,(Si) using the plane sweep algorithm of subsec-
tion 3.2.2, in time O(rjlogrl). (Any algorithm that runs in time O(rilogrl) would
do.)
In a subsequent step i, i > 1:
1. We locate the segments of S in Dec8 (Si-i). In other words, for each region F in
Dec8 (Si-i), we compute the set S(F) of segments in S which intersect F.
2. For each region F of Dec,(Si-I), we compute the decomposition of S(F) USi, and
the portion of it that lies inside F. To do this, we simply compute the total de-
composition Dec, (S(F) U Si), using the plane sweep algorithm of subsection 3.2.2.
(Again, any algorithm that runs in time O(m log m) for m segments would do.)
3. We obtain Dec,(Si) by putting together all the portions Dec,(S(F) U Si) n F
inside the trapezoids F of Dec,( S i-1), and merging the regions that share a wall
of Dec,(Si-1) which disappears in Dec,(Si).
Show that all three phases 1, 2, and 3 can be performed using O(n) operations. To
analyze phase 2, note that Si-, is a random ri-1-sample of Si, then use the extension
of the moment theorem given in exercise 4.3 for the function g(x) = xlogx.
Exercise 5.9 (Querying the influence graph) The influence graph built by an on-
line algorithm can be used to answer conflict queries on a set of objects. For instance, the
influence graph built for a vertical decomposition can answer location queries for a point
inside this decomposition. Show that, if n segments are stored in the influence graph,
answering a given location query takes time O(logn), on the average over all possible
insertion orders of the n segments into the influence graph. More generally, show that
the same time bound holds for any conflict query which, on any subset JZ of objects,
answers with a single region of Fo(7Z).
their algorithm (see exercises 5.3 and 5.4). Mulmuley's algorithm is very similar to that
of Clarkson and Shor, yet its analysis is based on probabilistic games and combinatorial
series, and is much less immediate.
The influence graph was first introduced in a paper by Boissonnat and Teillaud [31, 32]
where it was called the Delaunay tree, and was used there to compute on-line the
Delaunay triangulation of a set of points. Guibas, Knuth, and Sharir [117] proposed
a similar algorithm to solve the same problem. How to use the influence graph in an
abstract setting is described by Boissonnat, Devillers, Schott, Teillaud, and Yvinec in
[28] and applied to other problems, especially to compute convex hulls or to decompose
a set of segments in the plane. The method was later used to solve numerous other
problems. The influence graph is sometimes called the history of the incremental con-
struction.
The accelerated algorithm that builds the vertical decomposition of a simple polygon
is due to Seidel [204]. This method was subsequently extended to solve other problems
by Devillers [80], for instance to compute the Voronoi diagram of a polygonal line or of
a closed simple polygon (see section 19.2). The algorithm described in exercise 5.8 that
computes the decomposition of a polygon in time O(n log* n) is due to Clarkson, Cole
and Tarjan [69].
The method called backward analysis used in exercise 5.6 was first used by Chew in
[59] to analyze an algorithm that computes the Voronoi diagram of a convex polygon
(see exercise 19.4). It was subsequently used in a systematic fashion by Seidel in [203]
and Devillers in [80].
Mehlhorn, Sharir, and Welzl [167, 168] gave a finer analysis of randomized incremental
analysis by bounding the probability that the algorithm exceeds its expected perfor-
mances by more than a constant multiplicative factor.
Randomized incremental algorithms proved very efficient in solving many geometric
problems. The basic methods (using the influence or the conflict graphs) or one of
their many variants inspired much work by several researchers such as Mulmuley [172,
174], Mehlhorn, Meiser and 6 'Dinlaing [164], Seidel [205], Clarkson and Shor [71], and
Aurenhammer and Schwarzkopf [18].
There is a class of randomized algorithms which work not by the incremental method,
but rather by the divide-and-conquer paradigm. The subdividing step is achieved using
a sample of the objects to process. Randomization is used for choosing the sample, and
the method can be proved efficient using the probabilistic theorems given in exercises 4.5
and 4.6. Randomized divide-and-conquer is mainly used for building hierarchical data
structures that support repeated range queries. Typically, these queries can be expressed
in terms of locating a point in the arrangement of a collection of hyperplanes, simplices,
or other geometric objects. In a dual situation, the data set is a set of points and
the queries ask for those points which lie in a given region (half-space, simplex, ... ).
Haussler and Welzl [123] spurred new interest in the field with their notion of an e-net.
Later, Matousek introduced the related notion of c-approximations [150]. Chazelle and
Friedman [53] showed how to compute these objects in a deterministic fashion using
the method of conditional probabilities. The resulting deterministic method is called
a derandomization of the randomized divide-and-conquer method. This method was
then widely used, for instance by Matousek [150, 151, 152, 153, 154, 155], Matousek
and Schwarzkopf [156], or Agarwal and Matousek [4]. In his thesis [35], Br6nnimann
94 Chapter 5. Randomized algorithms
studies the derandomization of geometric algorithms and the related concept of the
Vapnik-Chervonenkis dimension. Randomized divide-and-conquer is also used by Clark-
son, Tarjan, and Van Wyk in [65] to build the vertical decomposition of a simple
polygon.
Last but not least, the book by Mulmuley [177] is entirely devoted to randomized
geometric algorithms, and serves as a very comprehensive reference on the topic.
Chapter 6
Dynamic randomized
algorithms
The geometric problems encountered in this chapter are again stated in the ab-
stract 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, Fo (S) stands for the set of regions defined
and without conflict over S. To design a dynamic algorithm that maintains the
set Fo(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.
Such a structure is called an augmented influence graph, and can be imple-
mented using an influence graph together with a conflict graph between the re-
gions stored in the influence graph and the current set of objects. In some cases,
we might be able to do without the conflict graph.
96 Chapter 6. Dynamic randomized algorithms
In section 6.2, we describe the augmented influence graph and how to perform
insertions and deletions. The randomized analysis of these operations is given in
section 6.3. This analysis assumes a probabilistic model which is made precise
and unambiguous in section 6.1. The general method is used in section 6.4 to
design a dynamic algorithm that builds the vertical decomposition of a set of
segments in the plane.
This chapter also uses the terminology and notation introduced in the previous
two chapters. To ease the reading process, some definitions are recalled in the
text or in the footnotes.
Inserting an object
Inserting an object O, into a structure built for a set Sn-_ is very similar to the
operation of inserting an object in an on-line algorithm that uses an influence
98 Chapter 6. Dynamic randomized algorithms
graph. The only difference is that, in addition to the insertion into the influence
graph, we must also take care of updating the conflict lists. This can be done in
two phases: a locating phase, and an updating phase.
Locating. The algorithm searches for all the nodes in the influence graph of
:Za(E) that conflict with On. Each time a conflict is detected, we add a conflict
arc to the conflict graph, add On to the conflict list of the region that conflicts
with it, and add this region to the list L(OA).
Updating. A node of the influence graph is created for each region in Fo(Sn)
determined by a set of objects that contains On. This node is also linked to
parent nodes so that the two inclusion properties hold.
We may recall that a region in Fo(Sn) is said to be created by On if it is
determined by a set of objects that contains On. Similarly, a region of FO(Sn-1)
is said to be killed by On if it conflicts with On. More generally, a region stored
in a node of the influence graph Ta(s) has a creator in E, and a killer if it is not
a leaf. The creatorof F is, among all the objects that determine F, the one that
has the highest rank in E. The killer of F is, among all the objects in E that
conflict with F, the one with the lowest chronological rank.
For the rest of this chapter, we assume that the augmented influence graph
satisfies the update condition 5.3.3. In particular, a node of the graph that stores
a region created by On is linked only to nodes storing regions killed by On.
Deleting an object
To simplify the discussion, assume that the current set S has n objects, and that
the current data structure is the augmented influence graph la(s) corresponding
to the chronological sequence E = {O1, - , On}. The object to be deleted is
.
Ok, the object that has chronological rank k. The algorithm must modify the
augmented influence graph to look as if Ok had never been inserted into E.
The augmented graph must therefore correspond to the chronological sequence
S = {O1i,. ,Ok-1, Ok+1.... On}.
For any integer 1, k < I < n, let us denote by S' the subset S1 \ {Ok} of S. In
particular, observe that Sk = Sk-1.
In what follows, an object is called a determinant of a region if it belongs to
the set of objects that determine that region. The symmetric difference between
the nodes of Ia(s) and those of Ia(E') can be described as follows.
1. The nodes of la(s) that do not belong to -Ea(V) are determined by a set
of objects that contain Ok. Therefore Ok is a determinant of those regions,
and we say that such nodes (and the corresponding regions) are destroyed
when Ok is deleted.
2. The influence graph Ta(V') has a node that does not belong to la(E) for
6.2. The augmented influence graph 99
each region in U1=k+1. nFo(SI) that conflicts with Ok. Let us say that
such a node is new when Ok is deleted, and so is its corresponding region.
A new region has a creator and, occasionally, a killer in the sequence E'. If
the region belongs to Fo(S'), conflicts with Ok, and is determined by a set
of objects that contain O, then it is a new region after Ok is deleted, and
its creator is Qi.
Nodes that play a particular role when Ok is deleted include of course the
new nodes as well as the destroyed ones, but the nodes killed by Ok also have
a special part to play. The nodes killed by Ok should not be mistaken for the
nodes destroyed when Ok is deleted. Nodes killed by Ok correspond to regions
of Fo(Sk-l) that conflict with Ok, whereas nodes destroyed when Ok is deleted
correspond to regions that admit Ok as a determinant. The latter nodes disappear
from the whole data structure when Ok is deleted. The former nodes are killed
when Ok is inserted but remain in the data structure (occasionally becoming
internal nodes), and they still remain after Ok is deleted.
Upon a deletion, the arcs in the influence graph Ta(s) that are incident to
the nodes destroyed by Ok disappear and the graph Ia(E') has arcs incident to
the new nodes. In particular, new nodes must be linked to some parents (which
are not necessarily new nodes). Moreover, a few nodes of Ia(s) that are not
destroyed witness the destruction of some of their parents. Let us call these
nodes unhooked. They must be rehooked to other parents.
Again, deletions can be carried out in two phases: a locating phase, and a
rebuilding phase.
Locating. The algorithm must identify which nodes of the influence graph
la(s) are in conflict with Ok, which nodes have to be destroyed, and which are
unhooked. Owing to both inclusion properties, this can be done by a traversal of
the influence graph. This time, however, we not only visit the nodes that conflict
with Ok, but also those which admit Ok as a determinant. The destroyed or
unhooked nodes are inserted into a dictionary which will be looked up during the
rebuilding phase.
Rebuilding. The first thing to do is to effectively remove all the destroyed
nodes. Those nodes can be retrieved from the dictionary, and all the incident
arcs in the graph are also removed from the graph. The conflict lists of the nodes
which conflict with °k are also updated accordingly. We shall not detail these
low-level operations any further, as they should not raise any problems. Next,
we must create the new nodes, as well as their conflict lists; we must also hook
these new nodes and rehook the nodes that were previously unhooked. The detail
of these operations depends on the nature of the specific problem in hand. The
general design is always the same, however: the algorithm reinsertsone by one,
and in chronological order, all the objects Qi whose rank I is higher than k and
that are creators of at least one new or unhooked region. To reinsert an object
100 Chapter 6. Dynamic randomized algorithms
involves creating a node for each new region created by QI, hooking this node
into the influence graph, setting up its conflict list, and finally rehooking all the
unhooked nodes created by O1.
To characterize the objects Oj that must be reinserted during the deletion of
Ok, we must explain what critical regions and the critical zone are. For each
I > k, we call critical those regions in .Fo(S -1) that conflict with Ok- We call
critical zone, and denote by Z- 1 , the set of those regions.
Lemma 6.2.1 Any object 01 of chronological rank 1 > k that is the creator of
a new or unhooked node when Ok is deleted conflicts with at least one critical
region in Z1 - 1.
with 01. The object O1 is then reinserted, and the details of this operation depend
of course on the problem in hand. The main obstacle is that we might have to
change more than the critical zone of the influence graph. Indeed, the new regions
created by 01 always have some critical parents, even though they may also have
non-critical parents. Moreover, parents of an unhooked region are new, but the
unhooked region itself is not. To correctly set up the arcs in the influence graph
that are incident to new nodes, the algorithm must find in Ia(s) the unhooked
nodes and the non-critical parents of the new nodes. At this phase, the dictionary
set up in the locating phase is used. After reinserting 01, the priority queue Q is
updated as follows: the regions in Z 1 _1 that conflict with 01 are not critical any
more; however, any new region created by 0 belongs to Z1. Then for each of
these regions F, the killer of F in A' is identified as the object in L'(F) with the
smallest chronological rank. This object is then searched for in Q and inserted
there if it is not found. Then F is added to the list of regions killed by QI.
Lemma 6.3.1 Upon deleting an object, the number of nodes that are destroyed,
new, or unhooked is, on the average,
o ( Lfo (I S)
where, as usual, fo(l, S) stands for the number of regions defined and without
conflict over a random sample of size I from S.
Proof. We bound the number of destroyed, new, and unhooked nodes separately.
1. The number of destroyed nodes. A node in Ta(s) corresponding to a
region F in 4j (S) is destroyed during a deletion if the object deleted is one of the
i objects that determine the region F. Let F be a region in F(S). Given that F
corresponds to a node in the influence graph built for S, this node is destroyed
during a deletion with a conditional probability i/n < b/n. From theorem 5.3.2,
we know that the expected number of nodes in the influence graph is
n(fMlS)
102 Chapter 6. Dynamic randomized algorithms
so the number of nodes destroyed when deleting an object is, on the average,
1 E fo(1, S))
2. The number of new nodes. The regions that correspond to the new nodes
in the influence graph when Ok is deleted are exactly the regions created by 01,
for some I such that k < 1 < n, that belong to Fo(S') and conflict with Ok. Let
F be a region of 4j(S). This region F belongs to TFo(S1) with the probability
pj(1 - 1) that was given in subsection 5.2.2. Assuming this, F is created by 01
with conditional probability i/(l - 1), and F conflicts with Ok with conditional
probability j/(n - I + 1). Therefore, for a given k, the number of new nodes in
the influence graph upon the deletion Ok is, on the average (using corollary 4.2.7
to the moment theorem),
EL E AI(S)
P;(l -1) I = °( _ _
Averaging over all ranks k, the number of new nodes in the influence graph after
a deletion is
1 nn1 fo( Ll'/2j , S) 1 n-1 fo (1,S)
0n -EE 1'2 =0°VE
3. The number of unhooked nodes. Unhooked nodes are the non-destroyed
children of destroyed nodes. If condition 5.3.3 is satisfied, the number of children
of each node in the augmented influence graph is bounded by a constant. It
follows that the number of unhooked nodes is at most proportional to the number
of destroyed nodes. El
The update condition 5.3.3 assumes that the number of children of a node
is bounded by a constant. However, the number of parents of a node is not
necessarily bounded by a constant and the following lemma is useful to bound
the number of arcs in the influence graph that are removed or added during a
deletion.
Lemma 6.3.2 The number of arcs in the influence graph that are removed or
added during a deletion is, on the average,
Proof. The simplest proof of this lemma involves the notion of biregion encoun-
tered in exercise 5.7. A biregion defined over a set of objects S is a pair of regions
defined over S which can possibly be related as parent and child in the influence
graph, for an appropriate permutation of S. A biregionis determined by at most
2b objects, and the notion of conflict between objects and regions can be extended
to biregions: an object conflicts with a biregion if it is not a determinant of any
of the two regions but conflicts with at least one of the two regions. Biregions
obey statistical laws similar to those obeyed by regions. In particular, a biregion
determined by i objects of S which conflicts with j objects of S is a biregion
defined and without conflict over a random l-sample of S, with the probability
p'(I) given by lemma 4.2.1. A biregion defined and without conflict over a subset
S of S corresponds to an arc in the influence graph whenever the objects that
determine the parent region are inserted before those that determine the child
region and at the same time conflict with the parent region. This only happens
with a probability a E [0,1] (which depends on the number of objects determin-
ing the parent and the child, and the number of objects that at the same time
determine the child and conflict with the parent).
A biregion determined by i objects in S and conflicting with j objects in S
corresponds to an arc in the influence graph la(s) that was created by 01, with
a probability smaller than l pj(1) (see also exercise 5.7); this arc, created by 01,
conflicts with Ok with a probability smaller than
1 j
- pZ (I).
A computation similar to that in the proof of lemma 6.3.1 shows that the
expected number of arcs in the influence graph that are created or removed
during a deletion (which are those adjacent in the influence graph to new nodes
or to destroyed nodes) is
I n1E ffo (1, S)A
Vn 11 l
where ffo(i, S) is the expected number of biregions defined and without conflict
over a random 1-sample of S. It remains to show that ffo(l, S) is proportional to
fo(l, S). Let S1 be a subset of size 1 of S. The parent region in a biregion that
is defined and without conflict over SI is a region defined over SI that conflicts
with exactly one object in SI, and is therefore a region in F1 (SI). Conversely,
if the update condition 5.3.3 is true, every region in Fl(Sl) is the parent in a
bounded number of biregions defined and without conflict over S1. It follows that
ffo(l, S) is within a constant factor of the expectation fi(l, S) of the number of
regions defined and conflicting with one element over a random i-sample. From
corollary 4.2.4 to the sampling theorem, this expected number is O(fo(l, S)). E
104 Chapter 6. Dynamic randomized algorithms
Lemma 6.3.3 The total size of all the conflict lists attached to the nodes that
are new or destroyed when an object is deleted is, on the average,
0 (E fo(1 S))
Proof.
1. Conflict lists of destroyed nodes. A region F of 4j(S) corresponds to a
node of the influence graph Ta(s) with probability
n
P3; (1),
1=1
as implied by lemma 5.2.2. The conflict list attached to this node has length j
and this node is destroyed during the deletion of an object with probability i/n.
The total size of the conflict lists attached to destroyed nodes is thus
LEE~~I-i
l~(S) IP3
p(1)I- = ( Eml,)
1i=t1 3=111
= O( 2 (n l ) fo(LS2))
= 0 ( fo (1iS))
112
E_ E I j(S)I pJ(l-1) n -
n-+)(1
(j-1)
i= =1 =k+l 11
Applying corollary 4.2.7, this size is
Lastly, setting up the priority queue Q of killers of critical regions involves the
regions of the influence graph La(E) that are killed by Ok. The conflict lists of
these regions are traversed in order to set up the conflict lists of the new children
of these nodes. The following lemma is therefore needed in order to fully analyze
dynamic algorithms.
Lemma 6.3.4 The number of nodes in the influence graph la(E) that are killed
by a random object in S is, on the average,
o( Efo(1, S))
The total size of the conflict lists attached to the nodes killed by a random object
is, on the average,
o (I fo(1, S))
pj(k -1)
n EZZZ
k=2 i=1 j=1
i(S)I p,(k-1) 'k = E
k=2
- 0 (!foI:
(n kL
as can be deduced from corollary 4.2.7 to the moment theorem.
The total size of the conflict lists attached to nodes killed by a random object
is, on the average,
= E f o ( Lk/2j, S))
k=1
O (EMol, S))
106 Chapter 6. Dynamic randomized algorithms
Parameter t' is O(log n) if we use a balanced binary tree, but it is O(log log n)
if we use a stratified tree along with perfect dynamic hashing (see section 2.3).
Moreover, as we will see further on, if fo(l, S) grows at least quadratically, then
implementing Q with a simple array of size n will suffice, and t' can be ignored
in the analysis.
o (n Ml S))
o ( fo(l, S)
As always, fo(l,S) is the number of regions defined and without conflict over a
random I-sample of S, t is the complexity of any operation on a dictionary, and
t' is the complexity of an operation on the priority queue Q.
Proof.
1. The storage needed by the augmented influence graph fa(s) is proportional
to the total size of the conflict lists attached to the nodes of lTa(s). Each element
in one of these conflict lists corresponds to a conflict detected by an on-line
algorithm processing the objects in S in the chronological order of the sequence
E. The expected number of conflicts, for a random permutation of E, is thus
given by theorem 5.2.3 which analyzes the complexity of incremental algorithms
that use a conflict graph.
2. The randomized analysis of an insertion into the augmented conflict graph
is identical to that of the incremental step in an on-line algorithm that uses
an influence graph. Indeed, the two algorithms only differ in that one updates
conflict lists. Each conflict between the inserted object and a node in the current
108 Chapter 6. Dynamic randomized algorithms
0 IS (L2 2,S
which we know from the proof of theorem 5.3.4. Averaging over the rank of the
deleted object, we get
o ( fo (l S))
From lemma 6.3.1, the latter expression is also a bound on the expected number
of nodes destroyed and thus on the global cost of traversing the influence graph.
If the update condition 6.3.5 is realized, lemmas 6.3.3 and 6.3.4 show that the
conflict lists of the new regions can be set up in time
o (E fo(1,S))
Lemma 6.3.1 and the update condition 6.3.5 (2a) assert that the term
o (t Eo ( IS))
accounts for the average complexity of all the operations performed on the dic-
tionaries of nodes.
Since t is necessarily Q(1), lemmas 6.3.1 and 6.3.2, together with condition 6.3.5
(2c), assert that the former term also accounts for all the operations that update
the augmented influence graph, not counting those on the conflict lists or the
priority queue.
It remains to analyze the management of the priority queue Q of critical region
killers. The number of insertions and queries in the priority queue is proportional
to the total number of critical regions encountered during the rebuilding phase.
6.3. Randomized analysis of dynamic algorithms 109
These regions are either killed by the deleted object, or they are new regions.
Their average number is thus
0 1 Efo(l' 5))
as asserted by lemmas 6.3.1 and 6.3.4. The average number of minimum queries
to be performed on the queue Q is
since the number of objects to be reinserted is bounded from above by n on the one
hand, and by the number of unhooked or new nodes (estimated by theorem 6.3.1)
on the other hand. [1
Consequently,
I fo (1,S))
each such object QI, a killer of a critical region, the algorithm builds the new
nodes created by 01 and rehooks the unhooked nodes created by 01. Figure 6.1
shows how the influence graph built for the four segments {°O, 02, 03, 04} is
modified when deleting 03. The reader may observe again how the graph was
created incrementally, in figures 5.6, 5.7 and 5.8. In this example, nodes B and H
are killed by 03, nodes J,K,L,M,N,O,P,Q,S,U,V are destroyed, nodes R,T,W
are unhooked (they are created by 04), and B' is a new node (its creator is 04).
The subsequent paragraphs describe in great detail the specific operations
needed.
Locating. This phase is trivial: all the nodes that conflict with the object
Ok to be deleted, or that are determined by a subset containing Ok, are visited
together with their children. The algorithm builds a dictionary D of unhooked
or destroyed nodes, which will be used during the rebuilding phase.
Rebuilding. The priority queue Q, which contains the killers of critical re-
gions, is initialized with the nodes in Ia(s) that are killed by Ok-
At each step in the rebuilding process, the algorithm extracts from the priority
queue Q the object 0 1 of smallest chronological rank. It also retrieves the list of
the critical regions that conflict with 01.
Each of these regions is split into at most four subregions by 01, and the walls
stemming from its endpoints and its intersection points. These subregions are
not necessarily trapezoids in the decomposition Dec(S'). Indeed, the walls cut
by 01 have to be shortened, keeping only the part that is still connected to the
endpoint or intersection point from which it stems. The other part of the wall
must be removed and the adjacent subregions separated by this part must be
joined. The join can be one of two kinds: internalwhen the portion of wall to be
removed separates two critical regions, and external when it separates a critical
region from a non-critical region (see figure 6.2).
To detect which regions to join, 2 the algorithm visits all the critical regions
that conflict with 01, and stores in a secondary dictionary DI, the walls incident
to these regions that are intersected by 01. Any wall in this dictionary that
separates two critical regions gives rise to an internal join, and any wall incident
to only one critical region gives rise to an external join.
In a first phase, the algorithm creates a temporary node for each subregion
resulting from the splitting of a critical region by 01 or the walls stemming from
Oj. The node that corresponds to a subregion Fi of the region F is hooked in the
graph as a child of F. Its conflict list is obtained by selecting, from the conflict
2
The algorithm cannot traverse the sequence, ordered by O, of critical regions for two rea-
sons: (1) it does not maintain the vertical adjacencies between the internal nodes of the influence
graph, and the adjacencies between either the trapezoids of the decomposition Dec(Sl-1) or the
critical regions of Zj-1 are not available, and (2) the intersection of 0Q with the union of the
regions in Zj-1 may not be connected (see for instance figure 6.4).
112 Chapter 6. Dynamic randomized algorithms
(a)
F D
(b) (c)
(d)
(b)
77
-I
.I--
I ! I : ;
(c) (d)
list of F, the segments intersecting Fi. Then the algorithm processes the internal
and the external joins, as explained below.
1. Internal joins. Every maximal set {G 1 , Gh} of subregions, pairwise ad-
jacent and separated by walls to be removed, must be joined together into a single
region G. The algorithm creates a temporary node for G. The nodes correspond-
ing to G 1, G 2 ,. . . , Gh are removed from the graph and the node corresponding
to G inherits all the parents of these nodes. The conflict list of G is obtained by
merging the conflict lists of G 1 , G2 , .. ., Gh, removing redundancies. For this, we
use a procedure similar to that of subsection 5.2.2, but which need not know the
order along 01 of the subregions to be joined. By scanning the conflict lists of
these subregions successively, the algorithm can build for each segment 0 in S a
list LG(O) of the subregions that conflict with 0. A bidirectional pointer inter-
114 Chapter 6. Dynamic randomized algorithms
connects the entry in the list L'(Gi) that corresponds to an object 0 with the
entry in LG(O) corresponding to the subregion Gi. The conflict list of G can be
retrieved by scanning again all the conflict lists L'(Gi) of the subregions G1 , ....
Gh. This time, each segment 0 encountered in one of these lists is added to the
conflict list of G and removed from the other conflict lists, using the information
stored in LG(O).
Let us call auxiliary regions the regions obtained after all the internal joins.
These regions are either subregions that needed no internal join, or regions ob-
tained from an internal join of the subregions. An auxiliary region that does not
need to undergo any external join is a region of the decomposition Dec(S'). Let
H be such a region. This region is new if it conflicts with Ok, unhooked other-
wise. In the former case, the temporary node for H becomes permanent and the
killer of H is inserted into the priority queue Q. In the latter case, a node for H
already exists in the influence graph la(S). A simple query in the dictionary of
unhooked nodes retrieves this node, which can then be rehooked to the parents
of the auxiliary node created for H.
2. External joins. In a second phase, the algorithm performs the external joins.
An auxiliary region undergoes a left join if its left wall must be removed, and a
right join if its right wall must be removed, and a double left-right join if both its
vertical walls must be removed. Let G be an auxiliary region undergoing a right
join. For instance, this is the case for region G = GI U G2 in figure 6.2. The right
wall of G is on the boundary of the critical zone, since this is an external join. This
wall is therefore not cut by the deleted segment Ok. When the decomposition
of S is built incrementally according to the order in the sequence A, this wall
appears at a certain step and is removed when Oj is inserted. Thus, among all
the regions in la(S), there is one region Fd created by O1 that contains the right
wall of G.3 The region Ed is necessarily destroyed or unhooked: indeed, Ed is a
trapezoid in the decomposition Dec(S1), and has a non-empty intersection with
one or more critical regions in Z1 _1 . As every critical region in Z1 - is contained
in the union of the trapezoids of Dec(SI-1 ) of which Ok is a determinant, the
region Ed must intersect those trapezoids. Thus at least one of the parents of Ed
in the graph la(S) is a destroyed node. Similarly, if the left wall of G must be
removed, there is in Ia(E) one destroyed or unhooked region Fg created by 01
that contains the left wall of G. If the join is double left-right, Ed and Fg may
be distinct or identical (see figure 6.3).
Several auxiliary regions may be joined into the same permanent region (see
figure 6.4). Let {G1 , G2, . ., Gj} be the sequence ordered along 0l of the auxiliary
3
1t would have been more desirable to subscript F by 1 and r for left and right, but this
would have conflicted with the index I for Oj and created confusion. We have kept a French
touch with the indices g and r for the French gauche and droit, meaning respectively left and
right. (Translator's note)
6.4. Dynamic decomposition of a set of line segments 115
V VK'1 2/Z
'
6<
Fg /
Fd 4
01:
regions 4 whose left wall is contained in the same region Fg of Ia(s) created by
O°. If j > 1, then the right walls of these auxiliary regions {G1 , G2 , . . ., Gj-1,
are also contained in Fg and must be removed as well. If the right wall of Gj is
a permanent wall (that does not have to be removed), the join results in a single
trapezoid of the decomposition Dec(S, ) that is the same as Fg U G1 U . .. U Gj =
Fg U Gj (see figure 6.4). If the right wall of G3 also has to be removed, then
we introduce the ordered sequence of auxiliary regions {Gj, Gj+l, . . , Gh}: this
sequence consists of regions whose right wall must be removed and which lie in
the same region Fd of Ia(s) created by O1. The left walls of the regions in
{ Gj, Gj+l,... , Gh} then also belong to Fd and have to be removed. The join
operates on the auxiliary regions {G1 , ... , GjC,..., GO} and results in a unique
trapezoid in Dec(S8) that is the same as F. U G1 U . . . U Gh U Fd = F9 U Gj U Fd.
We present below the operations to be performed in the latter case of a double
left-right join. The former cases can be handled in a similar manner. Suppose
for now that the auxiliary regions {G1 , . . . , Gj,. . . , Gh} as well as the regions Fg
and Fd in the decomposition Ia(s) that participate in the join are known to the
algorithm.
If the trapezoid resulting from the join F = Fg U Gj U Fd does not conflict
with Ok (see figure 6.3, right), it is a trapezoid in the decomposition Dec(Sl).
Necessarily, the regions Fg, Fd, and F are the same, and the corresponding node
in Ia(s) is unhooked. It then suffices to search for this node in the dictionary of
unhooked nodes, to remove the auxiliary nodes created for G1 , G2 , . . ., Gh, and
to rehook the node corresponding to F, with the critical nodes in the parents of
G1 , G2 , .. ., Gh as the parents of F.
If the resulting trapezoid F = Fg U Gj U Fd conflicts with Ok (see figure 6.3,
left), then it is a new region of la(E'), and the regions Fg and Fd in la(E)
4
We must emphasize that even though the given description of the region resulting from an
external join refers to the order of the joined auxiliary regions along 01, the algorithm does not
know this order, nor does it need it.
116 Chapter 6. Dynamic randomized algorithms
III
_ I I ,I
Uk I i
(a)
(a)
LD)
(c)
are destroyed. The auxiliary nodes created for G1 , G2 , .. ., Gh are removed, and
replaced by a single node corresponding to F. This node is then rehooked to the
parents of F, and Ed that are not destroyed, and to all the critical parents of G1 ,
G2 , ... , Gh. The conflict list of F is derived from those of F9 ,G1 , G 2 , ... , Gh
and Ed, as is the case for internal joins. Lastly, the killer of F is inserted into the
priority queue Q.
We now have to explain how to retrieve the unhooked or destroyed nodes
corresponding to the regions Fg and Fd involved in the join. Let G be an auxiliary
region whose left wall must be removed. The corresponding region Fg is either
6.4. Dynamic decomposition of a set of line segments 117
destroyed or unhooked, created by QI, and the segments that support its floor
and ceiling 5 respectively support the floor and ceiling of G. Any region in the
decomposition of a given set of segments is identified uniquely by its floor, its
ceiling, and one of its walls. Below, we show that either we can find one of the
walls of F., or we can identify a destroyed region F' which is the unique sibling
of F9 in la(s).
* If G does not conflict with Ok, but its right wall is permanent (see fig-
ure 6.5b), then this right wall is also that of F9 .
* Lastly, if G does not conflict with Ok, and if both its walls must be removed
(see figure 6.5c), then segment 0Q intersects both walls of a critical region
that was subsequently split into G and G'. The other subregion G' also
conflicts with Ok but does not undergo any join. In Ila(s), exactly one
node F' has Ot for creator, is destroyed, and shares the same floor, same
ceiling, and same left wall as G'. This node F' has only one parent, and
this parent has two children, one of which is F' and the other the node F9
that we are looking for: indeed, the parent of F' corresponds to a trapezoid
in the decomposition Dec(S 1- 1) whose two walls are intersected by 0 e.
In either case, the region Fg, or its sibling F' is known through its creator, its
floor, its ceiling, and one of its left or right walls. This information is enough to
characterize it. Naturally, the same observation goes for Fd or its sibling Fd. We
can then use the dictionary D storing all the destroyed or unhooked nodes. This
dictionary comes in two parts, Dg and Dd. In the dictionary Dg, the nodes are
labeled with:
* the pair of segments whose intersection determines the right wall of the
trapezoid, or the same segment repeated twice if the wall stems from the
segment's endpoint.
Similarly, in its counterpart Dd, nodes are labeled the same way, except that in
the last component the right wall is replaced by the left wall. Any destroyed or
unhooked node is inserted into both dictionaries Dg and Dd.
5
We recall that the floor and ceiling of a trapezoid are its two non-vertical sides.
118 Chapter 6. Dynamic randomized algorithms
-77
(a) (b)
-i
A
(c)
To analyze this algorithm, we first check that it does satisfy the update condi-
tions 6.3.5. The first condition is satisfied, since the augmented influence graph
has the same nodes and arcs as the influence graph built by the on-line algorithm
of subsection 5.3.2, which itself satisfies the update condition 5.3.3. Therefore,
we need only look at deletions.
1. Number of operations on the dictionaries. Each deletion involves a
two-sided dictionary D of destroyed or unhooked nodes, as well as a dictionary
D., for each reinserted segment Qi, of walls in the critical zone intersected by
Ot. A destroyed or unhooked node is inserted and queried at most once in D.
A critical region in Z 1 - has at most two walls which must be inserted into DJ,
and this region will not be a critical region any more after the reinsertion of 01.
The number of operations on all dictionaries DI is thus at most proportional to
the total number of critical regions encountered in the rebuilding phase. Any
critical region is either killed or new. The total number of operations is thus at
most proportional to the number of nodes that are killed, destroyed, unhooked,
or new.
2. Conflict lists of new nodes. The conflict list of a new node is obtained by
scanning the conflict lists of the auxiliary or destroyed regions of which it is the
6.4. Dynamic decomposition of a set of line segments 119
(- I f 1S) = (1 + a)'
O (If ( S) = O(logn + )
We can now use theorem 6.3.6 to state the following theorem, which summarizes
the results so far:
O(log n+ a).
n
120 Chapter 6. Dynamic randomized algorithms
where the parameters t and t' stand respectively for the complexities of the
operations on dictionaries and priority queues.
Therefore, if we use perfect dynamic hashing together with stratified tree, the
expected cost of a deletion is
0 (logn + (1 + ) loglogn) .
If we use balanced binary trees, it remains
For the preceding algorithm, we have merely applied the general principles of
the augmented influence graph to the case of computing the vertical decomposi-
tion of a set of segments. In fact, in this specific case, we may derive a simpler
algorithm, yet one that uses less storage. This algorithm does not need to keep
the conflict lists and maintains a non-augmented influence graph. It is outlined in
exercises 6.1, 6.2 and 6.3, and its performances are summarized in the following
theorem:
Therefore, the expected cost of a deletion is 0 ((1 + a) log log n) if we use per-
fect dynamic hashing coupled with stratified trees. It remains 0 ((1 + a) log n)
if we use balanced binary trees.
6. 5. Exercises 121
6.5 Exercises
Exercise 6.1 (Dynamic decomposition) Let us maintain dynamically the decom-
position of a set of segments using an influence graph. Show that the creator of a new
trapezoid, or a trapezoid unhooked during a deletion, is also the creator of at least one
destroyed trapezoid.
Hint: The proof of this fact relies on the two additional properties possessed by the
influence graph of a decomposition:
1. The influence domain of an internal node is contained in the union of the influence
domains of its children.
2. If an object Ok is the determinant of an internal node, it necessarily is a determi-
nant of at least one child of this node.
Exercise 6.3 (Dynamic decomposition) The aim of this exercise is to show how we
may dynamically maintain the decomposition of a set S of segments using a simple
influence graph, without the conflict lists.
122 Chapter 6. Dynamic randomized algorithms
122 Chapter 6. Dynamic randomized algorithms
01
> Ok
9k
/
01
- V
kA') (e)
Figure 6.6. Detecting conflicts in critical zone. Region F is shaded, and region H within
is emphasized.
The segments that must be reinserted during a deletion are the creators of destroyed
regions (see exercise 6.1) and can be detected during the locating phase.
Let 01 be one of the segments to be reinserted during the deletion of Ok. To retrieve
all the critical regions that conflict with O, the algorithm considers in turn the destroyed
regions H with creator 01, and selects the critical regions F related to H by one of the
five cases described in exercise 6.2.
For this, the deletion algorithm maintains an augmented dictionary A, storing the
sequence ordered along Ok of critical regions intersected by Ok. Let H be one of the
destroyed regions, created by 01. If H has a wall that stems from a point on 01 and
butts against Ok, or a wall stemming from 01 n Ok, this wall is located in the structure
A, and the critical region containing this wall is retrieved. If H has two walls stemming
from a point on Ok and from a point on 01, the region containing the wall stemming
from the point on Ok is searched for in A, and it is selected if it also contains the wall
of H stemming from the point on 01. Lastly, if 01 and Ok support the floor and ceiling
of H, the right wall of H is searched for in A, and any critical region that intersects the
floor and the ceiling of H is selected.
1. The selected region obviously conflicts with 01. As shown in exercise 6.2, any
critical region that conflicts with H is selected. Show that such a region can be selected
at most 16 times.
To speed up the locating phase, the algorithm maintains the lists of nodes killed by
each object stored in the structure. To perform the deletion, the algorithm proceeds
along the following lines.
Locating. The algorithm traverses the influence graph starting on the nodes killed
by Ok, and visits the destroyed or unhooked nodes. During this traversal, the algorithm
sets up a dictionary D that stores the destroyed and unhooked nodes, and a list C of the
creators of the destroyed nodes.
6.6. Bibliographicalnotes 123
Rebuilding. The list £ is sorted by chronological order, for instance by storing the
elements in a priority queue, and extracting them in order. The redundant elements are
extracted only once. The dictionary A initially stores the regions killed by Ok*
The objects of £ are processed in chronological order. For each object 01, the critical
regions that conflict with Qi are selected as explained above. The remaining operations
are identical to those in the algorithm of section 6.4. The conflict lists of the new regions
do not have to be computed. On the other hand, the dictionary A must be updated.
2. Show that the performances of this algorithm are those given by theorem 6.4.2.
Exercise 6.4 (Lazy dynamic algorithms) In this exercise, we propose a lazy method
to dynamically maintain the decomposition of a set of segments. For simplicity, let us
assume that the segments do not intersect. The algorithm maintains an influence graph
in the following lazy fashion:
1. The graph is a mere influence graph, no conflict lists are needed.
2. During an insertion, the nodes corresponding to the new trapezoids are hooked to
the nodes corresponding to the killed trapezoids as in the algorithms described in
subsection 5.3.2 and section 6.4.
3. During a deletion, the nodes corresponding to the new trapezoids are hooked to
leaves of the graph that correspond to destroyed trapezoids. More precisely, a node
corresponding to a new trapezoid is hooked to leaves of the graph that correspond
to the destroyed nodes that have a non-empty intersection with the new trapezoid.
No node is removed from the graph.
4. The algorithm keeps the age of the current graph in a counter, meaning the total
number of operations (insertions and deletions) performed on this graph. Each
time the number of segments effectively present falls below half the number stored
in this counter, the algorithm builds the influence graph anew by inserting the
segments effectively present into a brand new structure.
1. Show that when 0(n) segments are stored in the structure, the expected cost of an
insertion or a location query is still O(logn).
2. The cost of the periodic recasting of the graph is shared among all the deletions.
Show that the amortized complexity of a deletion is still 0(log n) on the average. (Recall
that the segments do not intersect, by assumption.)
Hint: It will be noted that the number of children of a node in the influence graph is not
bounded any more. The analysis must then have recourse to biregions (see exercise 5.7)
to estimate the expected complexity of the locating phases.
in the plane. The algorithm by Clarkson, Mehlhorn, and Seidel [70] uses the same
approach to maintain the convex hull of a set of points in any dimension. The method
was then abstracted by Dobrindt and Yvinec [86]. A similar approach is also discussed
by Mulmuley [1761, whose book is the most comprehensive reference on this topic.
There is another way to dynamize randomized incremental algorithms. This approach,
developed by Schwarzkopf [198, 199], can be labeled as lazy. As outlined in exercise 6.4,
it consists in not removing from the structure the elements that should disappear upon
deletions. These elements are marked as destroyed, but remain physically present, and
still serve for all subsequent locating phases. Naturally, the structure may only grow.
When deletions outnumber insertions, the number of objects still present in the structure
is less than half the number of objects still stored, and the algorithm completely rebuilds
the structure from scratch, by inserting one by one the objects that were not previously
removed.
Finally, we shall only touch the topic of randomized or derandomized dynamic struc-
tures which efficiently handle repetitive queries on a given set of objects, while allowing
objects to be inserted into or deleted from this set. These structures embody the dy-
namic version of randomized divide-and-conquer structures, discussed in the notes of the
previous chapter. These dynamic versions can be found in the works by Mulmuley [175],
Mulmuley and Sen [178], Matougek and Schwarzkopf [153, 156], Agarwal, Eppstein, and
Matousek [3] and Agarwal and Matougek [4].
Part II
Convex hulls
Convexity is one of the oldest concepts in mathematics. It already appears
in the works of Archimedes, around three centuries B.C. It was not until the
1950s, however, that this theme developed widely in the works of modern math-
ematicians. Convexity is a fundamental notion for computational geometry, at
the core of many computer engineering applications, for instance in robotics,
computer graphics, or optimization.
A convex set has the basic property that it contains the segment joining any two
of its points. This property guarantees that a convex object has no hole or bump,
is not hollow, and always contains its center of gravity. Convexity is a purely affine
notion: no norm or distance is needed to express the property of being convex.
Any convex set can be expressed as the convex hull of a certain point set, that
is, the smallest convex set that contains those points. It can also be expressed
as the intersection of a set of half-spaces. In the following chapters, we will be
interested in linear convex sets. These can be defined as convex hulls of a finite
number of points, or intersections of a finite number of half-spaces. Traditionally,
a bounded linear convex set is called a polytope. We follow the tradition here, but
we understand the word polytope as a shorthand for bounded polytope. This lets
us speak of an unbounded polytope for the non-bounded intersection of a finite set
of half-spaces.
In chapter 7, we recall the definitions relevant to polytopes, their facial struc-
ture, and their combinatorial properties. We introduce the notion of polarity as
a dual transform on polytopes, and the notions of projective spaces and oriented
projective spaces to extend the above definitions and results to unbounded poly-
topes. In chapter 8, we present solutions to one of the most fundamental problems
of computational geometry, namely that of computing the convex hull of a finite
number of points. Chapter 9 contains algorithms which work only in dimension
2 or 3. Lastly, chapter 10 tackles the related linear programming problem, where
polytopes are given as intersections of a finite number of half-spaces.
Chapter 7
Polytopes
7.1 Definitions
7.1.1 Convex hulls, polytopes
H+=H+UH, H-=H-UH.
Consider a d-polytope P. A hyperplane H supports P, and is called a supporting
hyperplane of P, if H n P is not empty and P is entirely contained in one of the
closed half-spaces H+ or H-. The intersection H n P of the polytope P with
a supporting hyperplane H is called a face of the polytope P. Faces are convex
subsets of Ed, with a dimension ranging from 0 to d - 1. To these faces, called
the proper faces of 'P, we add two faces called improper: the empty face whose
dimension is set to -1 by convention, and the polytope P itself, of dimension d.
A face of dimension j is also called a j-face. A 0-face is called a vertex, a 1-face
is called an edge, and a (d - 1)-face is called a facet of the polytope.
If F is a face of P and H a supporting hyperplane of P such that F = H n P,
H is said to support P along F.
Theorem 7.1.1 The boundary of a polytope is the union of its proper faces.
Proof. Consider a polytope P. It is easy to show that the union of the faces
of P is included in the boundary of P. Indeed, let F be a face of 'P, H a
hyperplane supporting P along F, and H+ the half-space bounded by H that
contains P. Any point X in F belongs to P and to H, and a neighborhood of
this point contains points that do not belong to P. The converse inclusion (of
the boundary in the union of the proper faces) results from a general theorem
on bounded closed convex sets of Ed, stated in exercise 7.5. It is a consequence
of this theorem that there is a supporting hyperplane passing through any point
of the boundary of a polytope 'P; thus every point of the boundary belongs to a
supporting hyperplane and hence to a proper face of P. n
Theorem 7.1.2 A polytope has a finite number of faces. Faces of a polytope are
also polytopes.
Proof. Consider a polytope 'P, the convex hull conv(X) of a finite set of points
X. The theorem can be proved by showing that every proper face of P is the
convex hull of a subset of X. Indeed, let H be a supporting hyperplane of P and
let X' be the subset of the points of X that belong to H. We first show that
H nP = conv(X'). That conv(X') C HfnP is immediate. To prove the converse,
we show that any point of P that does not belong to conv(X') does not belong
to H. Let H(Y) = 0 be an equation of H and assume that P is contained in the
half-space H+ = {Y E Ed: H(Y) > 0}. For any point X' in X' or in conv(X'),
we have H(X') = 0, and for any point X in X \ X' or in conv(X \ X'), we have
H(X) > 0. Any point Y in P is a linear convex combination of points in X. If
Y does not belong to conv(X'), at least one of the coefficients of the points in
X \ X' in this combination is strictly positive, and thus H(Y) > 0. 0
130 Chapter 7. Polytopes
130 Chapter 7. Polytopes
Hi Hi1
I /
II
Figure 7.1. For the proof of theorem 7.1.3.
Proof. Let P be a polytope defined as the convex hull of a finite point set X.
By successively removing from X any point Xi that can be expressed as a linear
convex combination of the remaining points, we are left with a minimal subset X'
of X such that P = conv(X'). Let us now prove that any point of X' is a vertex of
P. Let Xi be a point of X'. Since X' is minimal, Xi does not belong to the convex
hull conv(X' \ {Xi}) of the other points, and the theorem stated in exercise 7.4
shows that there is a hyperplane Hi' that separates Xi from conv(X' \ {Xi}) (see
figure 7.1). The hyperplane Hi parallel to Hi' passing through Xi supports P and
contains only Xi among all points of X'. Now theorem 7.1.2 above shows that
Hi n P = conv({Xi}) = {Xi}.
The following two theorems are of central importance. They show that a poly-
tope might equivalently be defined as the bounded intersection of a set of closed
half-spaces.
Theorem 7.1.4 Any polytope is the intersection of a finite set of closed half-
spaces. More precisely, let P be a polytope, and {Fi: 1 < i < m} be the set of
its (d - 1)-faces, Hi the hyperplane that supports P along Fi, and Hi+ the closed
half-space bounded by Hi that contains P. Then:
m
i=1
belong to P does not belong to the intersection ni=l1 Hi. Let X be a point
not in P, and Y a point in the interior of P but not in the hyperplane passing
through X and some d - 1 vertices of P. Such a point exists, since the interior
of P is of dimension d and cannot be contained in the union of a finite number
of hyperplanes of dimension d - 1. Segment XY intersects the boundary of P in
a point Z (see figure 7.2). This point necessarily belongs to a proper face of P
and, from the choice of Y, cannot belong to a face of P of dimension j < d - 1.
Thus Z belongs to one of the facets Fi of P. Then Z belongs to the hyperplane
Hi, Y to the half-space Hi+ and X to the opposite half-space Hi-. E
Proof. The proof goes by induction on the dimension d of the space. In dimen-
sion 1, the theorem is trivial. Let
m
Q n Hi
t=1
71
From this we may conclude that Q C conv(V). And since Q is convex and
contains V, the opposite inclusion is trivial. 0
Remark. If the intersection Q is of dimension d and if its expression 7.1 is
minimal, that is, for any j = 1,.. ., m,
Q ln Hi
i54j
H~i ( )
and is therefore not empty. Indeed, the intersection nij Hi is neither empty,
nor entirely contained in H-, because Q is not empty. But this intersection is
not contained in Ht3
either, otherwise Ht3
could be removed from expression 7.1
without changing the intersection Q.
Theorem 7.1.1 shows that the boundary of a polytope is the union of its proper
faces, and the preceding remark shows that the union of the (d - 1)-faces gives
the boundary of a polytope. The following theorem shows more precisely that
any proper face of a polytope is entirely contained within a facet of the polytope.
contains all the vertices in V(P) \ V(Fj) and all the vertices in V(Fi) \ V(F 2 ). El
Proof. 1. Let {FI, F2 ,..., Fr} be a family of faces of the polytope P. Let F
be the intersection ni= Fi. If F is empty, F is trivially a face of P. Otherwise
we choose for the origin of Ed a point 0 in F. For i = 1, . .. , r, we let Hi be a
hyperplane that supports P along Fi, and Ni be the vector of Ed such that
Hi = {X E Ed: X. N, = °},
and
PCH+={XEEd: X.N>ް}.
If N = Eri=1 Ni, the hyperplane H defined by
H = {X Ed: X *N=0}
supports P along F.
2. Let {FI, F2 , .. ., Fm} be the facets of polytope P. Let {H1 , H2 , . . ., Hm} be
the hyperplanes that support P along these facets. Let F be a (d - 2)-face of P.
From theorem 7.1.6, F is a (d - 2)-face of a facet Fj of P. From theorem 7.1.5,
facet Fj can be expressed as
F3 = H3 n -P= H, n (ki&j
k)=n()nH
k54j
F=(H, HHi) ( n
k/+ {i~j
(Hj n Hk)) = Hi n H n (n
kjiji,j}
k+
or equivalently
F=Hn HI nP=FnF3.
Using the second assertion in theorem 7.1.7, it is also easy to prove by induction
on j (from j = d - 1 down to j = 0) that any j-face (O < j < d - 1) of a polytope
P is the intersection of all the (d - 1)-faces of P that contain it.
Let then j and k satisfy 0 < j < k < d - 2. Consider a j-face F of polytope
P. The intersection of all the k-faces of P that contain F is also a face of P that
contains F. To show that this face is precisely F, it suffices to show that F is
the intersection of some k-faces of P. From what was said above, F is a face of
a (k + 1)-face G of P, and thus F is the intersection of all the k-faces of G that
contain it. But k-faces of G are also k-faces of P and therefore F is indeed the
intersection of some k-faces of P. [1
Two faces F and G of a polytope P are called incident if one is included in the
other, and if their respective dimensions differ by one. Two vertices of a polytope
are said to be adjacent if they are incident to some common edge. Two facets of a
polytope are said to be adjacentif they are incident to some common (d- 2)-face.
A* = {X E Ed A *.X=1}.
Let H be a hyperplane that does not contain the origin 0. The pole of H is the
point H* that satisfies
H*.X=1, VXEH.
Lemma 7.1.8 The polarity of center 0 reverses the inclusion relationships be-
tween points and hyperplanes: a point A belongs to a hyperplane H if and only if
the pole H* of H belongs to the polar hyperplane A* of A.
136 Chapter 7. Polytopes
Proof.
A E H -t~A H* = I H* XA*
H+={XEEd: X.H*<1}
H-={X EEd: X H* > 1}
Proof.
Generally speaking, we call a duality any bijection that reverses inclusion rela-
tionships. The preceding relation shows that polarity centered at 0 is a duality,
and the polar hyperplane A* is often called the dual of A. Similarly, the pole H*
is often called the dual of hyperplane H.
The notion of duality extends naturally to polytopes: a polytope Q is dual to
a polytope P if there is a bijection between the faces of P and the faces of Q that
reverses inclusion relationships.
The following theorems show that it is possible to define a polar image P# for
any polytope P whose interior contains the origin 0.
The polar transformationcentered at 0 is closely linked to the polarity defined
above, but it associates points with half-spaces and not with hyperplanes. Let A
be a point of Ed. The polar image A# of A is the half-space A*+ bounded by A*
that contains the origin:
or I
7. 1. Definitions 137
Note that this formula allows the definition to be extended to the case where A
contains the origin 0.
The two following facts are immediate consequences of the above definition:
1. The polar image A# of a set A is convex.
2. If A and B are two sets such that A C B, then B# C A#.
In the rest of this subsection, P stands for a polytope of Ed whose interior
contains the origin 0, and P# denotes the polar image of P.
then P# is the intersection of the n half-spaces Xi+ bounded by the polar hy-
perplanes Xi of the point Xi,
n
P#= nxi*+.
Indeed, the inclusion P# C ni=l Xi+ is trivial. To prove the converse, we show
that every point that does not belong to P# does not belong to i=l Xi*+. Let
Y be a point that does not belong to P#. There is a point X that belongs to P
such that Y .X > 1. Since X is a linear convex combination of {X, ..., Xr,}, its
existence implies that Y - Xi > 1 for at least one of the points Xi, and thus Y
does not belong to Xi*.
The polar set P# of polytope P is the bounded intersection of a finite number
of half-spaces. It is thus a polytope, by theorem 7.1.4. El
Proof. For any point A of P, the closed half-space A*+ contains the polytope
'P#. Moreover, if A belongs to the boundary of P, it belongs to one proper face
F of 'P and there is a supporting hyperplane H of P that passes through A. The
pole H* of H is a point that belongs to both A* and P#. Thus A* n P# is not
empty and A* is indeed a supporting hyperplane of 'P#. 0
Theorem 7.1.13 There exists a bijection between the faces of 'P and those of
'P# which reverses inclusion relationships. This bijection associates the k-faces
of 'P with the (d-1 - k) -faces of 'P#,for all k = O. . . , d-1.
F*= n(P#nX*)
XEF
F** = F.
7. 1. Definitions 139
This, property is proved below for the proper faces of P and P#. In order to
extend it to improper faces, we note that the images of P and fP# are empty sets
because both P and 7P# have non-empty interiors. Therefore we can make the
convention that the d-dimensional face of P (resp. P#) corresponds to the empty
face of P# (resp. 7P).
Let now F be a proper face of P. Then
Finally, the following properties can be easily proved from the preceding ones.
4. If the origin 0 lies in the interior of two polytopes P1 and P2, then
By using the bijection between the faces of polytope P and its dual, we can
easily prove the following lemma which will be useful in establishing the Dehn-
Sommerville relations (theorem 7.2.2) satisfied by any simple polytope:
Lemma 7.1.14 For any 0 < j < k < d - 1, any i-face of a simple polytope P is
a face of ( dj) k-faces of P.
E (-1)knk((P) = 0.
k= -1
Proof. The proof we present here goes by induction on the dimension d of the
polytope. The base case is proved easily since, in one dimension, a polytope has
only two proper faces, namely its vertices, and thus satisfies Euler's relation.
142 Chapter 7. Polytopes
For each face F of P and each hyperplane Hj, in this family, we define a
signature: Xj(F) = 1 if Hj intersects the relative interior of F, and Xj(F) = 0
otherwise.
Consider a face F, and call P, (resp. Pm) its vertex with minimal (resp. max-
imal) xd-coordinate. The horizontal hyperplanes intersecting the relative inte-
rior of F lie strictly between horizontal hyperplanes H2 1- 1 and H2 mi-that pass
through PI and Pm respectively. If face F is of dimension k > 1, then I and m are
distinct integers, and the number of hyperplanes with even indices that intersect
the relative interior of F is one more than the number of hyperplanes with odd
indices that intersect the relative interior of F, whence
2n-2
1 = E (- 1)'X(F).
j=2
d-2 d-1
Z(_-1)kknk pj) = E(- 1)k-nk-l(Pj) = 1 - (_l)d-1. (7.3)
k=O k=1
7.2. The combinatorics of polytopes 143
It now suffices to multiply relations 7.7 and 7.8 by (-1)i and to sum over
j = 1, . . . , 2n - 1 to obtain by use of equation 7.2, noticing that there are n - 1
even and n - 2 odd relations:
d-1
Recall now that n is the number no(P) of vertices of 'P. In the last equation, we
may now recognize Euler's relation for polytope P. [1
In the case of a 2-polytope, Euler's relation, written as
no(P) - ni(P) = 0,
expresses the fact that a polygon has as many vertices as edges. In the case of a
3-polytope, the relation is a bit more interesting and can be written as
E(-')i (
j=o
d-k )7(P) = nk(P), k = O.. .. ,d.
Z
j=-l
(-1)jnj(F) = 0.
The sum
Z nj (F)
FEYk (P)
S
FcE-k (P)
nj(F)= d ) ni(P), (O< j < k < d-1).
Finally, we get
-
7.2. The combinatorics of polytopes 145
The first relation is trivial, the following two are equivalent, and the last is pre-
cisely Euler's relation. They can be compacted into two linearly independent
equations binding the numbers no, ni, and n2 of proper faces of a simple 3-
polytope. Fixing the number n = n2 of facets, these relations may be expressed
as
no=2n-4, nl=z3n-6.
This proves the following theorem:
The following subsection shows that the Dehn-Sommerville relations alone can
be used to derive an upper bound on the number of faces of any polytope as a
function of its number of vertices or facets.
Theorem 7.2.5 (Upper bound theorem) Any d-polytope with n facets (or n
vertices) has at most O(n[d/ 2 i) faces of all dimensions and O(nLd/ 2 ]) pairs of
incident faces of all dimensions.
yield d + 1 linear relations between the d numbers no, n 1 ,. . . , nd-1 of proper faces
of polytope P. The first relation (obtained for k = 0) is trivial, and the others
are not all linearly independent. But one may prove easily that the odd relations
(those that correspond to odd values of k) are linearly independent. Indeed, the
coefficients of n2p+l in the equations obtained for k = 2q+ 1, with p and q ranging
from 0 to [4- 1 j, form a triangular matrix. Thus the Dehn-Sommerville relations
form a system of rank at least
r=L + 1j.
146 Chapter 7. Polytopes
In fact, it can be shown that there are exactly r linearly independent relations
among the Dehn-Sommerville relations (see exercise 7.7). Moreover, it can be
shown that the Dehn-Somerville system can be solved for the variables nj, j =
0 ... ., r - 1, yielding an expression for these variables as a linear combination of
the nj's, j = r, . .. , d (see exercise 7.8). If the simple polytope has n facets, there
is a trivial bound, for j > r,
( n j )=O(n d-j)
on its number of j-faces. Indeed, lemma 7.1.14 shows that a j-face of a simple d-
polytope is the intersection of d - j facets. We conclude that a simple d-polytope
with n facets has 0(nLd/2j) faces. In a simple polytope, k-faces (k < d) are
incident to d - k (k + 1)-faces; thus the number of pairs of incident faces is also
0(0Ld/2j). We therefore have proved the theorem for a simple polytope with n
facets.
A dual statement of the theorem also shows that the theorem is true for sim-
plicial d-polytopes with n vertices. To extend this result to arbitrary polytopes,
it suffices to show that simple and simplicial polytopes maximize the number of
faces and incidences between faces. The following perturbation argument shows
that the numbers of faces and incidences of faces of a non-simplicial d-polytope
are less than those of some simplicial d-polytope obtained by slightly perturb-
ing the vertices. Let P be a non-simplicial d-polytope, and n be the number of
its vertices. Each face of P is the convex hull of its vertices and may therefore
be triangulated, or in other words decomposed into a union of simplices whose
vertices are the vertices of that face. In a triangulation,1 each face F of P is ex-
pressed as the union of simplices whose relative interiors form a partition of F. A
simple scheme to triangulate a d-polytope and its faces is to proceed recursively,
or equivalently in a bottom-up fashion, as follows. Let F be a (k + 1)-face of P.
To triangulate F, we choose a vertex A of F, and consider the (k + 1)-simplices
conv(A, T), where T ranges over the k-simplices in the recursively obtained trian-
gulation of the k-faces of F which do not contain A. The number of faces of the
triangulation is at least the number of faces of P. Slightly perturbing the vertices
of P while keeping the union of the simplices in the triangulation convex (and
this can always be done, see exercise 7.10) yields a simplicial polytope P' whose
faces are in one-to-one correspondence with the simplices in the triangulation of
P. The numbers of faces and incidences of P' are thus strictly greater than their
counterparts for P.
In this subsection, we prove that the bound given in the upper bound theorem
(theorem 7.2.5) is optimal. For this, we introduce a particular class of polytopes,
and show that their numbers of faces and incidences achieve the bound given in
the upper bound theorem.
The moment curve is the curve Md in Ed followed by a point MT parameterized
by a real number T:
Md {M(-T) = (T, T2,. .. ,Td),T E RI}.
Lemma 7.2.6 Any subset of k < (d + 1) points on the moment curve is linearly
independent.
Proof. Consider d+1 points {Mo, M1 , .. ., Md} on the moment curve, for the val-
ues {TO, Ti, . . ., rd} of the parameter. The determinant formed by the coordinates
of these points is
ro r2 __ od
To T02 ... Td
12ITi = (Td -Ti)
Td T2,,Tdd O<i<j<d
1rd Td ... d
the so-called Van Der Monde determinant, and does not vanish when the Ti's are
pairwise distinct. 5
A consequence of this lemma is that any hyperplane in Ed intersects the moment
curve in at most d points.
A cyclic polytope in Ed is the convex hull of n > d + 1 points on the moment
curve. By the above lemma, a cyclic polytope is simplicial.
Let now P be a cyclic polytope in Ed, the convex hull of n points {M 1 , M2 ,
... , Mn} of Md with respective parameters {T1 T2, ....., r}. Let I a subset of the
set of indices {1, 2,.. . , n}, of cardinality k < d/2, and consider the polynomial
Theorem 7.2.8 For any integer n > d + 1, there is a polytope in Ed that has n
facets and exactly ( n) (d - k)-faces, for all 0 < k < d/2.
L(X)
- I N
XEd
L(X
X /
Sometimes it can help to represent the projective space pd as the set of antipo-
dal (i.e. diametrically opposite) pairs of points on a sphere Sd in Ed+1 centered
at the origin Q. The point X of pd corresponding to the affine line L(X) in Ed+l
can be represented as the pair of points at the intersection of L(X) and Sd. In
this representation, k-subspaces of pd are represented by great k-spheres of Sd,
which are intersections of Sd with affine (k + 1)-subspaces of Ed+1 that contain
Q. The hyperplane at infinity Hoo corresponds to the great (d - 1)-sphere of Sd
in a hyperplane parallel to Ed. The function induced by this representation maps
a point X in pd not in Ho, to the point X = L(X) n Ed of Ed, and is commonly
referred to as the central projection (see figure 7.5).
Homogeneous coordinates
We must note at this point that the equivalence relation 'R used in the definition
of pd is compatible neither with the affine structure nor with the vector-space
structure of Ed+l. Indeed, if XI, X2, YE Y 2 are points in Ed+l, it may happen
that XN 11Z 2 and YlTZYI2 , yet (XI + Y 1 ) R. (X2 + Y2) does not hold. As
a consequence, the projective space pd is neither an affine space, nor a vector
space.
Nevertheless, any basis of Ed+1 can be used as a coordinate system for Pd:
we represent point X as a (d + 1)-tuple (X1 , . .., Xd+1) of reals, the coordinates
of some point in Ed+i on the line L(X). This (d + 1)-tuple (XI,... ,Xd+l) is
not uniquely defined, yet it is unique up to a non-null multiplicative factor, and
constitutes the homogeneous coordinates of X. Any projective hyperplane H
can be described as the set of projective points whose homogeneous coordinates
satisfy a linear equation
d+1
E hixi = 0
i=l
whose coefficients are unique up to a multiplicative factor.
7.3. Projective polytopes, unbounded polytopes 151
Projective mappings
In a projective space, the hyperplane at infinity is like any other hyperplane and
plays no particular role. In general, the properties of a projective space pd are
invariant under any linear map X ) XT whose matrix T is non-singular.
Such a mapping is called a projective mapping. It transforms a k-dimensional
projective subspace into another projective subspace of the same dimension. The
hyperplane at infinity may be mapped onto any hyperplane of pd by a suitable
projective mapping.
Polarity, duality
Any hyperplane H in a projective space has a homogeneous equation of the kind
d+1
H=f{X: Zhixi= 01.
where Rd stands for the d x d identity matrix. Let H* be the projective point
(hi, .. ., hd, -hd+l). The homogeneous equation of H can be rewritten in matrix
form
H = {X: H*SXt = 0}.
Point H* is the pole of hyperplane H. Conversely, to any projective point P with
homogeneous coordinates (Pi, ... ,Pd+1) there corresponds a polar hyperplane P*
with homogeneous equation
P* = {X: PSX t = 0}.
152 Chapter 7. Polytopes
This double correspondence between points and hyperplanes is called the polar-
ity centered at 0. It is exactly the extension to projective spaces of the polarity
centered at 0 described for Euclidean spaces in subsection 7.1.3. In a Euclidean
space, the polarity centered at 0 maps points other than 0 to hyperplanes that
do not pass through 0. In a projective space, the polarity centered at 0 maps
points to hyperplanes, in a one-to-one fashion without restrictions: the projective
point 0 (corresponding to the center 0) is mapped to the polar hyperplane at
infinity Hoo, and the pole of a hyperplane H that passes through 0 is the point
at infinity in the direction normal to the hyperplane H. In the projective space,
as in its Euclidean counterpart, the polarity centered at 0 is an involution, that
is,
P** = P and H** = H,
and reverses inclusion relationships, that is,
P E H -: H* E P*.
Polarity is therefore a duality.
More generally, for any symmetric non-singular (d + 1) x (d + 1) matrix AB,
we consider the mapping that maps a point P to the hyperplane P* satisfying
P*= {X : PAXt = 0, } and a hyperplane H to the point H* satisfying
H = {X : H*ABX t = O}. This mapping is an involution between points and
hyperplanes, therefore is one-to-one, and reverses inclusion relationships. The set
B of those projective points X that satisfy
XABXt = 0
corresponds to a quadric 1 in Ed, and the duality just defined is called the polarity
with respect to B. Using this terminology, the polarity centered at 0 is the polarity
with respect to the unit sphere Sd-i centered at 0. The signatureof the quadric
B is the set of signs of its eigenvalues. In fact, it can be shown that in a projective
space, two quadrics with the same signature or with opposite signatures can be
derived from one another by a projective mapping. The corresponding polarities
are called equivalent.
Besides the polarity centered at 0, one of the polarities most widely used in
computational geometry is that with respect to the unit paraboloid, Pd-1, with
Cartesian equation in Ed
d-1
Xd i
i=l
and homogeneous equation in pd
/ d-1 - 0 0 w
XA-pXt = O with A~p = | 0 -1/2 .
0 -1/2 0
7.3. Projective polytopes, unbounded polytopes 153
The paraboloid Pd-i can therefore be derived from the unit sphere Sd-i by a
projective mapping sending the center 0 of Sd_1 to infinity along the xd-axis. The
polarity with respect to Pd-i is therefore projectively equivalent to the polarity
centered at 0. For more details on this polarity, see exercises 7.13 and 7.14.
Motivation
arcs. There is no way to identify one of these two projective arcs as being the
segment that joins P and Q.
Without segments, we certainly cannot define what it means for a set to be
convex, nor what the convex hull of a set of points is.
About half-spaces. Let us consider a hyperplane H in the projective
space pd, with homogeneous equation H*SXt = 0. If X does not belong to
H, the sign of the bilinear homogeneous form H*SXt is arbitrary and without
significance since the homogeneous coordinates are defined up to a multiplicative
factor (of either sign). It is therefore impossible to locate the point P on either
side of H. In fact, a projective hyperplane does not separate the space into two
disconnected half-spaces. In the spherical model, a hyperplane is represented by
a great (d - 1)-sphere of Sd. Each projective point P is represented as a pair
(P, -,P) of two antipodal points on Sd, and each of these points belongs to a
different hemisphere determined by H.
Oriented projective geometry remedies this situation while keeping the advan-
tages of projective geometry.
Definition
For each vector V of a vector space, the set {AV : A E R, A > 0} is an oriented
vector line. An oriented projective space of dimension d consists of oriented lines
of a vector space Vd+1 of dimension d + 1. A subspace of this space consists of
the oriented lines lying in a subspace of Vd+l.
More concretely, the oriented projective space pd that extends the affine space
Ed can be described in terms of the embedding of Ed in the space Ed+1. As before,
we let the origin Q be a point of Ed+1 not in the hyperplane that we consider as
Ed. The oriented projective space pd is the set of all rays cast from Q in Ed+l,
or equivalently the set of equivalence classes of the points in Ed+1 \ {Q} for the
relation 7?o defined by: X ZoX' if there exists A > 0 such that X = AX'. Thus, a
point in the projective space corresponds to two points in the oriented projective
space, which are then called opposite points. In the spherical representation, the
oriented projective space amounts to distinguishing the two points in an antipodal
pair of Sd.
When a basis of Ed+1 is understood, a point in the oriented projective space
has a vector of homogeneous coordinates which is defined up to a positive mul-
tiplicative factor. In the rest of this chapter, we denote by P either a point in
the oriented projective space or its vector (P1,P2, -,Pd+1) of homogeneous co-
. .
where [Ao, Al, . .- , Ad-1, X] is the determinant of the matrix whose coefficients
are the homogeneous coordinates of {Ao, A1 ... , Ad-L, X}. The coefficients
(hi, .. ., hd+
0 ) in the homogeneous equation Ed+' hixi = 0 defining H are thus
defined up to a positive multiplicative factor. It is possible to determine two
classes between the points in Pd \ H, and an oriented projective hyperplane
separates the space into two half-spaces
= {X
H+ H-= { E Pd
E Pd [AOdAl,...,Ad .,X]X] <
[Ao, Al,-..., Ad-1, > 0},
0}.
2
For instance, for any (k + 1)-tuple {Ao, A 1 ,..., Ak} of independent points in F, the vec-
tors generating the oriented vector lines of Ed+1 corresponding to {Ao,A 1 ,...,Ak} form a
coordinate system for F.
156 Chapter 7. Polytopes
Duality
The notion of duality can be extended without problems to the oriented projective
space. The oriented projective point H* defined by
is the pole of the oriented projective hyperplane H for the polarity centered at
0. Likewise, H is the polar hyperplane of H*. The pole of the hyperplane -'H
with the opposite orientation is the point opposite to the pole of H. Polarity re-
verses the inclusion relationships between points and hyperplanes and, moreover,
reverses the relative positions of a point and a hyperplane, that is
P EH H*SPt = 0 PSH*t = 0 H* G P*
P e H+ H*SPt <O PSH*t < 0 H* E P*+
P E H- H*SPt >O PSH*t > 0 H* E P*-.
H+ = {X E Pd : Xd+1 > O}
We may also define the notion of simplex in an oriented projective space. Let
{Po, P1 , . .. , Pk4 be a set of k + 1 independent points in IPo. This set of points
7.3. Projective polytopes, unbounded polytopes 157
+- n H,;
!+ni;
Proof. Let P and Q be two points in IP0, not opposite to one another. If P and
Q both belong to one of the half-spaces Ho or Hoo, then segment PQ of pd
projects onto segment PQ in Ed. Otherwise, since P is not opposite to Q, there
is a hyperplane H such that P and Q lie on the same side of H. The projective
mapping sending H to H, transforms segment PQ into a segment P'Q' which
projects onto segment P'Q' in Ed. 0
Defined this way, convex sets include segments, simplices, and open half-spaces;
antipodal pairs of points, closed half-spaces, projective subspaces, and the entire
oriented projective space are quasi-convex.
The notions of quasi-convexity and convexity are invariant under projective
mapping. The intersection of quasi-convex sets is quasi-convex, and the intersec-
tion of convex sets is convex.
Projective polytopes
The quasi-convex hull of a set of points in Pd is the smallest quasi-convex set
that contains that set. The quasi-convex hull is not always convex, but it is
convex when the set of points is contained within an open half-space of Pd. In
this case, we may speak of the convex hull of the set of points. Quasi-convex and
convex hulls consist of all linear combinations of the points with non-negative
coefficients. A projective polytope is the convex hull of a finite set of points which
is entirely contained in an open half-space.
The notions of supporting hyperplanes and faces can be carried over to the pro-
jective setting without problems. The above correspondence therefore establishes
a one-to-one correspondence between the faces of the polytopes P and P", which
also allows us to transfer to projective polytopes the combinatorial properties of
Euclidean polytopes. All the theorems in sections 7.1 and 7.2 can therefore be
7.3. Projective polytopes, unbounded polytopes 159
stated for projective polytopes. Here, we only give the projective statements of
theorems 7.1.4 and 7.1.5, which concern the polar transformations.
A set 1t of projective hyperplanes in Pd is in generalposition if, for any j < d,
the intersection of any j of them is a projective subspace of dimension d -j,
and if moreover the intersection of any d + 1 of them is empty. The intersection
of m closed projective half-spaces nl 1 Ht is contained in an open projective
half-space if and only if there is a subset of d + 1 hyperplanes in general position
among the hyperplanes Hj bounding all the half-spaces: such an intersection is
called non-trivial. Theorems 7.1.4 and 7.1.5 can now be restated in a projective
setting:
In the oriented projective space, the polarity centered at 0 (or any other po-
larity, for that matter) can be used to define an involutive one-to-one mapping
on the set of all projective polytopes, without anyjrestrictions. The polar image
A# of a polar point A is the closed half-space A*+ defined by
Let now
'P = conv(Pi, . . ., Pn)
be a projective polytope. For each i = 1,...,n, we denote by Pi* the polar
hyperplane of Pi and by Pi+ = Pi# the polar half-space of Pi*. The polar
image of the polytope P is the intersection
n -
'P#nPi*+.
i=1
(a) (b)
Unbounded polytopes
P= nHi+
j=1
in Ed. On the other hand, if 'P intersects Hoo, it projects onto the union of two
linear convex unbounded subsets
(n 7 U (nH-
m
Q= ( H)fn Hi
j=1
Conversely, let
m
Q=fnHi
j=1
7.4 Exercises
Exercise 7.1 (Radon's theorem) Show that any set X of at least d + 2 points of Ed
can be split into two subsets Xl and X2, such that conv(Xl) n conv(X 2 ) #' 0.
EAiXi = 0.
L=1
For Xl (resp. X2), choose the points Xi whose coefficients Ai in the above relation are
positive (resp. negative or zero).
Exercise 7.2 (Helly's theorem) Let {QC 1 , ./.. , Ir} be a family of r convex sets of Ed.
Show that if any d + 1 convex sets have a non-empty intersection, then so does the whole
family.
Hint: One possible proof goes by induction on r. By induction, we know that there is a
point Xi in the intersection nfl#i )Ci, for all i = 1,. . . , r. Then use Radon's theorem on
the set {Xi : i = 1, .. . , r} to construct a point X that belongs to all the sets ki.
Exercise 7.3 (Caratheodory's theorem) Show that the convex hull of a subset X of
Ed can be described as the set of all possible convex linear combinations of d + 1 points
of X. Use this to show that every polytope is a finite union of simplices.
Hint: Let conv(X) be the convex hull of a subset X of Ed and X a point in conv(X)
given by a minimal convex linear combination X = `=1 AiXi. If r > d + 1, the points
Xi are not independent. Use this to show that we may remove one of the points from
the combination, and that it is therefore not minimal.
7-4. Exercises 163
Hint: First show that for any point X V AC, there is a unique point D(X) of K such that
VX K, D(X) X',
where X' is the unique point of ACsuch that
Exercise 7.6 (Simplices) Show that simplices are the only polytopes which are both
simple and simplicial.
Exercise 7.8 (The upper bound theorem) Let P be a simplicial d-polytope and let
nj = nj (P) denote the number of j-faces of P. Show that the Dehn-Sommerville relations
on the numbers nk can be solved for the numbers nj, j = 0,..., [4-d1, yielding those
numbers as linear combinations of the numbers nj with j = |d] .... d.
Hint: Given integers r > 1, d > 2r -2, let D(r, d) be the r x r determinant
r d 1 d1> Id-r+l0
t r -1)Jtr1J
d
r --2) r-2
- (
-
r )
Exercise 7.9 (Euler's relation) Show that Euler's relation is the only non-trivial lin-
ear relation satisfied by the numbers nk(P) (O < k < d - 1) of faces of any d-polytope.
E Aj nj (P) = Ad
j=O
Exercise 7.11 (Maximal polytope) Show that there exists a polytope with n vertices
on a sphere, or on a paraboloid, with maximal complexity Q(nLd/2] ).
Hint: In the Euclidean space Ed, when d is even (d = 2p), we consider the curve M'd on
the unit sphere, parameterized by
1
M' = {M(r) = - (sin(T), cos(r), sin(2r), cos(2r), .. ., sin(pr), cos(pr)), r E [0, 7r/2]}.
O<i<j<d
1 cos(7 2 p) sin(r2p) ... cos(pr 2 p) sin(pr 2 p)
166 Chapter 7. Polytopes
show that the convex hull of n points on this curve, parameterized respectively by
{r 1 , r2, ... , n}, is a polytope whose faces are in one-to-one correspondence with those of
a cyclic polytope (introduced in subsection 7.2.4). Conclude that it is possible to build
a maximal polytope whose vertices lie on the unit sphere of Ed, with exactly ( k)
(k - 1)-faces for any k, 1 < k < d/2.
By considering the projective mapping that sends the unit sphere of Ed onto the unit
paraboloid in Ed, with equation
d-1
Xd ZExi,
i=l
show that it is possible to build a maximal polytope whose vertices are on the unit
paraboloid of Ed.
Exercise 7.12 (Upper bound theorem) This exercise presents a very simple proof
of the upper bound theorem. This proof considers a polytope, given as the intersection
of n half-spaces in Ed bounded by hyperplanes in general position, and shows that the
number of vertices of this polytope is O(nJ14i).
1. Show that any vertex of the polytope is the vertex that has the minimal or maximal
Xd-coordinate in a k-face, for some k > [d] For this, we consider a vertex P of the
polytope. This vertex is incident to d edges, at least [d] of which are contained in the
half-space Xd > Xd(P) or the half-space Xd < Xd(P).
2. Note that a face has a unique vertex with maximal Xd-coordinate, and a unique
vertex with minimal Xd-coordinate. Recall the bound of (d-k) on the number of
faces of dimension k of a polytope given by the intersection of n half-spaces in Ed and
conclude.
Exercise 7.13 (Polarity with respect to a paraboloid) Consider the polarity with
respect to the unit paraboloid P with homogeneous equation
Ed-1 0 °
XApXt = 0 with ( 01 0 1/2
\ -1/2 0
where Ed-1 is the (d -1) x (d - 1) identity matrix. Show that the restriction of this
polarity to the Euclidean space maps a point P in Ed with coordinates (P1,P2, Pd)
to the hyperplane P* in Ed with equation
d-1
Xd = 2 PiXi -Pd,
PE H H*E P*.
P E H+ H* e P*+
P c H- H* E P*-.
Exercise 7.14 (Lower convex hull) Let {P1 , P2 ,... ., P } be a set of points in Ed and
O' be a point on the Xd-axis, with Xd > 0 large enough such that the facial structure
of conv(O', P1 ,P 2, ... ,PP) is stable as O' goes to infinity along the Xd-axis. We call
lower convex hull of {P1 , P2 ,. .. , Pn}, and we denote by convs(Pl, P2 ,... aPn), the set of
faces of conv(O', P1 , P2 , .. ., Pn) which do not contain 0'. Using the oriented projective
space and the polarity with respect to the unit paraboloid P studied in exercise 7.13, show
that there is a one-to-one correspondence between the faces of conv (P1 , P2 , ... P Pn) and
those of the unbounded intersection fn= Pi*+, where the half-spaces Pi*+ are defined as
in exercise 7.13.
Exercise 7.15 (Euler's relation) Show that Euler's relation for an unbounded poly-
tope of Ed can be expressed as
d
EZi)knk(P) = 0,
k=O
A(DB={A+B: AeA,BCB}.
To compute the convex hull of a finite set of points is a classical problem in com-
putational geometry. In two dimensions, there are several algorithms that solve
this problem in an optimal way. In three dimensions, the problem is consider-
ably more difficult. As for the general case of any dimension, it was not until
1991 that a deterministic optimal algorithm was designed. In dimensions higher
than 3, the method most commonly used is the incremental method. The algo-
rithms described in this chapter are also incremental and work in any dimension.
Methods specific to two or three dimensions will be given in the next chapter.
Before presenting the algorithms, section 8.1 details the representation of poly-
topes as data structures. Section 8.2 shows a lower bound of Q(n log n + nLd/ 2 i )
for computing the convex hull of n points in d dimensions. The basic operation
used by an incremental algorithm is: given a polytope C and a point P, derive the
representation of the polytope conv(C U {P}} assuming the representation of C
has already been computed. Section 8.3 studies the geometric part of this prob-
lem. Section 8.4 shows a deterministic algorithm to compute the convex hull of n
points in d dimensions. This algorithm requires preliminary knowledge of all the
points: it is an off-line algorithm. Its complexity is O(n log n + nL(d+l)/ 2 i), which
is optimal only in even dimensions. In section 8.5, the influence graph method
explained in section 5.3 is used to obtain a semi-dynamic algorithm which al-
lows the points to be inserted on-line. The randomized analysis of this algorithm
shows that its average complexity is optimal in all dimensions. Finally, section 8.6
shows how to adapt the augmented influence graph method of chapter 6 to yield
a fully dynamic algorithm for the convex hull problem, allowing points to be in-
serted or deleted on-line. The expected complexity of an insertion or deletion is
O(logn + nL[d/2 -l), which is optimal.
Throughout this chapter, we assume that the set of points whose convex hull is
to be computed is in general position. This means that any subset of k + 1 < d + 1
points generates an affine subspace of dimension k. This hypothesis is not crucial
170 Chapter 8. Incremental convex hulls
170 Chapter 8. Incremental convex hulls
for the deterministic algorithm (see exercise 8.4), but it allows us to simplify the
description of the algorithm and to focus on the central ideas. It becomes an
essential assumption, however, for the randomized analyses of the on-line and
dynamic algorithms.
Proof. Subsection 7.2.4 shows that the convex hull of n points in the Euclidean
space Ed may have Q(nLd/2 J) faces. In any dimension, Q(nLd/ 2j) is thus a trivial
lower bound for the complexity of computing convex hulls. In two dimensions, the
lower bound Q (n log n) is a consequence of theorem 8.2.2 proved below. Finally,
any set of points in E2 can be embedded into E3 , so the complexity of computing
convex hulls in E3 cannot be smaller than in E2 . [:
Proof. Consider n real numbers x1 , x2, .. ., X,, which we want to sort. One way
to do this is to map the number xi to the point Ai with coordinates (xi, x?) on
the parabola with equation y = x2 (see figure 8.2). The convex hull of the set
of points {Ai : i = 1,...,n} is a cyclic 2-polytope, and the list of its vertices
is exactly the list of the vertices {Ai : i = 1,...,n} ordered according to their
increasing abscissae. El
45
XI X2 z3 X4 X5
Figure 8.2. Transforming a sorting problem into a convex hull problem in two dimensions.
Suppose that point P and polytope C are in general position, meaning that P
and the vertices of C form a set of points in general position. The facets of C
can then be separated into two classes with respect to P. Let F be a facet of C,
HF the hyperplane that supports C along F, and HF+ (resp. HF) the half-space
bounded by HF that contains (resp. does not contain) C. The facet F is red with
respect to P if it is visible from point P, that is if P belongs to the half-space
Hi. It is colored blue if P belongs to HF+. From the general position assumption,
it follows that P never belongs to the supporting hyperplane HF and therefore
every facet of C is either red or blue with respect to P.
Using theorem 7.1.7, any face of C is the intersection of the facets of C which
contain it. The faces of C of dimension strictly smaller than d- 1 can be separated
into three categories with respect to P: a face of C is red if it is the intersection
8.3. Geometric preliminaries 173
of red facets only, blue if it is the intersection of blue facets only, or purple if it is
the intersection of red and blue facets.
Intuitively, the red faces are those that would be lit if a point source of light
was shining from P, the blue faces are those that would remain in the shadow,
and the purple faces would be lit by rays tangent to C. In figure 8.3, the blue
faces of C are shaded, the red edges are outlined in dashed lines, and the purple
edges are shown in bold.
Lemma 8.3.1 Let C be a polytope and P a point in general position with respect
to C. Every face of conv(C U {P}) is either a blue or purple face of C, or the
convex hull conv(G U {P}) of P and a purple face G of C.
Proof. Note that if P belongs to C, all the facets of C are blue with respect to
C (theorem 7.1.4) and the content of the lemma is trivial.
In the other case, we first show that a blue face of C is a face of
conv(C U {P}). Let F be a facet of C that is blue with respect to P. Since
P belongs to the half-space H+, the hyperplane HF which supports C along F
also supports conv(C U {P}) and conv(C U {P}) n HF = F, which proves that
F is indeed a facet of conv(C U {P}). Any blue facet of C is thus a facet of
conv(C U {P}). Any blue face of C, being the intersection of blue facets of C, is
also the intersection of facets of conv(C U {P}): therefore a blue face of C is also
a face of conv(C U {P}) (theorem 7.1.7).
Next we show that, for any purple face G of C, G and conv(G U {P}) are
faces of conv(C U {P}). If G is a purple face of C, then there is at least one
red facet of C, say F1 , and one blue facet of C, say F2 , that both contain G
(see figure 8.4). Let H1 (resp. H2 ) be the hyperplane supporting C along F1
(resp. F2 ). Point P belongs to the half-space H+ which contains C, and since
Hlnconv(CU{P}) = G we have shown that G is a face of conv(CU{P}). Point P
also belongs to the half-space Hj- that does not contain C. Imagine a hyperplane
that rotates around H1 n H2 while supporting C along G. There is a position
H for which this hyperplane passes through point P. Hyperplane H supports
conv(C U {P}), and since conv(C U {P}) n H = conv(G U {P}), we have proved
that conv(G U {P}) is a face of conv(C U {P}).
Finally, let us show that every face of conv(C U {P}) is either a blue or a purple
face of C, or the convex hull conv(G U {P}) of P and of a purple face G of C.
Indeed, a hyperplane that supports conv(CU{P}) is also a supporting hyperplane
of C, unless it intersects conv(C U {P}) only at point P. As a consequence, any
face of conv(C U {P}) that does not contain P is a (blue or purple) face of C, and
any face conv(C U {P}) that contains P is of the form conv(G U {P}) where G
is a purple face of C. Note that the vertex P of conv(C U {P}) is also a face of
the form conv(G U {P}) obtained when G is the empty face of C. Indeed, when
174 Chapter 8. Incremental convex hulls
174 Chapter 8. Incremental convex hulls
H2
/
P does not belong to C, C necessarily has some facets that are blue and some
facets that are red with respect to P. The empty face, being the intersection of
all faces of C, is therefore purple. O
The following lemma, whose proof is straightforward, investigates the incidence
relationships between the faces of C and those of conv(C U {P}).
Lemma 8.3.2 Let C be a polytope and P a point in general position with respect
to C.
* If F and G are two incident faces of polytope C, either blue or purple with
respect to P, then F and G are incident faces of conv(C U {P}).
* If G is a purple face of C, then G and conv(G U {P}) are incident faces of
conv(C U {P}).
* Finally, if F and G are incident purple faces of .F, then conv(F U {P}) and
conv(G U {P}) are incident faces of conv(C U {P}).
Recall that two facets of a polytope C are adjacent if they are incident to the
same (d - 2)-face and that the adjacency graph of a polytope stores a node for
each facet and an arc for each pair of adjacent facets.1 We say that a subset
of facets of a polytope C is connected if it induces a connected subgraph of the
adjacency graph of C.
Lemma 8.3.3 Consider a polytope C and a point P in general position. The set
of facets of C that are red with respect to P is connected, and the set of facets of
C that are blue with respect to P is also connected.
'Two facets sharing a common k-face, k < d - 2, may be not adjacent, even though they
are connected as a topological subset of the boundary of the polytope. Such a situation is only
possible in dimension d > 3.
8.3. Geometric preliminaries 175
8.3. Geometric preliminaries 175
Figure 8.5. Isomorphism between the purple faces and the faces of a (d -l)-polytope.
Proof. If P belongs to C, the set of the red facets is empty, any facet is blue,
and the lemma is trivial. We will therefore assume that P does not belong to C.
The connectedness of the set of red facets can be proved easily in two dimen-
sions. Indeed, the polytope conv(C U {P}) has two edges incident to P. By
lemma 8.3.1, there are exactly two purple vertices of C with respect to P. Hence,
the adjacency graph of the 2-polytope C is a cycle that has exactly two arcs
connecting a blue and a red facet.
Let us now discuss the case of dimension d, and suppose for a contradiction that
the set of facets of C that are red with respect to P is not connected. Therefore,
we may choose two points Q and R on two facets of C that belong to two distinct
connected components of the set of red facets of C. Let H be the affine 2-space
passing through points P, Q, and R. This plane intersects polytope C along a
2-polytope It n H. The edges of C n H that are red with respect to P are exactly
the intersections of the red facets of C with H. The points Q and R belong to two
separate connected components of the set of red edges of C n H. Connectedness
of the set of red faces of a 2-polytope would then not hold, a contradiction.
Analogous arguments prove the connectedness of the set of facets of
conv(C U {P}) that are blue with respect to P. E
Finally, the lemma below completely characterizes the subgraph of the inci-
dence graph induced on the faces of C that are purple with respect to P.
Lemma 8.3.4 Let C be a polytope and P a point in general position with respect
to C. If C has n vertices and does not contain P, then the set of the properfaces of
C that are purple with respect to P is isomorphic, for the incidence relationship,
to the set of faces of a (d - 1)-polytope whose number of vertices is at most n.
Proof. From lemma 8.3.1, we know that the faces of polytope C that are purple
with respect to P are in one-to-one correspondence with the faces of conv(CU{P})
176 Chapter 8. Incremental convex hulls
that do not contain P. Since point P does not belong to C, there must be
a hyperplane H which separates P from C (see exercise 7.4). Hyperplane H
intersects all the faces of conv(C U {P}) that contain P except for the vertex P,
and those faces only. Moreover, the traces in H of the faces of conv(C U{P}) are
the proper faces of the (d - 1)-polytope conv(C U{P}) n H, and the traces in H
of incident faces of conv(C U {P}) are incident faces of conv(C U{P}) n H. Thus,
the incidence graph of the (d - 1)-polytope conv(C U {P}) n H is isomorphic to
the subgraph of the incidence graph of conv(C U {P}) induced by the faces that
contain vertex P. Lemmas 8.3.1 and 8.3.2 show that this subgraph is isomorphic
to the subgraph of the incidence graph of P induced by the faces of C that are
purple with respect to P. Lastly, the vertices of polytope conv(C U{P}) n H are
the traces in H of the edges of conv(C U {P}) incident to vertex P, and their
number is at most n. L
2. Initialize the convex hull to the simplex conv(Ad+l), the convex hull of the
first d + 1 points of A.
3. In the incremental step: the convex hull of conv(Ai) is built knowing the
convex hull conv(Ai-1) and the point Ai to be inserted.
Phase 1. We first identify a facet of conv(Ai-1) that is red with respect to Ai.
Phase 2. The red facets and the red or purple (d - 2)-faces of conv(Ai-1) are
traversed. A separate list is set up for the red facets, the red (d - 2)-faces,
and the purple (d - 2)-faces.
Phase 3. Using the information gathered in phase 2, we identify all the other
red or purple faces of conv(Ai-1). For each dimension k, d - 3 > k > 0O
a list lRk of the red k-faces is computed, as well as a list Pk of the purple
k-faces.
Phase 4. The incidence graph is updated.
Before giving all the details for each phase, let us first describe precisely the
data structure that stores the incidence graph. For each face F of dimension k
(O < k < d -1) of the convex hull, this data structure stores:
* the list of the sub-faces of F, which are the faces of dimension k - 1 incident
to F,
* the list of the super-faces of F, which are the faces of dimension k + 1
incident to F,
* the color of the face (red, blue, purple) in the current step, and
* a pointer p(F) whose use will very soon be clarified.
H-
Ai
4i-1
Figure 8.6. One of the facets of conv(Ai- 1 ) containing Ai-, must be red with respect to Ai.
the adjacency graph2 of conv(Ai-1), starting with the initial red facet that was
found in phase 1, visits all the facets visible from Ai, which we color red, and
their (d - 2)-faces, which we color red if they are incident to two red facets, or
purple if they are incident to a blue facet. The traversal backtracks whenever the
facet encountered was already colored red, or if it is a blue facet.
Phase 3. We now know all the red and purple (d - 2)-faces, and the red facets.
In this phase, all the remaining red and purple faces are colored, and their lists
are set up in order of decreasing dimensions. Assume inductively that all the red
and purple faces of dimension k' > k + 1 have already been identified and colored,
and that the lists lRk' and Pk, have already been set up. We process the k-faces in
the following way. Each sub-face of a face of Pk+, that has not yet been colored
is colored purple and added to the list Pk. Afterwards, each sub-face of Zk+1
that has not yet been colored is added to the list Rk.
Phase 4. To update the incidence graph, we proceed as follows. All the red
faces are removed from the incidence graph, and so are all the arcs adjacent to
these faces in the graph. The purple faces are processed in order of increasing
dimension k. If F is a k-face purple with respect to P, a new node is created for
the (k + 1)-face conv(F U {Ai}) and linked by an arc to the node for F in the
incidence graph. Also the pointer p(F) is set to point to the new node created
for conv(F U {Ai}). It remains to link this node to all the incident k-faces of
the form conv(G U {Ai}), where G is a (k - 1)-face incident to F. For each sub-
face G of F, its pointer p(G) gives a direct access to the node corresponding to
conv(G U {Ai}), and the incidence arc can be created.
2
The adjacency graph is already stored in the incidence graph, and need not be stored
separately (see subsection 8.1).
8.4. A deterministic algorithm 179
Phase 1 of each incremental step can be carried out in time proportional to the
number of facets created at the previous step. The total cost of phase 1 over all
the incremental steps is thus dominated by the total number of facets created.
At step i that sees the insertion of Ai, the cost of phase 2 is proportional to the
number of nodes visited during the traversal of the adjacency graph. The nodes
visited correspond to red facets of conv(Ai-1), and to the blue facets adjacent to
these red facets. The total cost of this phase is thus at most proportional to the
number of red facets of conv(Avi-) and of their incidences.
The cost of phase 3 is bounded by (a constant factor times) the number of
arcs in the incidence graph that are visited, and this number is the same as the
number of incidences between red or purple faces of conv(Ai-1).
Lastly, the cost of phase 4 is proportional to the total number of red faces and
of their incidences, plus the number of purple faces and of their incidences to
purple faces.
In short, when incrementally adding a point to the convex hull, the cost of
phases 2, 3, and 4 is proportional to the number of red or purple faces, plus the
number of faces incident to a red face, plus the number of incident purple faces.
Red faces and their incidences correspond to the nodes and arcs of the incidence
graph that are removed from the graph. The purple faces and the incidences
between two purple faces correspond to nodes and arcs of the incidence graph that
are added to the graph. The total cost of phases 2, 3, and 4 is thus proportional
to the number of changes undergone by the incidence graph. Since a node or arc
that is removed will not be inserted again (red faces will remain inside the convex
hull for the rest of the algorithm), this total number of changes is proportional to
the number of arcs and nodes of the incidence graph that are created throughout
the execution of the algorithm, which also takes care of the cost of phase 1. The
following lemma bounds this number.
Lemma 8.4.1 The number of faces and incidences created during the execution
of an incremental algorithm building the convex hull of n points in d dimensions
is O(n[(d+l)/ 21).
Proof. Lemma 8.3.1 shows that the subgraph of the incidence graph of conv(Ati)
induced by the faces created upon the insertion of Ai is isomorphic to the set of
faces of conv(A4i-) that are purple with respect to Ai. The number of incidences
between a new face and a purple face of conv(Ai-1) is also proportional to the
number of purple faces of conv(Ai-1). Finally, lemma 8.3.4 shows that the set of
purple faces of conv(A<i-) is isomorphic to a (d - 1)-polytope that has at most
i- 1 vertices. The upper bound theorem 7.2.5 shows that the number of these
faces and incidences between these faces, is O(iL(d-1)/2J). This is thus a bound on
180 Chapter 8. Incremental convex hulls
the number of faces and incidences created upon inserting Ai. Summing over all
i, i = 1, . .. , n, the total number of facets and incidences created by the algorithm
is: n
0(iL(d 1)/2J) =(nL(d+1)-/2J
i~Ii
Theorem 8.4.2 The incremental algorithm builds the convex hull of n points in
d dimensions in time O(n log n + nL(d+l)/ 2 J ) and storage O(nLd/ 2 i).
This algorithm is optimal in the worst case when the dimension of the space is
even.
bounded by Hd that does not contain Pd. Similarly let Ho be the hyperplane
containing {Pl, .. . , Pd- , Pd} and let Ho- be the half-space bounded by Ho that
does not contain Pd. The region determined by the (d + 1)-tuple is the union
of the two open half-spaces Hj and Ho-. A point conflicts with a region if it
belongs to at least one of the two open half-spaces that make up the region. In
this case, the influence domain of a region is simply the region itself.
With this definition of regions and conflicts, the convex hull of a set S of
n affinely independent points can be described as the set of regions defined and
without conflict over S. In fact, the regions defined and without conflict over S are
in bijection with the (d-2)-faces of conv(S). Indeed, let a region be determined by
the (d + 1)-tuple {Po, Pi, .. . , Pd- , Pd} of points in S. Because the points in S are
assumed to be in general position, if this region is without conflict over S, the two
d-1 simplices Fd = conv({Po, Pi, ..., Pd-1 }) and F0 = conv({PI,.. . ., Pd- , Pd})
are facets of conv(S), and the (d-2)-simplex G = FonFd = conv({Pi, .. ., Pd-,})
is the (d - 2)-face of conv(S) that is incident to both these facets. This region
will be denoted below by (Fo, Fd) or sometimes by (Ed, Fo). The set of regions
defined and without conflict over a set S therefore not only gives the facets of
conv(S), but also their adjacency graph. Using this information, it is an easy
exercise to build the complete incidence graph of conv(S) in time proportional
to the number of faces of all dimensions of conv(S) (see exercise 8.2).3
The algorithm
The algorithm is incremental, and in fact closely resembles that which is described
in section 8.4. The convex hull conv(S) of the current set S is represented by its
incidence graph. At each step, a new point P is inserted. The faces of conv(S)
can be sorted into three categories according to their color with respect to P,
as explained in section 8.3: red faces, blue faces, and purple faces. The on-line
algorithm, like the incremental algorithm, identifies the faces that are red and
purple with respect to P, then updates the incidence graph. The main difference
resides in the order with which the points are inserted. The on-line algorithm
processes the points in the order given by the input, and therefore cannot take
advantage of the lexicographic order to detect the red facets. For this reason, the
algorithm maintains an influence graph. As we may recall, the influence graph
3
1t would certainly be more natural to define a region as a open half-space determined by
d affinely independent points. In this case the region is one of the half-spaces bounded by the
hyperplane generated by these d affinely independent points, and a point conflicts with such a
region if it lies in this half-space. With these definitions, the facets of the convex hull conv(S)
of a set S of n points in Ed are in bijection with the regions defined and without conflict over S.
In fact, such a definition of regions is perfectly acceptable and so is an incremental algorithm
based on these definitions (see exercise 8.5). Such an algorithm, however, does not satisfy the
update conditions 5.2.1 and 5.3.3, and its analysis calls for the notion of biregion introduced in
exercise 5.7.
182 Chapter 8. Incremental convex hulls
182 Chapter 8. Incremental convex hulls
is used mainly to detect the conflicts between the point to be inserted and the
regions defined and without conflict over the points inserted so far. The influence
graph is an oriented acyclic graph that has a node for each region that, at some
previous step in the algorithm, appeared as a region defined and without conflict
over the current subset of points. At each step of the algorithm, the regions
defined and without conflict over the current subset correspond to the leaves
of the influence graph. The arcs in this graph link these nodes such that the
following inclusion property is always satisfied: the influence domain of a node is
always contained in the union of the influence domains of its parents. 4 A depth-
first traversal of the influence graph can detect all the conflicts between the new
point P and the nodes in the graph. With a knowledge of the conflicts between
points P and the regions defined and without conflict over S, it is easy to find
the facets of conv(S) that are red with respect to P. Indeed:
* A region defined and without conflict over S that conflicts with P corre-
sponds to a red or purple (d - 2)-face of conv(S), since it is incident to two
(d - 1)-faces of conv(S), at least one of which is red (see figure 8.7).
* A region defined and without conflict over S that does not conflict with P
corresponds to a (d - 2)-face of conv(S) that is blue with respect to P.
In an initial step, the algorithm processes the first d+ 1 points that are inserted
into the convex hull. The incidence graph is set to that of the d-simplex formed
4Recall also that we frequently identify a node in the influence graph with the region that it
corresponds to, which for instance lets us speak of conflicts with a node, of the influence domain
of a node, or of the children of a region.
8.5. On-line convex hulls 183
by these points, and the influence graph is initialized by creating a node for each
of the regions that correspond to the (d - 2)-faces of this simplex.
To describe the current step, we denote by S the current set of points already
inserted, and by P the new point that is being inserted. The current step consists
of a location phase and an update phase.
Locating. The location phase aims at detecting the regions killed by the new
point P. These are the regions defined and without conflict over S that conflict
with P. For this, the algorithm recursively visits all the nodes that conflict with
P, starting from the root.
Updating. If none of the regions defined and without conflict over S is found
to conflict with P, then P must lie inside the convex hull conv(S), and there
is nothing to update: the algorithm may proceed to the next insertion. If a
region corresponding to a (d - 2)-face of conv(S) is found to conflict with P,
however, then at least one of the two incident (d - 1)-faces is red with respect to
P. Starting from this red face, the incidence graph of conv(S) can be updated
into that of conv(S U {P}) by executing phases 2, 3, and 4 of the incremental
algorithm described above in section 8.4.
Its remains to show how to update the influence graph. Let us recall that
the nodes of the influence graph are in bijection with the (d - 2)-faces of the
successive convex hulls, and that the corresponding regions are determined by a
pair of adjacent facets, or also by the d + 1 vertices that belong to these facets.
To update the influence graph, the algorithm considers in turn each of the purple
(d - 2)-faces of conv(S), and each of the (d - 3)-faces incident to these faces.
1. Consider a (d - 2)-face G1 of conv(S) that is purple with respect to P, and
let (F1 , F1) be the corresponding region; F1 and F1' are two (d- 1)-faces of conv(S)
that are incident to G1 . We may assume that F1 is blue with respect to P and F1 is
red (see figure 8.8). The face GI is a (d-2)-face of conv(SU{P}) that corresponds
to the new region (F1 , F{'), where F{' is the convex hull conv(GI U {P}). A new
node of the influence graph is created for region (F1 , F{') and this node is hooked
into the influence graph as the child of (F1 , F,). In this way, the inclusion property
is satisfied. Indeed, let H1 and H' be the hyperplanes supporting conv(S) along
F1 and Ff, respectively. The hyperplane H7' supporting conv(S U {P}) along
F,' is also a hyperplane supporting conv(S) along G1 . As a consequence, the
half-space H`' that does not contain conv(S U {P}) is contained in the union
of the half-spaces H1 and H'7, which do not contain conv(S). The influence
domain of region (F1 , F{') is therefore contained within that of (F1 , F1).
2. Let K be a (d-3)-face of conv(S), purple with respect to P, and let G1 and
G2 be the purple (d - 2)-faces of conv(S) that are incident to K.5 Let (F1 , Ffl
and (F2 , F2) be the two regions corresponding to G1 and G2 , the faces F1 and F2
5 The set of purple faces of conv(S) being isomorphic to a (d - 1)-polytope (lemma 8.3.4),
any purple (d-3)-face of conv(S) is incident to exactly two purple (d -2)-faces (theorem 7.1.7).
184 Chapter 8. Incremental convex hulls
/ .1
IFE
Figure 8.8. On-line convex hull: new regions when inserting a point P.
being blue with respect to P while faces Ff and F' are red (see figure 8.8). The
convex hull conv(K U {P}) is a (d - 2)-face of conv(S U {P}), and is incident
to the (d - 1)-faces Fj' = conv(Gi U {P}) and F2' = conv(G2 U {P})). In the
influence graph, a new node is created for the region (Ff', F2'), and hooked into
the graph to two parents which are the nodes corresponding to regions (F1 , F1)
and (F2 , F2). Let us verify that the inclusion property is satisfied. Indeed, the
influence domain of (Fl', F2') is the union H" - U H2' , where H"'- (resp. H2'-) is
the half-space bounded by hyperplane H1' (resp. H2') that supports conv(SU{P})
along Fj' (resp. F2') and does not contain conv(S U {P}). The half-space Hj'
is contained in the the influence domain of region (F1 , Ff), and similarly H2'-
is contained in the influence domain of (F2 , F2). Consequently, the influence
domain of (Ff', F2') is contained in the union of the influence domains of (F1 , Ff)
and (F2 , F2).
This description can be carried over almost verbatim to the case of dimension 2.
We need only remember that the polytope conv(S) has an empty face of dimen-
sion -1, incident to all of its vertices. If P is not contained within conv(S), the
empty face is purple and incident to the two purple vertices of conv(S) (see also
figure 8.9).
8.5. On-line convex hulls 185
P
In this randomized analysis, we assume that the points are inserted in a random
order. The performances of the algorithm are then estimated on the average,
assuming that all n! permutations are equally likely.
To apply the results in chapter 5, we must verify that the algorithm satisfies
the update condition 5.3.3 for algorithms that use an influence graph.
1. Testing conflict between a point and a region boils down to testing whether
a point belongs to two half-spaces, and can be performed in constant time.
3. The parents of a region created by a point P are recruited among the regions
killed by P. From the analysis of phases 2, 3, and 4 of the incremental step
in section 8.4, we can deduce that updating the incidence graph takes time
proportional to the total number of red and purple faces of conv(S) and
of their incidences. If every (d - 2)-face of the convex hull is linked by a
bidirectional pointer with the corresponding node in the influence graph,
it is easy to see that updating the influence graph takes about the same
time as updating the incidence graph. The set of points being in general
position, the facets of conv(S) are simplices; thus the number of red or
purple faces and of their incidences is proportional to the number of red
facets of conv(S). Each of these red facets is incident to d - 1 red or purple
186 Chapter 8. Incremental convex hulls
Since the update conditions are satisfied, the randomized analysis of the onl-line
convex hull computation can now be established readily by theorem 5.3.4 which
analyzes algorithms that use an influence graph. The number of regions without
conflict defined over a set S of n points in a d-dimensional space is exactly the
number of (d - 2)-faces of the convex hull conv(S), which is Q(nLd/21) according
to the upper bound theorem 7.2.5.
Theorem 8.5.1 An on-line algorithm that uses the influence graph method
to build the convex hull of n points in d dimensions requires expected time
O(nlogn + n Ld/ 2 J), and storage O(nLd/ 2 i). The expected time required to per-
form the n-th insertion is O(logn + nLd/ 2i-1).
each deletion, the structure is rebuilt into the exact state it would have been in,
had the deleted point never been inserted. Consequently, the augmented influence
graph only depends on the sequence E = {P 1 , P2 , . . ., Pn} of points in the current
set, sorted by chronological order: Pi occurs before Pj if the last insertion of Pi
occurred before the last insertion of Pj.
Let us denote by la s) the augmented influence graph obtained for the chrono-
logical sequence E. The nodes and arcs of Ia(s) are exactly the same as those of
the influence graph built by the incremental algorithm of the preceding section,
when the objects are inserted in the order given by E. We denote by SI the
subset of S formed by the first 1 objects in E. The nodes of la(E) correspond
to the regions defined and without conflict over the subsets SI, for 1 = 1, . . , n. .
The arcs of -;a(s) ensure both inclusion properties: that the domain of influence
of a node is contained in the union of the domains of influence of its parents, and
that a determinant of this node is either the creator of this node or is contained
in the union of the sets of determinants of its parents. Moreover, the augmented
influence graph contains a conflict graph between the regions that correspond
to nodes in the influence graph, and the objects in S. This conflict graph is
implemented by a system of interconnected lists such as that described in sec-
tion 6.2: each node of the conflict graph has a list (sorted in chronological order)
of the objects that conflict with the corresponding region; also, for each object
we maintain a list of pointers to the nodes in the influence graph that conflict
with that object. The record corresponding to an object in the conflict list of a
node is interconnected with the record corresponding to that node in the conflict
list of the object.
Insertion
Inserting the n-th point into the convex hull is carried out exactly as in the on-line
algorithm described in section 8.5, except that while we are locating the object in
the influence graph, each detected conflict is added to the interconnected conflict
lists.
Deletion
Let us now consider the deletion of point Pk. For l = k, . . . , n, we denote by S,
the subset Si \ {Pk} of S, and by E' the chronological sequence {P1 , . . ., Pk-1,
Pk+I .... Pn}. When deleting Pk, the algorithm rebuilds the augmented influence
graph, resulting in -Ta(VY). For this, we must:
1. remove from the graph la(s) the destroyed nodes, which correspond to
regions having Pk as a determinant, 6
6
Recall that an object is a determinant of a region if it belongs to the set of objects that
determine this region.
188 Chapter 8. Incremental convex hulls
12
2. create a new node for each region defined and without conflict over one of
the subsets S', 1 = k + 1, . . ., n that conflicts with Pk,
3. set up the new arcs that are incident to the new nodes. The new nodes must
be hooked to their parents which may or may not be new. The unhooked
nodes, which are nodes of Ia(s) that are not destroyed but have destroyed
parents, must be rehooked.
creator of some new or unhooked node if and only if there exists a region defined
and without conflict over S8>- which conflicts with both P1 and Pk (lemma 6.2.1).
When processing P1, we call a region critical if it is defined and without conflict
over S' 1- but conflicts with Pk. The criticalzone is the set of all critical regions.
The critical zone evolves as we consider the objects PI in turn. At the beginning
of the rebuilding phase, the critical regions are the regions of Ia(s) that are
killed by Pk. Subsequently, the critical regions are either regions in Ta(s) that
are killed by Pk, or new regions in Ia(E'). At each substep in the rebuilding
phase, the next point to be processed is the point of smallest rank among all the
points that conflict with one or more of the currently critical regions. To find
this point, the algorithm maintains a priority queue Q of the points in E' that
are the killers of critical regions. Each point PI in Q also stores the list of the
current critical regions that it kills. The priority queue Q is initialized with the
killers in E' of the regions in Ia(E) that were killed by Pk.
At each substep in the rebuilding phase, the algorithm extracts the point Pi of
smallest rank in Q, and this point is then reinserted into the data structure. To
reinsert a point means to create new nodes for the new regions created by P1, to
hook them to the influence graph, and to rehook the unhooked nodes created by
Pi. The (d-2)-faces of conv(S>-) that are red or purple with respect to the point
Pk that is removed correspond to critical regions and are, below, called critical
faces. Unless explicitly stated, the color blue, red, or purple, is now given with
respect to the point Pi that is being reinserted. The regions that are unhooked
or new and created by P1 can be derived from the critical purple (d - 2)-faces
and their (d - 3)-subfaces, which will be considered in turn by the algorithm.
Along with point PI, we know the list of critical regions with which it conflicts.
These regions correspond to the critical red or purple (d - 2)-faces, and a linear
traversal of this list allows the sublist of its critical purple (d - 2)-faces to be
extracted.
Let G be a critical purple (d - 2)-face, and (F, F') be the corresponding region;
F and F' are (d- 1)-faces of conv(Sl-1), both incident to G, and we may assume
that F is blue with respect to P1 while F' is red (see figure 8.11 in dimension 3
and figure 8.12 in dimension 2.)
In the convex hull conv(S'), G is a (d - 2)-face that corresponds to (F, F"), a
region defined and without conflict over S', where F" is the convex hull
conv(G U {P 1}) (see figure 8.11 in dimension 3 and figure 8.12 in dimension 2.)
If region (F, F") conflicts with Pk (see figures 8.11a and 8.12a), then it is a new
region created by P1. In the augmented influence graph, a new node is created
for this region, with node (F, F') as parent. The conflict list of (F, F") can be
190 Chapter 8. Incremental convex hulls
0 C 8. nP
.Pk .*Pk
/ / \/ /\
k-)
Figure 8.11. Deleting from a 3-dimensional convex hull: handling critical purple (d - 2)-
faces.
(a) (F, F") is a new region.
(b) (F, F") is an unhooked region.
set up by selecting the objects in conflict with (F, F") from the conflict list of
(F, F'). The killer of (F, F") in A' is inserted in the priority queue Q if it was not
found there. Finally, region (F, F") is added to the list of critical regions killed
by this point.
If region (F, F") does not conflict with Pk (see figures 8.11b and 8.12b), then it
corresponds to an unhooked node created by P1. This node is found by using the
dictionary D of destroyed and unhooked nodes, and hooked as a child of (F, F').
Pk p. Pi Pk
G 6
(a) (b)
Figure 8.12. Deleting from a 2-dimensional convex hull: handling critical purple (d -2)-
faces.
(a) (F, F") is a new region.
(b) (F, F") is an unhooked region.
(d- 3)-face K has two pointers for keeping track of the critical purple (d-2)-faces
incident to K.
Let K be such a (d - 3)-face (see figure 8.13 in dimension 3 and figure 8.14 in
dimension 2). We denote by GI and G2 the two purple (d - 2)-faces incident to
K. At least one of them is a critical face, but not always both. We denote by
(F1 , Ff) and (F2 , F2) the regions corresponding to faces G1 and G2 of the convex
hull conv(S'-1). We may assume that facets F1 and F2 are blue, while F1 and
F2 are red.
The (d-2)-face conv(KU{Pj}) of conv(S') corresponds to some region (Ft', F2'),
where Fi' = conv(Gi U {Pi}) and F2' = conv(G2 U {P1}) (see figure 8.13; see also
figure 8.14, in dimension 2, in which K is the empty face of dimension -1, and
G1 and G2 are the two vertices of conv(S' 1-), both purple with respect to PI).
2.a If both GC and G2 are critical faces, the corresponding nodes in Ia(E')
may be retrieved through dictionary D'.
2.a.1 If region (Fl', F2') conflicts with Pk (see figure 8.14a), it is a new region
created by Pl; a node is created for this region, and inserted into the influence
graph with both (F1 , F) and (F2 , F2) as parents. The conflict list of (F',F2')
may be obtained by merging the conflict lists of (F1 , F1) and (F2 , F2), and then
selecting from the resulting list the objects that conflict with (Fl', F2'). Merging
the conflict lists can be carried out in time proportional to the total length,
because these lists are ordered chronologically. 8 The killer of (F',F2') in the
sequence E' is inserted into the priority queue Q if not found there, and region
(Ff', F2') is added to the list of critical regions killed by this point.
8
An alternative to this solution is to forget about ordering the conflict lists and to resort to
192 Chapter 8. Incremental convex hulls
. Pi
. Pk
/ / p.\ \
I \PO
Figure 8.13. Deleting from a 3-dimensional convex hull: handling critical purple (d -3)-
faces.
2.a.2 If region (F',F"') does not conflict with Pk (see figure 8.14b), then this
region is an unhooked region created by Pi. It suffices to find the corresponding
node using dictionary D and hook it back to the nodes corresponding to (FI, F1)
and (F2 ,F2).
2.b When only one of the purple (d - 2)-faces GC and G2 incident to K is
critical, say G1 , the algorithm must find in the influence graph the node cor-
responding to G2 , the other purple (d - 2)-face incident to K. Lemma 8.6.1
below proves that, in this case, conv(K, P1 ) is a (d - 2)-face of conv(S1 ) which
corresponds to a destroyed or unhooked node of Xa(E), whose parents include
precisely the node corresponding to region (F2 , F2). To find (F2 , F2), we may
therefore search in the dictionary D of destroyed or unhooked nodes, created
by PI, corresponding to the (d - 2)-face conv(K, Pi) of conv(Si). This node is
uniquely known from this criterion, because we know not only the (d - 2)-face
conv(K, P1 ) of its corresponding region, but also its creator P1 .
the method used in section 6.4 for merging the conflicts lists of trapezoids.
8.6. Dynamic convex hulls 193
, Pk
Pl / \
*I'F4' \ G
1 F1 - Pk
(a) (b)
Pk
L Pk / \
/ \\ /
,// I
/ \\
2 ~/\
G2
I 11
(C) ki) (e)
Figure 8.14. Deleting from a 2-dimensional convex hull: handling the critical purple (d-3)-
faces. Critical purple (d - 3)-face K here is the empty face of dimension -1.
G1 and G2 are its two purple vertices.
(a) G, and G2 are critical, (Fl',F2") is new.
(b) GI and G2 are critical, (F{', F2") is unhooked.
(c) G1 is critical, G2 is not, and GC is not a face of conv(S 1-1 ).
(d) G1 is critical, G2 is not, and GI is a face of conv(S 1- 1 ), but not purple
with respect to PI.
(e) G1 is critical, G2 is not, and G1 is a face of conv(S-1), this time purple
with respect to PI.
Proof. For the proof, imagine that Pk then P1 are inserted into S,-,: then we
obtain successively SI-1 and SI.
The (d - 2)-face K of conv(S' 1-) is purple with respect to Pk since it belongs
to a critical (d - 2)-face as well as to a non-critical (d - 2)-face. As a result, both
K and conv(K, Pk) are faces of conv(SI-1 ).
Since it is not critical, the (d - 2)-face G 2 is also a (d - 2)-face of conv(SI-'),
and its corresponding region is still (F 2 , F2), hence face G 2 of conv(Sj- 1 ) is purple
with respect to PI.
194 Chapter 8. Incremental convex hulls
Once the node corresponding to the (d-2)-face G2 of conv(Sl) has been found,
operations can resume as before, apart from a simple detail. If the region (Ff', F2')
that corresponds to the (d-2)-face conv(K, P1) of conv(S ) is new, then its conflict
list may be obtained by merging that of the critical region (FI, F{) and that of the
destroyed region (conv(K, Pi, Pk), F2'). (We do this in order to avoid traversing
the conflict list of region (F2 , F2) corresponding to face G2, which is neither new
nor destroyed.)
The algorithm is deterministic. Yet the analysis given here is randomized and
assumes the following probabilistic model:
* each insertion concerns, with equal probability, any of the objects present
in the current set immediately after the insertion;
* each deletion concerns, with equal probability, any of the objects present
in the current set immediately before the deletion.
8. 7. Exercises 195
Theorem 8.6.2 Using an augmented influence graph allows the fully dynamic
maintenance of the convex hull of points in Ed, under insertion or deletion of
points. If the current set has n points:
* the structure requires expected storage O(n log n + nLd/2 I),
* inserting a point takes expected time O(logn + nLd/ 2 ] -1),
* deleting a point takes expected time O(log n) in dimension 2 or 3 and time
O(tnLd/ 2 -1)l in dimension d > 3. The parametert represents the complexity
of an operation on the dictionaries used by the algorithm (t O(logn) if
balanced binary trees are used, t = 0(1) if perfect dynamic hashing is used.)
Proof. During the rebuilding phase in a deletion, the number of queries into the
dictionary of destroyed or unhooked nodes is at most proportional to the number
of destroyed or unhooked nodes. For each point P1 that is reinserted, the number
of updates or queries on the dictionary of (d - 3)-faces incident to critical purple
(d - 2)-faces is proportional to the number of these critical purple (d - 3)-faces.
Thus, the total number of accesses to the dictionaries is proportional to the total
number of critical faces encountered that correspond to new or killed nodes. The
conflict lists of new nodes can be set up in time at most proportional to the total
sizes of the conflict lists of new or killed nodes. All the other operations performed
during a deletion, except handling the priority queue, take constant time, and
their number is proportional to the number of destroyed, new, or unhooked nodes.
As a result, the algorithm indeed satisfies the update condition 6.3.5 for algo-
rithms that use an augmented conflict graph. Its randomized analysis is therefore
the same as in section 6.3, and is given in theorem 6.3.6 in terms of fo(l, S), the
expected number of regions defined and without conflict over a random I-sample
of S. For the case of convex hulls, since the number of such regions for any sample
is bounded in the worst case by Q(lId/2j) (upper bound theorem 7.2.5), so is their
expectation fo(1, S). This results in the performance given in the statement of
theorem 6.3.6. In dimension 2 or 3, the number of operations to be performed on
the dictionaries and on the priority queue is 0(1) whereas handling the conflict
lists always takes O(log n) time. Therefore, it suffices to implement dictionar-
ies and priority queues with balanced binary trees. In dimensions higher than
3, deletions have supra-linear complexity, and the priority queue may be imple-
mented using a simple array. °
8.7 Exercises
Exercise 8.1 (Extreme points) Extreme points in a set of points are those which are
vertices of the convex hull. Show that to determine the extreme points of n points in EE2
is a problem of complexity e (n log n).
196 Chapter 8. Incremental convex hulls
Hint: You may use the notion of an algebraic decision tree: an algebraic tree of degree a
is a decision tree where the test at any node evaluates the sign of some algebraic function
of degree a for the inputs. Loosely stated, a result by Ben-Or (see also subsection 1.2.2)
says that any algebraic decision tree that decides whether a point in Ek belongs to some
connected component W of Ek must have a height h = Q(logc(W) - k), where c(W) is
the number of connected components of W.
Exercise 8.2 (Adjacency graph) Let a simplicial d-polytope be defined as the convex
hull of n points. Show that knowledge of the facets of the graph (given by their vertices),
along with their adjacencies, suffices to reconstruct the whole incidence graph of the
polytope in time linear in the size of the adjacency graph, which is Q(nLd/2J).
Exercise 8.3 (1-skeleton) This problem is the dual version of its predecessor. Let a
simple d-polytope be defined as the intersection of n half-spaces. Suppose that the 1-
skeleton is known, that is the set of its vertices and the arcs joining them. Each vertex
is given as the intersection of d bounding hyperplanes. Show that the whole incidence
graph of the polytope may be reconstructed in time 0(nLd/2J).
Exercise 8.5 (On-line convex hulls) Give an algorithm to compute on-line the con-
vex hull of a set of points in Ed, by using an influence graph whose nodes correspond to
regions which are half-spaces. Give the randomized analysis of this algorithm.
O(nrlogn + n L§i). Give an on-line version of the preceding algorithm that uses an influ-
ence graph.
Show that in the version of the algorithm that uses a conflict graph, the storage
requirements may be lowered if only one conflict is stored for each half-space.
Convex hulls
in two and three dimensions
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-and-
conquer 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 problem of computing the convex hull of a polygonal line is interesting
from the point of view of its complexity. Indeed, the lower bound of Q(nlogn)
on the complexity of computing the convex hull of n points does not hold if the
points are assumed to be the vertices of a simple polygonal line. In fact, any
simple polygonal line that links the points in a given set determines an order on
those points which is not completely unrelated to the order of the vertices on
the boundary of the convex hull. In section 9.4, we show how it is possible to
compute in time O(n) the convex hull of a set of n points given as the vertices
9.1. Representation of 2- and 3-polytopes 199
(a) (b)
Figure 9.1. Representation of a 2-polytope: (a) the incidence graph, (b) the circular list
of its vertices.
The proper faces of a 2-polytope consist of its vertices and edges. Each edge
is incident to two vertices and each vertex to two edges. In fact, the incidence
graph of a 2-polytope is a cyclic graph that alternates vertices and edges (see
figure 9.1a). Without losing information, a 2-polytope may be represented by the
doubly-linked circular list of its vertices. Either direction in this list corresponds
to an order on the boundary of the polytope. If the plane that contains the 2-
polytope has an orientation, it induces an order on this boundary that is called
the direct (or counter-clockwise) order of the vertices, and the reverse order is
called the indirect (or clockwise) order of the vertices.
Representation of 3-polytopes
org(E)
sym(E
vertices contained in any given facet, and also on the set of edges and facets
containing any given vertex. Let us agree that supporting hyperplanes are ori-
ented by the outward normal, pointing into the half-space that does not contain
the polytope. This orientation induces a circular order on the edges and vertices
contained in a facet, which we again call the direct (or counter-clockwise) order;
the other orientation induces the indirect (or clockwise) order.
Cycles of edges of a 3-polytope, around a v