Dissertation
Average and Smoothed Complexity
of Geometric Structures
Dipl.–Math. Valentina Damerow
Universit¨
at Paderborn
Fakult¨
at f¨
ur Elektrotechnik, Informatik und Mathematik
Institut f¨
ur Informatik & Heinz Nixdorf Institut (HNI) &
Paderborn Institute for Scientific Computation (PaSCo)
Warburgerstraße 100, D – 33098 Paderborn
Reviewers: Prof. Dr. Friedhelm Meyer auf der Heide, Universit¨
at Paderborn
Prof. Dr. Peter B¨
urgisser, Universit¨
at Paderborn
Do not worry about your difficulties in mathematics;
I can assure you that mine are still greater.
bAlbert Einstein
Acknowledgments
During the last four years I had the golden opportunity to work for this Ph.D. thesis here
at the University of Paderborn. I am especially grateful to Prof. Friedhelm Meyer auf
der Heide who had the confidence in me to accomplish this goal. I experienced a lot of
support from him and also from the members of my research group “Algorithms and Com-
plexity” and many other colleagues in the F¨
urstenallee and on campus. It was sometimes
a challenge but always a great gratification for me to work and live with them.
As my second advisor I would like to thank Prof. Peter B¨
urgisser for valuable comments
on this thesis. My special thanks go also to my co-authors Marcin Bienkowski, Friedhelm
Meyer auf der Heide, Harald R¨
acke, Christian Scheideler, and Christian Sohler, as well as
to Marcel Rudolph Ackermann, Mirko Hessel-von Molo, Jarek Kutylowski, Harald R¨
acke,
and Christian Sohler for carefully reading parts of this thesis.
I would like to thank also all members of the DFG graduate school No. 693 “Scientific
Computation: Application-oriented Modelling and Development of Algorithms”, hosted
by the Paderborn Institute for Scientific Computation (PaSCo). I enjoyed the interdisci-
plinary and international environment very much, it was a great source of inspiration for
me.
bValentina Damerow
bPaderborn, December 2005
i
ii
Contents
1 Introduction 1
1.1 Outline ................................... 3
1.2 BibliographicNotes............................. 4
2 Smoothed Analysis 5
2.1 Smoothed Analysis of Algorithms . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Smoothed Analysis of the Simplex Algorithm . . . . . . . . . . . 7
2.1.2 Smoothed Analysis of Condition Numbers . . . . . . . . . . . . 8
2.1.3 Discrete Perturbation Models . . . . . . . . . . . . . . . . . . . 9
2.2 Smoothed Analysis of Geometric Structures . . . . . . . . . . . . . . . . 10
2.2.1 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . 11
3 Left-to-Right Maxima 13
3.1 AverageCaseAnalysis ........................... 15
3.2 Upper Bounds for the Smoothed Case . . . . . . . . . . . . . . . . . . . 16
3.2.1 Gaussian Normal Noise . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 UniformNoise ........................... 22
3.2.3 Unimodal Noise Distributions . . . . . . . . . . . . . . . . . . . 23
3.3 Lower Bounds for the Smoothed Case . . . . . . . . . . . . . . . . . . . 25
3.4 Conclusion ................................. 27
4 Extreme Points 29
4.1 AverageCaseAnalysis ........................... 33
4.2 Upper Bounds for the Smoothed Case . . . . . . . . . . . . . . . . . . . 37
4.2.1 Normal Gaussian Noise . . . . . . . . . . . . . . . . . . . . . . 41
4.2.2 UniformNoise ........................... 43
4.3 Lower Bounds for the Smoothed Case . . . . . . . . . . . . . . . . . . . 44
4.4 Conclusion ................................. 54
5 Bounding Box of a Moving Point Set 57
5.1 AnalysingMotion.............................. 58
5.1.1 Kinetic Data Structures . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.2 Motion Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.1.3 Smoothed Motion Complexity . . . . . . . . . . . . . . . . . . . 59
iii
Contents
5.2 Motion Complexity of the Bounding Box . . . . . . . . . . . . . . . . . 59
5.2.1 Duality between Bounding Box and Convex Hull . . . . . . . . . 60
5.2.2 Average Motion Complexity of the Bounding Box . . . . . . . . 62
5.2.3 Upper Bounds on the Smoothed Motion Complexity . . . . . . . 62
5.2.4 Lower Bounds on the Smoothed Motion Complexity . . . . . . . 63
5.2.5 Improved Upper Bounds on the Smoothed Motion Complexity . . 63
5.3 Conclusion ................................. 64
6 Voronoi Diagram and Delaunay Triangulation 67
6.1 AverageCaseAnalysis ........................... 69
6.2 ProofofLemma8.............................. 73
7 Summary and Open Problems 89
Bibliography 91
iv
1 Introduction
One of the main challenges in computer science is to determine the complexity of prob-
lems, structures, and algorithms. Since complexity and performance can vary drastically
depending on the considered input instance, it is our goal to provide a profound theoretical
analysis that gives reliable statements about the complexity and performance in applica-
tions, especially for algorithms. There are mainly two different traditional approaches to
achieve this goal, which are the worst case analysis and the average case analysis.
Certainly, worst case analysis is the strongest and most reliable complexity measure we
have. In worst case analysis, we ask for the maximum complexity of a particular problem
over all input instances. The analysis is thus independent of input instances and holds
for any input scenario and under any condition. But for many problems the worst case
complexity bounds are rather pessimistic and for some problems and algorithms rarely
or almost never encountered in applications. One famous example for this is the simplex
algorithm for linear programming. The worst case complexity of the simplex algorithm is
proven to be exponential, while at the same time it shows an extremely good performance
in practice and is therefore widely used.
In order to provide a more ‘realistic’ analysis method researchers introduced the aver-
age case analysis. In the average case analysis a probability distribution on input instances
is defined. The average case complexity of a problem or an algorithm is then the expected
complexity measured on input instances from that distribution. For example, a low average
case complexity provides at least some evidence that an algorithm might perform well in
practice. But in most cases the average case analysis depends on the chosen probability dis-
tribution in the sense that we obtain different results for different probability distributions.
Furthermore, we observe that the usually considered probability distributions provide in
some cases a too optimistic complexity measure compared to the behavior encountered in
applications. One reason for this is that in many applications the inputs have very special
properties and that these properties cannot be captured by any probability distributions.
However, for many problems and algorithms we see a large discrepancy between their
average case and worst case complexity. Moreover, the ‘typical’ complexity of a problem
oralgorithmoneencountersinpracticeseemstolieusuallysomewhere between its average
and worst case complexity. Thus there is need for a complexity measure that bridges this
gap between average case and worst case.
In 2001, Spielman and Teng introduced the smoothed case analysis as a hybrid between
average case and worst case analysis. In smoothed analysis, the input is object to slight
random perturbations, e.g. modeled by adding a random vector from a fixed probability
distribution to the input. The smoothed complexity of an algorithm or problem is then
1
1 Introduction
defined to be the worst case expected complexity over all perturbed inputs where the ex-
pectation is taken with respect to the random perturbation, e.g. the added random noise.
The smoothed complexity is measured as a function of the input size and the magnitude of
the perturbation. Indeed, later we will see that smoothed analysis is able to provide such a
bridge between average case and worst case analysis.
Besides this appealing theoretical motivation the use of smoothed analysis is partic-
ularly well motivated in the context of computational geometry. In many areas we en-
counter applications from computational geometry, e.g. in computer-aided design, oper-
ations research, geographic information systems, computer graphics, and combinatorial
optimization. In these applications of computational geometry the input data often come
from experimental and physical measurements and are thus afflicted with some error since
measuring devices have only limited accuracy. A standard assumption in physics is that
this error is distributed according to the Gaussian normal distribution. Thus we can use
smoothed analysis with Gaussian error to model inputs coming from physical measure-
ments. By the assumptions that physical measurements are not precise and that the error is
distributed according to the Gaussian normal distribution, smoothed analysis provides an
expected worst case complexity measure for this class of inputs.
Another interesting motivation for smoothed analysis in the context of computational
geometry is that the computations on a computer are carried out with limited accuracy.
When we consider the case that the input points are computed with fixed precision arith-
metic we observe that the rounded position of any point lies within a hypercube of a partic-
ular side length around its ‘real’ position where the side length of the hypercube depends
on the rounding. We can now model this scenario by the assumption that every point is
distributed uniformly in a hypercube centered at its ‘real’ position having an appropriate
side length (depending on the considered rounding). We obtain thus an expected worst
case complexity measure for computations under limited accuracy.
In this thesis, the combinatorial complexity of some fundamental geometric structures is
considered. The main contribution is to introduce a formal model for smoothed analysis of
the combinatorial complexity of geometric structures. Among other problems, this concept
is applied to the number of extreme points of the convex hull of a point set in IRd. In the
following, some of the results for this problem are sketched.
In particular, for the convex hull we will assume that the input points are perturbed
by Gaussian normal noise of variance σ2. It is then shown that the worst case expected
number of extreme points, or for short, the smoothed number of extreme points is poly-
logarithmic in the number of input points and polynomial in 1/σ. For this result almost
matching upper and lower bounds are given where the dimension dis considered as a
constant. Interestingly, for uniform noise of variance σ2the smoothed number of extreme
points is polynomial in the number of input points and 1/σ. This reveals a significant
discrepancy between the perturbation by Gaussian normal noise and by uniform noise. In
other words, the assumptions of measurement errors and fixed precision arithmetic lead to
quite different behavior and results.
Indeed, the analysis is much broader and provides actually bounds on the smoothed
2
1.1 Outline
number of extreme points for a whole class of continuous probability distributions. An
interesting open problem is to generally classify those probability distributions for which
the smoothed complexity is low or high.
Smoothed analysis is also used to introduce a new complexity measure for motion, the
smoothed motion complexity. Especially when considering applications on moving objects
the influence of measurement errors is not negligible and of major importance. The use
of smoothed analysis is thus very well motivated in the context of motion and motion
complexity. The concept of smoothed motion complexity is then applied to the problem of
maintaining a smallest axis-aligned bounding box of a moving point set.
Another fundamental geometric structure is the Voronoi diagram of a set of points in IRd.
The combinatorial complexity of Voronoi diagrams (= number of all faces) is assumed to
be low in the average case but for most probability distributions explicit proofs are not
published. In this thesis the case is considered that the points are chosen uniformly from
a hypercube and it is shown that the expected complexity of the Voronoi diagram is then
also linear in the number of points. Based on this average case analysis it seems possible
to carry out a smoothed case analysis of the Voronoi diagram which is a quite interesting
open problem.
1.1 Outline
In Chapter 2, an introduction to smoothed analysis is given with a formal definition and a
broad overview on related work. In several papers, smoothed analysis and also its variants
have been applied to problems from very distinct areas of research.
In the first technical Chapter 3, smoothed analysis is applied to the problem of count-
ing the number of left-to-right maxima in a sequence of elements. The chapter starts with
an average case analysis of the problem and presents then the smoothed case analysis in
great detail where upper and lower bounds for various noise distributions are given. On
the one hand, this problem and its analysis serves very well as an introductory example to
the concepts and techniques used in this thesis. On the other hand, the left-to-right max-
ima problem represents somehow a 1-dimensional version of two other multi-dimensional
problems that are considered in the next two chapters.
The problem to count the number of extreme points is a kind of canonical extension of
the left-to-right maxima problem to higher dimensions, and it is treated in Chapter 4. The
chapter starts with an average case analysis and presents then upper and lower bounds for
the smoothed number of extreme points for various noise distributions.
In Chapter 5, motion and especially moving point sets are considered under the notion
of motion complexity which is a complexity measure for movement of objects. It is pro-
posed to extend this notion to smoothed motion complexity, which is as the name already
indicates, a ‘smoothed’ version of motion complexity. This concept is then applied to the
bounding box problem where the number of combinatorial changes to the description of
the bounding box of a moving point set is considered. Upper and lower bounds on the
3
1 Introduction
smoothed motion complexity of the bounding box problem are given.
In the last technical Chapter 6, the Voronoi diagram of a random point set and particu-
larly the expected number of Voronoi vertices is considered. It is shown to be only linear in
the number of points for the case that the points are uniformly distributed in a hypercube.
For the case that the points are chosen uniformly from inside a ball, Dwyer [Dwy91] gave
already an explicit proof that the expected number of vertices is linear. He conjectured
that similar results hold for other uniform distributions but proofs are lacking so far or not
published in any form.
Each chapter starts with a short introduction and a brief overview of related work in
order to help classify the considered problem and the obtained results, and ends with a
summary and conclusion. Finally, in the last Chapter 7, a summary and conclusion of all
results in this thesis is given together with a prospect of future work in this area.
1.2 Bibliographic Notes
Parts of the work presented here in this thesis have been published in preliminary form
in the proceedings of the European Symposium on Algorithms (ESA) and the European
Workshop on Computation Geometry (EWCG). These publications are
•V. Damerow, H. R¨
acke, F. Meyer auf der Heide, C. Scheideler, and C. Sohler.
Smoothed Motion Complexity. In Proceedings of the 11th European Symposium
on Algorithms (ESA), 2003. [DMR+03]
•V. Damerow and C. Sohler. Smoothed Number of Extreme Points under Uniform
Noise. In Proceedings of the 20th European Workshop on Computational Geometry
(EWCG), 2004. [DS04b]
•V. Damerow and C. Sohler. Extreme Points under Random Noise. In Proceedings
of the 12th European Symposium on Algorithms (ESA), 2004. [DS04a]
•M. Bienkowski, V. Damerow, F. Meyer auf der Heide, and C. Sohler. Average
Case Complexity of Voronoi Diagrams of nSites from the Unit Cube. In Proceed-
ings of the 21st European Workshop on Computational Geometry (EWCG), 2005.
[BDMS05]
The results of Chapter 3 on the smoothed number of left-to-right maxima and of Chap-
ter 5 on the smoothed motion complexity of the bounding box are based on the work in
[DMR+03]. The lower bounds for the smoothed number of extreme points are an exten-
sion of this work, too. The upper bounds for the smoothed number of extreme points are
an extension of the results presented in the papers [DS04b] and [DS04a]. The average case
analysis of the Voronoi diagram in Chapter 6 is based on the work presented in [BDMS05].
4
2 Smoothed Analysis
The general idea of smoothed analysis is to weaken the worst case complexity by adding
small random noise to any input instance. The smoothed complexity of a problem is then
the worst case expected complexity over all input instances, where the expectation is with
respect to the random noise, and is given as a function of the input size and the relative
magnitude of the perturbation. To see how this complexity measure compares to worst
case and average case complexity we will consider these, too. In the following section, the
worst case, average case and smoothed case complexity of algorithms is introduced and
formally defined.
2.1 Smoothed Analysis of Algorithms
Let Xndenote the space of all input instances of length nto a particular algorithm A,
consider for example the space all linear programming problems of length nto the simplex
algorithm. Let TA(x)denote the running time of algorithm Aon input x∈ Xn. The worst
case complexity of algorithm Ais then the function
Cworst(A, n) := sup
x∈XnTA(x).
To consider the average case complexity of algorithm A, a probability measure ∆on Xn
is introduced. The average case complexity of algorithm Ais then defined as
Cave(A, n) := E∆TA(x),
where xis a random variable on (Xn,∆) and E∆is the expectation with respect to ∆.
For the smoothed complexity of algorithm A, in contrast, a probability measure ∆xis
considered for each input instance x∈ Xn, and the smoothed complexity of algorithm A
is defined as
Csmooth(A, n) := sup
x∈Xn
E∆xTA(y),
where yis a random variable on (Xn,∆x).
This definition of course heavily depends on the probability measures ∆xthat are used.
Which measures to use depends on each individual problem, but normally one will con-
sider measures which put much weight on inputs that are similar, or near, to x. This notion
is best illustrated by the following examples.
5
2 Smoothed Analysis
1. If Xnis a finite discrete metric space with metric d, one can consider
∆x({x0}) = f(d(x, x0))
with some suitable function fthat is e.g. supported on a bounded neighborhood of
0.
2. If Xnis a vector space and ϕ:Xn→IR≥0a suitable probability density function
one can consider
∆x(B) = ZB
ϕ(x−x0) dx0
where Bis a subset of Xn.
An important aspect of smoothed analysis is that the concept of smoothed complexity is
a generalization of both average case and worst case complexity. While the former can be
obtained by setting all distributions ∆xequal to the same global distribution ∆, the latter
is obtained in the case that the probability measures ∆xare all concentrated in the point x
itself. One could therefore also say that smoothed analysis actually interpolates between
worst case and average case analysis.
Besides the general definition of smoothed complexity, in most papers that appeared
on smoothed analysis, the following more concrete definition of smoothed complexity is
used. Let Xnbe a vector space, e.g. Xn= IRn. The smoothed complexity of algorithm A
is then the function
Csmooth(A, n) := sup
x∈Xn
E∆TA(x+||x||·ρ),
where ∆is again a probability measure on Xnand ρa random vector on (Xn,∆).
The vector ρis also denoted as the random noise by which the input instances to al-
gorithm Aare perturbed. By multiplying ρwith ||x||, the magnitude of the perturbation
is related to the magnitude of the input that is perturbed. This is important when the
considered problems are invariant under scaling which is for example the case for linear
programs. Otherwise it would happen that problems that are equivalent up to their ‘size’
obtain different results under the same perturbation. In the following we will denote this
definition of smoothed analysis as the additive perturbation scheme.
The name “smoothed analysis” comes from the following observation. If we consider
the complexity of a problem or an algorithm as a function from the input space to the
combinatorial size of the problem or the running time of the algorithm or to any other
complexity measure, and we plot this function, we obtain a complexity landscape, see
also Figure 2.1. The smoothed complexity is then the highest peak in this landscape after
it is convolved with a small random noise distribution. One could also interpret this as
taking for each single input point the average complexity value over a small (weighted)
neighborhood of this input point and assigning this value to the input point.
6
2.1 Smoothed Analysis of Algorithms
worst case
run time
input space
smoothed case
run time
input space
Figure 2.1: Complexity Landscape and Smoothed Complexity Landscape1.
Smoothed analysis provides thus an insight into the topology of worst case instances in
the input space. A low smoothed complexity shows whether bad inputs are pathological
and isolated and can thus be avoided by already slight changes to the input instance. A
high smoothed complexity reveals that bad inputs are somehow closely connected in terms
of lying closely in the same neighborhood of the input space.
2.1.1 Smoothed Analysis of the Simplex Algorithm
Smoothed analysis was introduced by Spielman and Teng [ST04] to explain the typically
good performance of the simplex algorithm in applications. For many variants of the
simplex algorithm with different pivot rules, the worst case complexity is proven to be
exponential, e.g. on the famous Klee-Minty cubes [KM72]. Nevertheless, the simplex al-
gorithm shows an extraordinarily good performance on input instances from applications.
The simplex algorithm is also known to have polynomial average case complexity under
different notions of average case. The first average case analysis of the simplex algorithm
was given by Borgwardt [Bor80], many other researchers followed him and investigated
the average case complexity for other variants and pivot rules of the simplex algorithm. But
still these results are not considered to give a satisfying explanation of the good behavior
of the simplex algorithm encountered in practice.
Another intention for Spielman and Teng to introduce smoothed analysis as a new com-
plexity measure was to model inputs that are encountered in applications. Besides the
assumption that inputs are afflicted with measurement errors, another motivation for us-
ing randomly perturbed inputs comes from the observation, that usually inputs are formed
in processes subject to chance, randomness, and arbitrary decisions. On the other hand
1Reproduction by courtesy of Daniel Spielman.
7
2 Smoothed Analysis
typical inputs can have very special properties such as being degenerated, which holds
especially for the simplex algorithm. It is e.g. not unusual that typical input instances
to the simplex algorithm contain many 0-entries in the constraints matrix. Indeed, this
phenomenon is captured by taking the worst case over all perturbed input instances.
Spielman and Teng now consider a particular two-phase shadow-vertex simplex method
on linear programs of the form
maximize cT·x
subject to A·x≤b
where Ais an (m×n)-matrix, bis an m-vector, and cis an n-vector over the reals. Let
T(A, b, c)denote the time complexity of this simplex method. They show that for every b
and c, the smoothed complexity of this method,
max
A∈IRm×n
EGT(A+||A||·G, b, c)= poly(m, n, 1/σ)
is polynomial in m, n, and 1/σ, independent of band c, where Gis a Gaussian random
(m×n)-matrix of variance σ2centered at the origin.
Most remarkable about this result is, that the complexity of the simplex algorithm actu-
ally grows incredibly slow from the polynomial average case complexity to the exponential
worst case complexity. This can be seen from the smoothed case bound, where the recip-
rocal of the standard deviation 1/σ goes only by a polynomial factor into the smoothed
case bound.
The result of Spielman and Teng definitively marks a major step to an understanding of
the behavior of the simplex algorithm in applications since it gives us a strong evidence
that worst case instances are pathological and very isolated in the input space and therefore
almost never encountered in practice.
2.1.2 Smoothed Analysis of Condition Numbers
Since 2001 several other papers on the smoothed analysis of algorithms have been written.
The following results are all obtained for the additive perturbation scheme.
In numerical analysis, the condition number of a problem instance plays an important
role. Generally, it is defined to indicate the sensitivity of the output to slight perturba-
tions of the input instance, and the running time of an algorithm is often given in terms
of the condition number of its input. Instead of bounding the condition number in the
average case, it is proposed to consider the smoothed value of the condition number in
order to show that already under small noise it is unlikely that a problem is ill-conditioned
[SST03]. In this stream of research, the Perceptron algorithm [BD02] and Renegar’s algo-
rithm [DST03, ST03b] for linear programming, and most recently, Gaussian elimination
[San04] are investigated.
8
2.1 Smoothed Analysis of Algorithms
In some sense connected to the analysis of smoothed condition numbers is the research
work of Beier and V¨
ocking. They consider the sensitivity of perturbations to discrete opti-
mization problems like the Knapsack problem [BV04a] and generally to the class of all bi-
nary optimization problems [BV04b]. The analyses are actually broader than in smoothed
analysis since they can even handle the case that the elements of an input instance are
from different probability measures. This enables them to study the effects of correlations
between the random elements of input instances and gives also a nice framework to study
semi-random input models where some elements of an input instance are adversarial and
some stochastic. Maybe most remarkable is their result that a binary optimization problem
has a polynomial smoothed complexity if and only if it has a pseudo-polynomial complex-
ity. This result was recently extended to all integer linear programs [RV05].
2.1.3 Discrete Perturbation Models
We just saw how smoothed analysis with the additive perturbation scheme is applied to
discrete algorithms. There are also attempts to define meaningful models for discrete
perturbations in order to analyze other discrete algorithms. This makes sense in several
settings, e.g. when investigating discrete structures like graphs and algorithms on graphs,
but also for other problems and algorithms like sorting and scheduling.
Banderier et al. [BMB03] were the first to introduce discrete perturbations. They define
partial permutations where the elements in a sequence are randomly permuted with prob-
ability p. In the partial permutations model they analyze then the quicksort algorithm2.
Banderier et al. introduce also partial bit randomization where integers are perturbed by
randomly choosing the last kbits. This model is extended by Becchetti et al. [BLMS+03]
and applied to clairvoyant scheduling. They introduce smoothed competitive analysis for
online algorithms and present an analysis of the smoothed competitive ratio of the multi-
level feedback algorithm. The usual competitive analysis gives often a too pessimistic
estimation of the performance of an online algorithm since the online algorithm is mea-
sured against an optimal offline algorithm with full knowledge of the future. Sometimes
the offline algorithm is thus simply too strong. In smoothed competitive analysis, the of-
fline algorithm is somehow weaker since the input instances are randomly perturbed and
it has not full knowledge about the future. In this sense, it seems quite natural to apply
smoothed analysis to the analysis of online algorithms.
As already mentioned, Banderier et al. consider the number of comparisons of the quick-
sort algorithm in the partial permutations model. Eppstein [Spi] proposed to refine this
model in such a way that the already sorted input and the reverse-sorted input stay unper-
turbed and that the perturbation of other inputs depends on their distance to these inputs.
This perturbation would capture one significant property of the continuous perturbation
scheme, that the zero (here the sorted and reverse-sorted inputs) stay unperturbed and that
other inputs are perturbed in proportion to their distance to zero.
2They consider a deterministic variant of quicksort where the first element is always taken as pivot element.
9
2 Smoothed Analysis
Spielman and Teng [ST03a] try to further develop this concept and introduce property-
preserving perturbations. The idea is to restrict a natural discrete perturbation model to
preserve certain properties of the input. The notion of a ‘natural’ perturbation scheme in
discrete settings is of course very vague since for most discrete problems is not nearly clear
what natural means. E.g. for graphs Spielman and Teng propose to define perturbations
by XORing an input graph with some random (sparse) graph such that some particular
property of the input graph (such as having a ρ-clique) stays preserved by the perturbation.
Then they measure the smoothed error probability of sub-linear time algorithms for this
property. This idea is in some sense closely related to studies in the field of property
testing.
In property testing one wants to decide whether an input instance has a certain property
or differs significantly from all instances with that property. Property testing provides an
alternative weakening of decision problems and is thus related to smoothed analysis. It
seems therefore promising to join these two models. In this stream of research, Flaxman
and Frieze [FF04] consider the diameter of randomly perturbed graphs and present an
algorithm for recognizing strong connectivity of smoothed instances and also present a
property tester for recognizing if a digraph is k-linked.
2.2 Smoothed Analysis of Geometric Structures
In this thesis the combinatorial complexity of (geometric) structures on point sets in IRdis
considered, such as the number of left-to-right maxima in a sequence of elements or the
number of extreme points of the convex hull of a point set. We investigate the smoothed
case complexity of these structures under an additive perturbation scheme which is defined
as follows.
Definition 1 (Perturbed Input Point) For a fixed probability measure ∆defined on IRd
consider an input point p∈IRdand a random noise vector ρfrom ∆. Let epbe the random
vector that is given by
ep:= p+ρ .
The random vector epis also denoted as the perturbed point to input point p, or for short
as the perturbed input point.
For a set Pof ninput points p1, . . . , pnfrom IRdwe denote by e
Pthe set of perturbed
input points under random noise ∆. It is given by
e
P:= {p1+ρ1, . . . , pn+ρn}={ep1,...,epn},
where ρ1, . . . , ρnare independent and identically distributed random noise vectors from
∆.
The smoothed complexity of a geometrical structure is defined on input instances P
where p∈[0,1]dfor all p∈ P. The reason for this confindement is that the input point set
10
2.2 Smoothed Analysis of Geometric Structures
needs to be normalized since the geometric structures considered here are invariant under
scaling.
Definition 2 (Smoothed Complexity) For a set Pof ninput points from [0,1]dconsider
some geometric structure on Pand let T(P)denote a combinatorial complexity measure
for this structure. For a fixed probability measure ∆on IRd, the smoothed complexity of
T(P)is defined as
max
P
E∆T(e
P)
where e
Pis the set of perturbed input points under random noise from ∆.
This perturbation scheme is also used by Bansal et al. who consider the labeling of smart
dust [BMS04]. By smart dust a large set of small and very simple devices is meant, each
consisting of a sensor and a sender that gathers sensor data and sends it to a central station.
These devices are usually placed with low accuracy. It is thus very natural to model the
imprecise information about the position of the sensor devices by random perturbations to
the position information.
Banderier et al. [BMB03] consider also the smoothed complexity of geometric struc-
tures. Among other things they analyze the smoothed number of left-to-right maxima in
the partial permutations model where each element is randomly permuted with probabil-
ity p. This problem is also considered in this thesis, see Chapter 3 and especially page 14
where the result of Banderier et al. is discussed in more detail. However, the perturbation
scheme of Banderier et al. significantly differs from the one used in this thesis.
2.2.1 Probability Distributions
In this thesis a very general class of probability measures is considered and the results
hold for all measures from this class. In the following this class of probability measure is
characterized by probability distribution functions.
In the 1-dimensional case we consider probability measures of the following kind. Let
Xbe a 1-dimensional random vector taking values from some domain R⊆IR. Let the
probability distribution function of Xbe given by
Φ(x) := Pr[X≤x] = Zx
−∞
ϕ(z) dz ,
Here ϕ: IR →IR≥0is a bounded, integrable function with R∞
−∞ ϕ(z) dz= 1 and is
denoted as the probability density function of variable X. All probability distributions of
the just described kind are denoted as continuous probability distributions.
In the d-dimensional case we consider probability measures that have as distribution
functionthed-foldproductofa1-dimensionalcontinuousprobabilitydistributionfunction.
11
2 Smoothed Analysis
Let X= (X1, . . . , Xd)be a d-dimensional random vector taking values from some area
Rd=Qd
i=1 R⊆IRdwhere R⊆IR. Let the probability distribution function of Xbe
given by
Pr[X1≤x1, . . . , Xd≤xd] = Zxd
−∞ ···Zx1
−∞
ϕ(z1)···ϕ(zd) dz1··· dzd.
Again ϕ: IR →IR≥0is a bounded, integrable function with R∞
−∞ ϕ(z) dz= 1 and is
denoted as the 1-dimensional components’ density function of X.
Note that all components of Xare mutually independent and identically distributed.
Probabilitydistributionsofthejustdescribedkindare denoted as continuous d-dimensional
product probability distributions. Examples for such distributions are the d-dimensional
Gaussian normal distribution or the uniform distribution in a d-dimensional hypercube.
Preliminaries. We considerthesmoothedcombinatorialcomplexityofgeometricstruc-
tures where the geometric structures are defined on point sets in IRd. The smoothed com-
plexity is usually given as a function of the input size, i.e. here the number of input points,
and the reciprocal of the standard deviation of the 1-dimensional random noise distribution.
For uniform noise we consider the uniform distribution in a hypercube of side length
2centered at the origin. Note, that the standard deviation of the 1-dimensional uniform
distribution (i.e. the uniform distribution in an interval [−, ]) is then /√3. Thus when
considering uniform noise we do not explicitly state this but give the results only in terms
of the side length of the hypercube. However, the results are still comparable to results for
other noise distributions where the bounds are given in terms of the standard deviation.
The following other definitions hold throughout this thesis:
•The logarithm to basis 2is denoted by log, and the logarithm to basis eby ln.
•The n-th harmonic number of first order is given by H(n) = Pn
`=1 1/`, and of
second order by H(2)(n) = Pn
`=1 1/`2for all n∈IN.
•It is H(n) = ln(n) + O(1).
•The Gamma function is given by Γ(n+1) = n!and Γ(n+1/2) = (2n)!·√π/(n!·22n)
for all n∈IN.
12
3 Left-to-Right Maxima
In this first technical chapter we consider the problem to count the number of left-to-right
maxima in a sequence of elements (numbers). We analyze the average and smoothed
number of left-to-right maxima for all continuous probability distributions.
On the one hand, this problem is very basic and rather simple since it is one dimensional.
It serves therefore as a good introductory example since proof ideas and basic technical
steps will return later in the analysis of other problems. On the other hand, the results
we obtain for this problem will be extended to higher dimensions in Chapter 4. There we
consider the number of maximal points and extreme points of the convex hull. Maximal
points are a kind of canonical extension of the left-to-right maxima problem to arbitrary
dimensions. Chapter 5 deals with the number of combinatorial changes to the description
of the bounding box of a moving point set. The left-to-right maxima problem serves there
as an auxiliary problem to improve some of the results.
However, the presentation of techniques and proofs in this chapter is in great detail in
order to make further reading more convenient. We will start now with the following
formal problem definition.
Definition 3 (Left-to-Right Maxima) Given is an arbitrary sequence Sof nnumbers
(called elements) S= (s1, . . . , sn)where sk∈IR for all 1≤k≤n. If all predeces-
sors of skhave smaller value than sk, i.e. if si< skfor all i < k, element skis called
aleft-to-right maximum in S. Let L(S)denote the number of left-to-right maxima in
sequence S.
The main contribution of this chapter is a rather general lemma that can be used to obtain
upper bounds on the smoothed number of left-to-right maxima for noise from continuous
probability distributions. This lemma is applied to obtain explicit bounds for noise from
the Gaussian normal distribution and the uniform distribution in a closed interval. The
upper bounds are then complemented by lower bounds. Interestingly, these upper and
lower bounds show that the smoothed number of left-to-right maxima differs significantly
for random noise from the Gaussian normal and the uniform distribution. This is even more
interesting since in the usual average case the expected number of left-to-right maxima is
the same for all continuous probability distributions.
Related Work. In many textbooks about computer science and theory [Knu97, LL83,
Kem84], the number of left-to-right maxima is considered in the context of permutations or
in the analysis of basic algorithms, e.g. for finding a maximum in a sequence of numbers.
13
3 Left-to-Right Maxima
For an input sequence of nelements, the maximum number of left-to-right maxima
is clearly nwhile it is 1in the best case. The average number is known to be the n-th
harmonic number H(n) = Pn
`=1 1/` for a wide variety of probability distributions. The
standard deviation is known to be (H(n)−H(2)(n))1/2, where H(2)(n) = Pn
`=1 1/`2is the
n-th harmonic number of second order.
The smoothed number of left-to-right maxima has already been analyzed but for a
fundamentally different perturbation scheme than the one that is considered here. Ban-
derier at al. [BMB03] introduce so called partial permutations where in a sequence of
nelements each element is selected with some fixed probability p, and the selected ele-
ments are then randomly permuted where each permutation is equally likely. Under this
model, the authors show that the smoothed number of left-to-right maxima is Ω(pn/p)
and O(pn/p ·log(n)). Interestingly, the worst case instance in the smoothed case under
this model is the sequence (n−k, n −k+ 1, . . . , n, 1,2, . . . , n −k−1) for k=pn/p.
For the perturbation scheme that is considered here, the worst case instance is the sequence
(1,2, . . . , n), see also Lemma 1.
Outline. In Section 3.1 the usual average case number of left-to-right maxima is con-
sidered. We will show how to derive the expected number of left-to-right maxima for a
sequence of independent and identically distributed random elements chosen from a con-
tinuous probability distribution. The average case is already well known and a proof can
actually be done by very simple considerations. But instead we present a more sophisti-
cated way of showing the average case by use of integrals. This is done to better illustrate
the approach for the smoothed case where the use of integrals is of major importance.
In Section 3.2 the smoothed case analysis is presented. The proofs are described in great
detail since the basic steps of the analysis will return in Chapter 4 where we consider the
number of extreme points in ddimensions. We derive a general lemma (Lemma 2) to upper
bound the smoothed number of left-to-right maxima for all continuous noise distributions.
This lemma is applied to obtain explicit bounds for noise from the Gaussian normal distri-
bution N(0, σ)and the uniform distribution in an interval [−, ]. For these noise distribu-
tions we get upper bounds of O(1/σ ·log(n)3/2+log(n)) and O(pn·log(n)/+log(n)),
respectively. Also some general class of unimodal probability distributions is considered
which have monotonic density functions with one single ‘peak’.
In Section 3.3 lower bounds for the smoothed number of left-to-right maxima are shown
which prove that the upper bounds are almost tight for Gaussian normal and uniform noise.
In the last section the results of this chapter are shortly summarized. We also work
out the property for continuous, unimodal probability distributions that are necessary to
provide a low smoothed complexity that comes close to the average case complexity.
14
3.1 Average Case Analysis
3.1 Average Case Analysis
We consider now the case when the elements s1, . . . , snare independent and identically
distributed random variables with probability distribution function Φ : IR →[0,1]. Let
Φhave the integrable density function ϕ: IR →IR≥0with R∞
−∞ ϕ(x) dx= 1. The
probability distribution of input element siis then given by
Pr[si≤x] = Φ(x) = Zx
−∞
ϕ(z) dz .
The following theorem holds for all distributions of the above kind.
Theorem 1 The expected number of left-to-right maxima in a sequence Sof nindepen-
dent and identically distributed random variables chosen from a continuous probability
distribution is
E[L(S)] = H(n) = Θ(log(n)) ,
where H(n)denotes the n-th harmonic number, i.e. H(n) = Pn
k=1 1/k.
Proof. The probability for the k-th element skto be a left-to-right maximum in Sis given
by
Pr[skis a left-to-right maximum in S] = Z∞
−∞
ϕ(x)·Φ(x)k−1dx . (3.1)
This holds since Φ(x)is the probability that a random variable siis not greater than
x, and since all variables are independent and identically distributed Φ(x)k−1equals the
probability that all k−1predecessors of skare smaller than x. Consequently, the expres-
sion ϕ(x)·Φ(x)k−1dxcan be interpreted as the probability that the k-th element reaches
xand is a left-to-right maximum. Hence, integration over xgives the probability that skis
a left-to-right maximum.
In order to compute the integral in (3.1) we will use the substitution z:= Φ(x), where
dz=ϕ(x) dx. This yields
Z∞
−∞
ϕ(x)·Φ(x)k−1dx=Z1
0
zk−1dz=1
k.
Of course, this result only reveals the fact that the probability for the k-th element to be
the largest among the first kelements is 1/k. We can exploit linearity of expectation and
sum up over the probabilities for all kwhich leads to
E[L(S)] =
n
X
k=1
1
k=H(n).
Consequently, the theorem is proven. B2
15
3 Left-to-Right Maxima
0.4
x
0.3
04
0.1
-2
0.2
0-4 2
Figure 3.1: Shifted Gaussian bell curves – the density functions of N(0,1),N(1/2,1) and
N(−1/2,1).
3.2 Upper Bounds for the Smoothed Case
In the last section we saw how to express the probability that a random element is a left-
to-right maximum by an integral expression. In order to investigate the smoothed number
of left-to-right maxima we will express the probability that a perturbed element is a left-
to-right maximum also by an integral expression in a similar way.
Let us first consider the random noise. Let ρ1, . . . , ρnbe independent and identically
distributed random numbers from a continuous noise distribution with integrable density
function ϕand corresponding distribution function Φ. So for a given sequence of input el-
ements S= (s1,...sn)we consider the sequence of perturbed elements e
S= (es1,...,esn)
where esk=sk+ρk, for all 1≤k≤n. For reasons of normalization we assume that
s1, . . . , sn∈(0,1].
First of all we make the following observation. When the noise distribution is fixed the
sequence of perturbed elements also becomes a random distribution where an element esk
is a random number with density function ϕ(x−sk)and according distribution function
Pr[esk≤x] = Φ(x−sk). Contrary to the usual average case, the perturbed elements are
not drawn from the same probability distribution and are thus not identically distributed.
Instead each perturbed element has a density and distribution function that is a copy of
16
3.2 Upper Bounds for the Smoothed Case
the density and distribution function of the random noise with different parameters. The
density and distribution function of eskdiffer from the density and distribution function of
the random noise only in the sense that the curves are shifted by the according amount of
sk. For example, in Figure 3.1 three shifted versions of the Gaussian density function are
depicted.
Now we can write analogously to (3.1) that
Prheskis a left-to-right maximum in e
Si=Z∞
−∞
ϕ(x−sk)·
k−1
Y
j=1
Φ(x−sj) dx . (3.2)
In order to proceed we first need to show the following lemma.
Lemma 1 The maximum expected number of left-to-right maxima in a sequence e
Sof per-
turbed elements is obtained for a sequence of input elements Sthat is monotonically in-
creasing.
Proof. Consider the two sequences of input elements S1= (s1, . . . , sk−2, sk, sk−1)and
S2= (s1, . . . , sk−2, sk−1, sk), where sk−1< sk, and let the difference between the these
two elements be γ:= sk−sk−1>0. For a fixed noise distribution we want now to show
that
β:= EhL(e
S2)i−EhL(e
S1)i≥0,
where L(e
S1)and L(e
S2)denote the number of left-to-right maxima in the perturbed se-
quences e
S1and e
S2under noise from the fixed probability distribution, respectively.
To see this it suffices to consider for both sequences S1and S2the probability that sk−1
and that skbecome a left-to-right maximum in the perturbed sequences e
S1and e
S2. Since
all elements are independent the probabilities for the other elements to be a left-to-right
maximum are equal for both sequences and we can neglect them. Hence we get that
β=Prhesk−1is left-to-right max. in e
S2i+Prheskis left-to-right max. in e
S2i
−Prheskis left-to-right max. in e
S1i+Prhesk−1is left-to-right max. in e
S1i .
Let now ϕand Φdenote the density function and distribution function of the fixed noise
distribution, respectively. Further, for ease of notation let F(x) = Qk−2
j=1 Φ(x−sj)denote
the probability that the first k−2elements in e
S1and e
S2are not greater than x. Then it
17
3 Left-to-Right Maxima
follows analogously to (3.2) that
β=Z∞
−∞
ϕ(x−sk−1)·F(x) dx+Z∞
−∞
ϕ(x−sk)·Φ(x−sk−1)·F(x) dx
−Z∞
−∞
ϕ(x−sk)·F(x) dx+Z∞
−∞
ϕ(x−sk−1)·Φ(x−sk)·F(x) dx
=Z∞
−∞
ϕ(x−sk−1)·(1 −Φ(x−sk)) ·F(x) dx(3.3)
−Z∞
−∞
ϕ(x−sk)·(1 −Φ(x−sk−1)) ·F(x) dx . (3.4)
In the next step we exploit in (3.3) that Φ(x)is a positive and monotonically increasing
function, and in (3.4) we substitute xby x+γ, which yields
β≥Z∞
−∞
ϕ(x−sk−1)·(1 −Φ(x−sk−1)) ·F(x) dx
−Z∞
−∞
ϕ(x−sk−1)·(1 −Φ(x−sk−1+γ)) ·F(x) dx≥0.
The last inequality holds again since Φ(x)is a positive and monotonically increasing
function. Thus Lemma 1 is shown. B2
So from now on when considering the smoothed number of left-to-right maxima, we
will assume that input sequence Sis a sequence of monotonically increasing elements
from (0,1]. The main idea for computing the integral (3.2) is now to subdivide the interval
(0,1] into m=d1/δesmaller intervals of length δ(the last one possibly shorter). Here
δis a small parameter that is specified later. Then the sequence Sof unperturbed input
elements is subdivided into msubsequences S1,...,Smwhere S`contains all elements
s∈ S that lie in the `-th small interval, i.e.
S`=s∈ S (`−1) ·δ < s ≤`·δ.
Note that all subsequences S1,...,Smof Sare also monotonically increasing, and that
S= (S1,...,Sm)by Lemma 1. This enables us to utilize that
L(e
S)≤
m
X
`=1 L(e
S`),(3.5)
where e
S`is the sequence of perturbed elements to input sequence S`and L(e
S`)is the
number of left-to-right maxima in sequence e
S`.
The advantage of this approach is that for small enough δthe elements of a subsequence
e
S`behave almost as in the usual average case. Intuitively, the reason for this is that the
18
3.2 Upper Bounds for the Smoothed Case
unperturbed input elements lie very close together and that the density functions of the
perturbed elements differ only very little.
Indeed, we will apply for each subsequence e
S`the average case bounds as if the elements
were identically distributed random numbers. Of course we make here an error but this
can easily be fixed. Then by (3.5) and a summation over all subsequences e
S`, we obtain an
upper bound on the smoothed number of left-to-right maxima for the whole sequence e
S.
In order to remedy the error between the smoothed number and the average number
of left-to-right maxima in subsequence e
S`we proceed as follows. In a first step we cut
off the “tail” of the considered noise distribution and treat it separately, i.e. we bound the
tail probability (later denoted as Z) and count the expected number of elements from the
tail as left-to-right maxima. This gives us in the end an additive error depending on the
considered noise distribution and on δsince the probability of the tail depends on these,
too.
For the remaining part of the probability distribution, we observe then that the smoothed
number and the average number of left-to-right maxima for each subsequence differ only
by a multiplicative factor rwhich depends on the choice of δ. A multiplication of the
average number of left-to-right maxima with rremedies then the error on the smoothed
number of left-to-right maxima.
However, we have here a trade-off between δand the number of subsequences. When
we choose δsmall in order to make the tail of the noise distribution not too heavy and thus
the additive error small, the number of subsequences (which is m=d1/δe) and therefore
the smoothed number of left-to-right for the whole sequence becomes large.
In order to proceed with the analysis, we will now fix one of the subsequences and
without loss of generality we consider the first subsequence S1. Let n1denote the number
of elements in subsequence S1, i.e. S1= (s1, . . . , sn1). For an element skin S1we know
that
Prheskis left-to-right max. in e
S1i=Z∞
−∞
ϕ(x−sk)·
k−1
Y
j=1
Φ(x−sj) dx
≤Z∞
−∞
ϕ(x−sn1)·Φ(x−s1)k−1dx
≤Z∞
−∞
ϕ(x)·Φ(x+δ)k−1dx , (3.6)
wherethelaststepfollows by substituting xby x+sn1and the observationthatsn1−s1≤δ.
We could easily solve this integral if instead of ϕ(x)there would occur a ϕ(x+δ). Thus
in a next step we will expand the integrand in (3.6) by a multiplication:
ϕ(x) = ϕ(x+δ)·ϕ(x)
ϕ(x+δ).
19
3 Left-to-Right Maxima
Where the ratio ϕ(x)/ϕ(x+δ)is bounded we can extract it from inside the integral and
solve the remaining integral as in the average case analysis. Let
Zϕ
δ,r := x∈IR ϕ(x)
ϕ(x+δ)> r
denote the subset of IR that contains all elements xfor which the ratio ϕ(x)/ϕ(x+δ)is
larger than some positive constant r. To avoid difficulties with zeros of ϕ, we will use
alternatively the definition Zϕ
δ,r := {x∈IR ϕ(x)> r ·ϕ(x+δ)}. The constant ris
the same as seen earlier, i.e. it is the multiplicative error between the average case and
smoothed case number of left-to-right maxima.
We can now formulate and prove the main lemma of this section as follows.
Lemma 2 For a fixed continuous probability distribution with integrable density function
ϕand for positive parameters δand rdefine the set Zϕ
δ,r := {x∈IR ϕ(x)> r·ϕ(x+δ)}.
Let Zbe the probability of set Zϕ
δ,r, i.e.
Z:= ZZϕ
δ,r
ϕ(x) dx .
For random noise from the fixed probability distribution, the smoothed number of left-
to-right maxima over all input sequences Sof nelements from (0,1] is
max
S
EhL(e
S)i≤max r·1
δ·H(n) + n·Z,H(n).
Proof. Let again m:= d1/δe. Without loss of generality we consider again the input
subsequence S1. We saw already in (3.6) that for an element sk∈ S1it is
Prheskis left-to-right max. in e
S1i≤Z∞
−∞
ϕ(x)·Φ(x+δ)k−1dx .
We can now compute this integral in the following way
(3.6) = ZIR
ϕ(x)·Φ(x+δ)k−1dx
=ZIR−Zϕ
δ,r
ϕ(x)·Φ(x+δ)k−1dx+ZZϕ
δ,r
ϕ(x)·Φ(x+δ)k−1dx
≤ZIR−Zϕ
δ,r
ϕ(x+δ)·ϕ(x)
ϕ(x+δ)·Φ(x+δ)k−1dx+ZZϕ
δ,r
ϕ(x) dx
≤r·ZIR−Zϕ
δ,r
ϕ(x+δ)·Φ(x+δ)k−1dx+Z
≤r·ZIR
ϕ(x)·Φ(x)k−1dx+Z=r·1
k+Z.
20
3.2 Upper Bounds for the Smoothed Case
It follows for input subsequence S1that
EhL(e
S1)i≤
n1
X
k=1
(r·1
k+Z) = r·H(n1) + n1·Z .
Analogous results hold also for subsequences S2,...,Sm, and by (3.5) it follows that
EhL(e
S)i≤
m
X
`=1
EhL(e
S`)i≤
m
X
`=1
r·H(n`) + n`·Z ≤ r·m·H(n) + n·Z .
Since the analysis is independent of the considered input sequence it holds for any
monotonically increasing input sequence S. To assure that the smoothed number of left-
to-right maxima does not drop below the average number, we take the maximum over
r·m·H(n) + n·Z and H(n). Thus Lemma 2 follows immediately. B2
3.2.1 Gaussian Normal Noise
In this subsection we show how to apply Lemma 2 to the case of normally distributed
noise. Let now
ϕ(x) := 1
√2π σ ·e−x2
2σ2
denote the density function for the standard Gaussian normal distribution with expectation
0and variance σ2, denoted by N(0, σ).
Theorem 2 For random noise from the standard Gaussian normal distribution N(0, σ),
the smoothed number of left-to-right maxima over all input sequences Sof nelements
from (0,1] is
max
S
EhL(e
S)i≤max ne3·lpln(n)/σm·H(n)+1,H(n)o
=O1
σ·log(n)3/2+ log(n).
Proof. In order to utilize Lemma 2 we choose δ:= σ/pln(n). For x≤σp2 ln(n)it
holds that
ϕ(x)/ϕ(x+δ) = e(δ/σ2)·x+δ2/(2σ2)=ex/(σ√ln(n))+1/(2 ln(n)) ≤e√2+1/(2 ln(n)) ≤e3.
Therefore, if we choose r:= e3we can conclude that Zϕ
δ,r ⊂[σp2 ln(n),∞). Now, we
will derive a bound on Z=RZϕ
δ,r ϕ(x) dxby using the following claim.
Claim 1 For the density function ϕ(x)of the Gaussian normal distribution N(0, σ)it holds
for any k≥1/√2πthat Z∞
σ·k
ϕ(x) dx≤e−k2/2.
21
3 Left-to-Right Maxima
The proof of this claim is deferred to the end of this subsection. With the claim it follows
that
Z=ZZϕ
δ,r
ϕ(x) dx≤Z∞
σ√2 ln(n)
ϕ(x) dx≤1
n.
Altogether we can apply Lemma 2 with the parameters δ=σ/√ln n,r=e3, and
Z= 1/n. It follows that for every input sequence Sthe expected number of left-to-right
maxima in the perturbed sequence e
Sunder Gaussian normal noise is at most
EhL(e
S)i≤max ne3·lpln(n)/σm·H(n)+1,H(n)o.
B2
We observe that it does not make sense to apply Theorem 2 for arbitrary values of
σ. If σ≥Ω(plog(n)) we obtain the average case bound of O(log(n)), and thus we
cannot distinguish in the analysis between the usual average case and the smoothed case.
If σ≤ O(log(n)3/2/n)we obtain an expected number of left-to-right maxima of O(n).
This means that for variances this small the perturbation of (worst case input) instances
does not show any effect in our analysis.
It remains now to prove Claim 1.
Proof of Claim 1. By a linear substitution t=x2/(2σ2),dx=σ/√2tdtwe get that
Z∞
σ·k
ϕ(x) dx=Z∞
σ·k
1
√2π σ ·e−x2
2σ2dx
=1
√2π·Z∞
k2/2
e−t·1
√2tdt
≤1
√2π·1
k·e−k2/2≤e−k2/2.
B2Claim 1
3.2.2 Uniform Noise
We consider now random noise that is uniformly distributed in the interval [−, ]. The
corresponding density function is given by
ϕ(x) := (1
2if x∈[−, ]
0else .
22
3.2 Upper Bounds for the Smoothed Case
Theorem 3 For random noise from the uniform distribution in [−, ], the smoothed num-
ber of left-to-right maxima over all input sequences Sof nelements from (0,1] is
max
S
EhL(e
S)i≤max (2·&rn·H(n)
2',H(n))
=O rn·log(n)
+ log(n)!.
Proof. Again we want to utilize Lemma 2 . We choose r= 1, then it follows immediately
that for 0< δ < 2we have Zϕ
δ,r =x∈IR ϕ(x)> ϕ(x+δ)= [−δ, ]. We can now
compute Zwhich is
Z=Z
−δ
1
2dx=δ
2.
With Lemma 2 it follows that the smoothed number of left-to-right maxima is at most
d1/δe·H(n) + n·δ/(2). If we choose δ=p2·H(n)/n we get that for every input
sequence Sthe expected number of left-to-right maxima in the perturbed sequence e
Sunder
uniform noise is at most
max
S
EhL(e
S)i≤max (2·&rn·H(n)
2',H(n)).
B2
Again we observe that Theorem 3 is not applicable for uniform distributions with arbi-
trary values of . If ≥Ω(n/ log(n)) we obtain the average case bound of O(log(n)) and
we cannot distinguish in our analysis between the usual average case and the smoothed
case. If ≤ O(log(n)/n)we obtain an expected number of left-to-right maxima of O(n)
and we cannot distinguish if a (worst case) instance is perturbed or not.
3.2.3 Unimodal Noise Distributions
In this section we investigate upper bounds for general noise distributions that fulfill the
following condition. We denote a continuous probability distribution as unimodal if the
corresponding integrable density function is bounded and monotonically increasing on
IR≤0and monotonically decreasing on IR≥0. In other words, the density function has a
single peak at x= 0. Note that the following analysis holds also for distributions that
have a single peak not at x= 0 but at any other x. But for ease of notation we restrict the
analysis to the first case. The following theorem gives now an upper bound on the number
of left-to-right maxima for arbitrary unimodal noise distributions with peak at x= 0.
23
3 Left-to-Right Maxima
Theorem 4 For random noise from a unimodal continuous probability distribution with
density function ϕ, the smoothed number of left-to-right maxima over all input sequences
Sof nelements from (0,1] is
max
S
EhL(e
S)i≤max n7·pn·H(n)·ϕ(0),H(n)o
=Opn·log n·ϕ(0) + log n.
Proof. Since we consider here monotonic probability distributions, ϕ(0) denotes the
(global) maximum of the density function. In order to utilize Lemma 2 we choose r:= 2
whereas δwill be chosen later.
Again we need to derive a bound for Z=RZϕ
δ,r ϕ(x) dx. We want now to find a
covering for set Zϕ
δ,r by defining sets Zi, i ∈IN, such that SiZi⊇ Zϕ
δ,r. Then we will
estimate RSiZiϕ(x) dxin order to derive an upper bound for Z.
We observe that for x+δ≤0we have ϕ(x)≤ϕ(x+δ)because of the monotonicity
of ϕ. Hence, it is Zϕ
δ,r ⊆[−δ, ∞). Now we partition [−δ, ∞)into intervals of the form
[(`−1) ·δ, ` ·δ]for `∈IN0. We define Zito be the i-th such interval that has a non-empty
intersection with Zϕ
δ,r. If less than iintervals have a non-empty intersection then Ziis the
empty set. By this definition we obtained the wanted covering, and it is SiZi⊇ Zϕ
δ,r as
desired.
We can now bound RSiZiϕ(x) dxas follows. First suppose that all Zi⊂IR≥0. Let zi
denote the start of interval Zi, i.e. Zi= [zi, zi+δ]. Then we obtain that
ZZi
ϕ(x) dx≤δ·ϕ(zi),
because Ziis of length δand ϕ(x)takes its maximum value within interval Ziat ϕ(zi). If
Z1= [−δ, 0] it follows that RZ1ϕ(x) dx≤δ·ϕ(0) for similar reasons.
Furthermore, it holds that ϕ(zi+2)≤1/2·ϕ(zi)for all i∈IN. To see this consider
another point in interval Zithat belongs also to Zϕ
δ,r, e.g. ˆzi∈ Zi∩Zϕ
δ,r. It is now
ϕ(zi)≥ϕ(ˆzi)>2·ϕ(ˆzi+δ)≥2·ϕ(zi+2),
where we utilize that ˆzi∈ Zϕ
δ,r ={x∈IR ϕ(x)/ϕ(x+δ)> r}, that r= 2 and that
ˆzi+δ≤zi+2.
Now we can combine everything and we obtain
ZSiZi
ϕ(x) dx≤ZZ1
ϕ(x) dx+X
i∈IN ZZ2i−1
ϕ(x) dx+X
i∈IN ZZ2i
ϕ(x) dx
≤δ·ϕ(0) + X
i∈IN
δ·ϕ(z2i−1) + X
i∈IN
δ·ϕ(z2i)
≤δ·ϕ(0) + X
i∈IN
1
2i−1·δ·ϕ(z1) + X
i∈IN
1
2i−1·δ·ϕ(z2)
≤δ·ϕ(0) + 2δ·ϕ(z1)+2δ·ϕ(z2)≤5δ·ϕ(0) .
24
3.3 Lower Bounds for the Smoothed Case
Figure 3.2: The curves of two density functions are depicted for probability distributions
causing a high smoothed complexity.
It follows that Z ≤ 5δ·ϕ(0) and Lemma 2 yields that the smoothed number of left-to-
rightmaximaisatmost2·d1/δe·H(n)+n·5δ·ϕ(0). Now, choosingδ:= pH(n)/(n·ϕ(0))
gives that for every input sequence Sthe expected number of left-to-right maxima in the
perturbed sequence e
Sunder noise from a unimodal distribution is at most
EhL(e
S)i≤max n7·pn·H(n)·ϕ(0),H(n)o.
B2
It remains to mention that the Gaussian normal and uniform noise distributions are of
course also unimodal distributions. For uniform noise, the Theorem 3 follows up to a
constant factor also from this result since for the uniform distribution in an interval [−, ]
the maximal density is clearly 1/(2). If we consider here Gaussian normal noise, we
obtain a much worse result than the one shown in Theorem 2 since the maximal density is
1/(√2π σ).
3.3 Lower Bounds for the Smoothed Case
To complete this chapter about the left-to-right maxima we will consider the tightness of
the just seen upper smoothed case bounds. Of course, a general lower bound arises from
the average case bound of Θ(log(n)). For the case of Gaussian normal noise this leaves
only a gap of roughly plog(n)to the upper bound of O1/σ ·log(n)3/2+ log(n).
For the case of uniform noise this general lower bound reveals a much larger gap to the
upper bound of O(pn·log(n)/+log(n)). In the following we construct an explicit input
sequence for which a large smoothed number of left-to-right maxima is achieved for the
uniform noise distribution. This closes the gap to the upper bound up to a factor of roughly
plog(n).
In fact, the following theorem holds not only for the uniform distribution but for all con-
tinuous probability distributions whose density functions have bounded support. Without
25
3 Left-to-Right Maxima
s1s2s3s4
n4/
n8/
0...
Figure 3.3: Input sequence for the lower bound construction for `= 4.
loss of generality we assume that the density functions are non-zero only in the interval
[−, ]and zero everywhere else, see also Figure 3.2 which shows two examples of such
density functions. Of course, the uniform distribution belongs to this class of distributions,
too.
Theorem 5 Forallcontinuousprobability distributionswith density function ϕof bounded
support, i.e. ϕis non-zero only in the interval [−, ], the smoothed number of left-to-right
maxima over all input sequences Sof nelements from (0,1] is
max
S
EhL(e
S)i≥min pn/ ·1−Φ−p/n√n·, n,
where Φdenotes the distribution function of ϕ. If the probability distribution is unimodal
and ϕ()6= 0 it is
max
S
EhL(e
S)i≥min n(1 −1/e)·lpn·ϕ()m, no.
Proof. Consider the following input sequence S= (s1, . . . , sn)of nelements. For some
`∈IN, ` ≤n, subdivide Sinto m:= dn/` esubsequences S1,...,Smof length `, the last
subsequence possibly shorter. Let all elements in each particular subsequence have equal
values such that the elements in a subsequence Sihave value i·`/n, i.e. s(i−1)·`+1 =··· =
si·`=i·`/n for all 1≤i≤m, see also Figure 3.3.
Let now ρ1, . . . , ρnbe nindependent and identically distributed random variables from
a continuous probability distribution whose density function ϕhas bounded support only
in the interval [−, ]. Again let esk=sk+ρkdenote the perturbed element to input element
sk, for all 1≤k≤n.
If element skis from subsequence Si, i.e. sk=i·`/n, we observe that eskis distributed
in the interval [i·`/n −, i ·`/n +]after the perturbation. Consider now the case that esk
26
3.4 Conclusion
is large, i.e. esk>(i−1) ·`/n +. It follows that eskis also larger than all elements in the
preceding subsequences e
S1,..., e
Si−1. So if there is at least one element in subsequence e
Si
that has a value larger than (i−1) ·`/n +, then there is also at least an element in e
Sithat
is a left-to-right maximum.
For the input element skin subsequence Si, it is now
Pr[esk≤(i−1) ·`/n +] = Pr[i·`/n +ρk≤(i−1) ·`/n +]
=Pr[ρk≤−`/n ] =: Φ(−`/n).
It follows then
Prhno element in e
Siis larger than (i−1) ·`/n +i≤Φ(−`/n)`,(3.7)
and thus
EhL(e
S)i≥m·1−Φ(−`/n)`.
Choosing `=√n·we get that m=dn/` e=pn/. The first part of the theorem
follows then immediately. Note that the smoothed number of left-to-right maxima cannot
exceed n.
For unimodal noise distributions with density function ϕ()6= 0 we can also conclude
that 1−Φ(−`/n)≥ϕ()·`/n and thus Φ(−`/n)≤(1 −ϕ()·`/n). Choosing now
`=lpn/ϕ()mwe get that (3.7) ≤1/e and therefore we have
EhL(e
S)i≥(1 −1/e)·lpn·ϕ()m.
B2
From the Theorem, the following Corollary follows immediately.
Corollary 1 For random noise from the uniform distribution in the interval [−, ], the
smoothed number of left-to-right maxima over all input sequences Sof nelements from
(0,1] is at least
max
S
EhL(e
S)i≥min n(1 −1/e)·lpn/(2)m, no
= Ω min npn/, no .
3.4 Conclusion
The results of this chapter are summarized in the following tabular overview. The bounds
are given in O-notation.
27
3 Left-to-Right Maxima
Upper Bounds Lower Bounds
Gaussian N(0, σ)O(1/σ)·log(n)3/2+ log(n)Ωlog(n)
uniform in [−, ]Opn·log(n)/ + log(n)Ωmin pn/, n
An interesting result is definitively that for different noise distributions we obtain a dif-
ferent smoothed complexity of the left-to-right maxima problem. We see that for Gaus-
sian normal noise of variance σ2, the smoothed number of left-to-right maxima is poly-
logarithmic in the number of elements and polynomial in 1/σ. Interestingly, for uniform
noise in an interval of length 2we obtain that the smoothed number of left-to-right max-
ima is polynomial in the number of elements and 1/.
Since both bounds are only a factor of roughly plog(n)away from corresponding lower
bounds this discrepancy is really significant. This result is especially suprising since in the
average case we obtain an expected number of left-to-right maxima of Θ(log(n)) for all
continuous probability distributions.
28
4 Extreme Points
The convex hull of a point set in d-dimensional Euclidean space is one of the fundamental
combinatorial structures in computational geometry. In this chapter we are interested in
the number of extreme points of the convex hull of a point set.
Definition 4 (Convex Hull – Extreme Points) Given is a set Pof npoints p1, . . . , pn,
where pk∈IRdfor all 1≤k≤n. The convex hull of Pis the smallest convex set
containing all points in Pand is denoted by conv(P), i.e.
conv(P) := (n
X
i=1
λi·piλi≥0,
n
X
i=1
λi= 1).
If the points in Pare in general position (no d+ 1 points lie on a common hyperplane)
the convex hull of Pis a d-dimensional (simplicial) polytope. The faces of conv(P)of
dimension 1are called vertices or extreme points and their number is denoted by V(P).
Analogously to Chapter 3, the main contribution in this chapter is a rather general lemma
by which upper bounds on the smoothed number of extreme points can be obtained for
noise from continuous d-dimensional product probability distributions. Again we apply
this lemma explicitly to the cases that the random noise comes from the standard Gaussian
normal distribution and from the uniform distribution in a hypercube.
Related Work. The convex hull of a point set in d-dimensional Euclidean space and its
properties have been studied extensively in the last decades.
To compute the convex hull of a point set Pmeans to compute a description of the
polytope formed by conv(P). A convex polytope can be described in many ways where
Seidel [Sei97] distinguishes between purely geometric and combinatorial descriptions. By
purely geometric it is meant that the output consists only of the vertices (= extreme points)
and/or the facets (= (d−1)-dimensional faces) of the polytope (given by coordinates and/or
defining inequalities, respectively). A combinatorial description contains also further in-
formation about the facial structure, for example given by a Hasse diagram of the face
lattice of the polytope. To compute this can be hard since McMullen [McM70] showed
that the number of faces in a polytope is at worst Θ(nbd/2c).
For geometric descriptions the case is different. To compute the extreme points of a
convex hull is also known as the irredundancy problem. A point is extreme (or irredundant)
if it cannot be represented as a convex combination of the remaining points in P. To test
29
4 Extreme Points
whether a point is irredundant one has to solve for all ninput points a linear programming
problem in dvariables with n−1constraints.
For fixed dimension dthis can be done in linear time e.g. by Megiddo’s [Meg84] linear
programming algorithm, which leads immediately to a an algorithm for the extreme point
problem that runs in O(n2)time. Matouˇ
sek could reduce this bound to O(n2−2/(bd/2c+1) ·
log(n)O(1))by using a data structure for linear programming queries [Mat93] that exploits
that the linear programs are closely related. One year later, Clarkson [Cla94] developed
a simple output-sensitive algorithm of run-time O(n· V(P)) by reducing the number of
involved constraints for every linear program from n−1to V(P).
Chan [Cha96b] combined this idea with Matouˇ
sek’s data structure and obtained for
fixed d > 3an O(n·log(V(P))d+2 + (n·V(P))1−1/(bd/2c+1) ·log(n)O(1))time algorithm
for the extreme point problem. Since an optimal output-sensitive algorithm is of time
O(n·log(V(P))) this algorithm is almost optimal (up to a factor of log(V(P))O(1)) when
V(P) = O(n1/bd/2c/log(n)K)for a sufficiently large constant K.
In dimensions 2 and 3, there is no need to distinguish between combinatorial and purely
geometric polytope descriptions since they cannot differ much in terms of their sizes. Out-
put sensitive algorithms with optimal time bound O(n·log(F(P))) were given in the
2-dimensional case by Kirkpatrick and Seidel [KS86] and in the 3-dimensional case by
Chazelle and Matouˇ
sek [CM95], where F(P)denotes the number of all faces of conv(P).
Also Chan [Cha96a] obtained an algorithm of this time bound for dimensions 2 and 3 by
similar techniques as described above.
Having optimal or almost optimal output-sensitive algorithms it remains to answer the
question about the quantitative behavior of the extreme points. Several researchers have
treated the combinatorial structure of the convex hull of nrandom points. In 1963/64,
R´
enyi and Sulanke [RS63, RS64] were the first to consider the area and perimeter (length
of the boundary) and the number of extreme points of the convex hull in expectation. For
the latter they showed the following results. In the plane, let Pbe a set of nindependent
and identically distributed points uniformly chosen from a bounded convex set with contin-
uously differentiable boundary (e.g. a sphere or ellipse). The expected number of vertices
is then Θ(n1/3). If the points are uniformly chosen from a convex polygon the expected
number of vertices is Θ(log(n)), and if the points are chosen from the 2-dimensional Gaus-
sian normal distribution the expected number of vertices is Θ(plog(n)).
This work was continued by several other authors, e.g. by Efron [Efr65], Raynaud
[Ray65, Ray70], Carnal [Car70], and Affentranger and Wieacker [AW91], and extended
to higher dimensions and other probability distributions. For instance, Raynaud [Ray70]
considered the case that the points in Pare chosen uniformly from the d-dimensional unit
ball and he showed that E[V(P)] = Θ(n(d−1)/(d+1)). For the case that the points are
chosen uniformly from any d-dimensional polytope (e.g. the d-dimensional hypercube)
Affentranger and Wieacker showed a bound of E[V(P)] = Θ(log(n)d−1). If the points
are chosen from the d-dimensional Gaussian normal distribution again Raynaud [Ray70]
proved E[V(P)] = Θ(log(n)(d−1)/2). In all these results dis considered to be a constant.
30
Generally, for continuous d-dimensional product probability distributions Bentley et al.
[BKST78] and Buchta et al. [BTT85] derived an upper bound of O(log(n)(d−1))on the
expected number of extreme points (this includes of course the Gaussian normal and the
uniform distribution in a hypercube). Har-Peled [Har98] gave another nice proof of this
result, and interesting for us is that these proofs are based on the computation of the ex-
pected number of maximal points (see below). Indeed, in our analysis we also exploit the
close connection between extreme and maximal points.
Maximal Points. The problem of counting the number of extreme points is very closely
related to the problem of counting the number of maximal points which we will exploit also
for our analysis. in order to define maximal points we need to introduce also the notion of
orthants of a point.
Definition 5 (Orthant of a Point) Consider a point p= (p(1), . . . , p(d))∈IRd. For any
subset I ⊆ [d] = {1, . . . , d}let
oI(p) := Y
i∈I −∞, p(i)×Y
i/∈I p(i),∞
denote the orthant centered at point pthat is introduced by the index set I.
Definition 6 (Maximal Points) Given is a set Pof npoints p1, . . . , pnin IRd. A point
pi∈ P,1≤i≤n, is denoted a maximal point of P, if there is an index set I ⊆ [d]such
that oI(pi)is empty, i.e. no other point of P −{pi}lies in oI(pi).
Let D(P)denote the number of maximal points of set P.
The reason for the close relation between extreme points and maximal points lies now
in the following observation. A point p∈ P is not maximal, if each of the 2dorthants
centered at pcontains at least one other point. In this case, pis not extreme either, see also
Figure 4.1. It follows immediately that the number of maximal points is an upper bound
on the number of extreme points, i.e.
V(P)≤ D(P).(4.1)
Buchta [Buc89] showed that the expected number of maximal points for a set Pof n
independent and identically distributed points chosen from a continuous d-dimensional
product probability distribution is Θ(log(n)d−1). This holds of course also for the uniform
distribution in a d-dimensional hypercube and the d-dimensional Gaussian normal distribu-
tion. Dwyer [Dwy90] considered the case that the points are chosen from a d-dimensional
ball and proved that E[D(P)] = Θ(n(d−1)/d).
The problem of counting the number of maximal points as it is treated here is essentially
an extension of the one-dimensional left-to-right maxima problem (see the previous Chap-
ter 3) to arbitrary dimensions. This will become very clear by a closer look at the analysis.
31
4 Extreme Points
o (p)
1,2
o (p)
o (p)
f
1
f g
g
o (p)
2
f g
f g
Figure 4.1: On the left side a point p∈IR2and its four orthants are depicted. In 2dimen-
sions, they are also called quadrants. On the right side we see, that extreme
points are also maximal points.
Indeed, the way how we analyze the maximal points is almost analogous to the way how
the left-to-right maxima were treated. Hence the chapters are almost equally structured.
Outline. In Section 4.1 we will consider the average case number of extreme points and
present another proof that E[V(P)] = O(log(n)d−1)for points chosen from continuous d-
dimensional product probability distributions. Our proof makes extensive use of integrals,
which seems to be very helpful for a better readability and understanding of the smoothed
case analysis.
The smoothed case analysis is then presented in Section 4.2. The main contribution is
a very general lemma which provides upper bounds for the smoothed number of extreme
points when the random noise comes from a continuous d-dimensional product probability
distribution. This lemma is a d-dimensional version of the main Lemma 2 in Section 3.2.
The lemma is then explicitly applied for the cases that the random noise comes from the
Gaussian normal distribution of variance3σ2and the uniform distribution in a hypercube
of side-length 2. For these noise distributions we get upper bounds on the smoothed
number of extreme points of O(1/σ)d·log(n)(3/2)·d−1and O(n·log(n)/)d/(d+1),
respectively.
In Section 4.3 the upper bounds are complemented by lower bounds. An explicit con-
struction is presented for which the smoothed number of extreme points under uniform
noise is large.
The chapter ends again with a brief summary and concluding remarks.
3Here the variance of the 1-dimensional Gaussian normal distribution of the components is meant.
32
4.1 Average Case Analysis
4.1 Average Case Analysis
In this section we will consider the case that Pis a set of nindependent and identically
distributed random points chosen from a continuous d-dimensional product probability
distribution over IRd. Let X= (X1, . . . , Xd)be a random vector from such a distribution
and let ϕ: IR →IR≥0be the 1-dimensional density function of the components of X. The
corresponding probability distribution function is then
Pr[X1≤x1, . . . , Xd≤xd] = Zxd
−∞ ···Zx1
−∞
ϕ(z1)···ϕ(zd) dz1··· dzd.
Note that all components of Xare mutually independent and identically distributed.
Examples for such continuous d-dimensional product probability distributions are the uni-
form distribution in a hypercube or the d-dimensional Gaussian normal distribution.
In this section we will show the following theorem.
Theorem 6 The expected number of maximal points in a set Pof nindependent and iden-
tically distributed random points in IRdchosen from a continuous d-dimensional product
probability distribution is
E[D(P)] ≤2d·
n
X
i1=1
1
i1
i1
X
i2=1
1
i2···
id−2
X
id−1=1
1
id−1
= Θ log(n)d−1.
By (4.1) we can immediately conclude that also the following theorem holds.
Theorem 7 The expected number of extreme points in a set Pof nindependent and iden-
tically distributed random points in IRdchosen from a continuous d-dimensional product
probability distribution is
E[V(P)] ≤ Olog(n)d−1.
We will now continue with the proof of Theorem 6.
Proof. First of all we recall that for an arbitrary point pk∈ P to be maximal it suffices
to have at least one empty orthant. Without loss of generality let us now fix the orthant
o[d](pk)for further considerations. Since a point has 2dorthants it follows by standard
union bound that
Pr[pkis maximal] = 2d·Pro[d](pk)is empty.
We will now show that
Pro[d](pk)is empty≤ H(n)d−1/n . (4.2)
By linearity of expectation the theorem follows then immediately.
33
4 Extreme Points
For reasons of better understanding let us first establish the 2-dimensional case. Con-
sider a point pk∈ P ⊂ IR2having the coordinates pk= (x, y). It follows that pk
has four orthants which are also called quadrants. The probability for any other point
pj∈ P − {pk}to be not in the quadrant o{1,2}(pk)=(−∞, x]×(−∞, y]is then equal
to the probability that the point pjlies in one of the three other quadrants of pk. These
three other quadrants are o{ }(pk) := [x, ∞)×[y, ∞),o{1}(pk) := (−∞, x]×[y, ∞), and
o{2}(pk) := [x, ∞)×(−∞, y].
It follows
Prpj∈o{ }(pk)=Prhp(1)
j≥xi·Prhp(2)
j≥yi= (1 −Φ(x)) ·(1 −Φ(y))
Prpj∈o{1}(pk)=Prhp(1)
j≤xi·Prhp(2)
j≥yi= Φ(x)·(1 −Φ(y))
Prpj∈o{2}(pk)=Prhp(1)
j≥xi·Prhp(2)
j≤yi= (1 −Φ(x)) ·Φ(y).
The probability for any point pj∈ P −{pk}to be not in o{1,2}(pk)is then given by
Prpj/∈o{1,2}(pk)
= (1 −Φ(x)) ·Φ(y) + (1 −Φ(x)) ·(1 −Φ(y)) + Φ(x)·(1 −Φ(y))
= 1 −Φ(x)·Φ(y).
Since there are n−1other points in P −{pk}the probability that o{1,2}(pk)is empty is
Pro{1,2}(pk)is empty=ZIR2
ϕ(x)·ϕ(y)·(1 −Φ(x)·Φ(y)
| {z }
=: z=z(x)
)n−1dxdy . (4.3)
This integral can be solved by two linear substitutions. In a first step we will substitute
1−Φ(x)·Φ(y) =: z=z(x), as indicated. Then it is dz=−ϕ(x)·Φ(y)·dxand this
yields the integral
(4.3) = ZIR Z1
1−Φ(y)
ϕ(y)
Φ(y)·zn−1dzdy=1
nZIR
ϕ(y)
Φ(y)·(1 −(1 −Φ(y)
| {z }
=: z
)n) dy . (4.4)
By the indicated second substitution 1−Φ(y) =: z=z(y)where dz=−ϕ(y)·dy,
we get
(4.4) = 1
nZ1
0
1−zn
1−zdz=1
nZ1
0
n−1
X
i=0
zidz=1
n
n−1
X
i=0 Z1
0
zidz
=1
n
n
X
i=1
1
i=H(n)
n,
34
4.1 Average Case Analysis
and thus (4.2) follows immediately for d= 2. The theorem is therefore shown for the
planar case.
We consider now the d-dimensional case. All the ideas and concepts needed are already
introduced in the 2-dimensional case. The presentation is thus rather short.
Again, we consider a particular point pk= (x(1), . . . , x(d))and fix one of its orthants,
again o[d](pk) := Qd
i=1(−∞, x(i)]. The probability for any other point pj∈ P − {pk}to
be not in o[d](pk)is given by
Prpj/∈o[d](pk)=X
I⊂[d]
Pr[pj∈oI(pk) ] = X
I⊂[d]Y
i∈I
Φ(x(i))Y
i/∈I
(1 −Φ(x(i))) .
This expression can be simplified by using the following claim.
Claim 2
X
I⊂[d]Y
i∈I
Φ(x(i))Y
i/∈I
(1 −Φ(x(i))) = 1 −Φ(x(1))···Φ(x(d))
The proof of claim 2 is done by an induction on dand is deferred to the end of this
section.
It follows that
Pro[d](pk)is empty=
ZIRd
ϕ(x(1))···ϕ(x(d))·(1 −Φ(x(1))···Φ(x(d))
| {z }
=: z=z(x(1))
)n−1dx(1) ··· dx(d)(4.5)
which is the d-dimensional analogue to (4.3).
Analogously to the 2-dimensional case, this integral can be solved by drepeated linear
substitutions. We will present here the first three substitutions for a better illustration of
the concept although the depiction is a little bit difficult.
The first substitution is already indicated, i.e. 1−Φ(x(1))···Φ(x(d)) =: z=z(x(1)).
35
4 Extreme Points
We get that dz=−ϕ(x(1))Φ(x(2))···Φ(x(d))dx(1) and it follows
(4.5) = ZIRd−1Z1
1−Φ(x(2))···Φ(x(d))
ϕ(x(2))···ϕ(x(d))
Φ(x(2))···Φ(x(d))·zn−1dzdx(2) ··· dx(d)
=1
nZIRd−1
ϕ(x(2))···ϕ(x(d))
Φ(x(2))···Φ(x(d))·(1 −(1 −Φ(x(2))···Φ(x(d))
| {z }
=: z=z(x(2))
)n) dx(2) ··· dx(d)
=1
nZIRd−2Z1
1−Φ(x(3))···Φ(x(d))
ϕ(x(3))···ϕ(x(d))
Φ(x(3))···Φ(x(d))·1−zn
1−zdzdx(3) ··· dx(d)
=1
n
n
X
i1=1
1
i1ZIRd−2
ϕ(x(3))···ϕ(x(d))
Φ(x(3))···Φ(x(d))·(1 −(1 −Φ(x(3))···Φ(x(d))
| {z }
=: z=z(x(3))
)i1) dx(3) ··· dx(d)
=1
n
n
X
i1=1
1
i1ZIRd−3Z1
1−Φ(x(4))···Φ(x(d))
ϕ(x(4))···ϕ(x(d))
Φ(x(4))···Φ(x(d))·1−zi1
1−zdzdx(4) ··· dx(d)
=1
n
n
X
i1=1
1
i1
i1
X
i2=1
1
i2ZIRd−3
ϕ(x(4))···ϕ(x(d))
Φ(x(4))···Φ(x(d))·(1 −(1 −Φ(x(4))···Φ(x(d))
| {z }
=: z=z(x(4))
)i2) dx(4) ··· dx(d)
=··· =1
n
n
X
i1=1
1
i1
i1
X
i2=1
1
i2···
id−2
X
id−1=1
1
id−1≤H(n)d−1
n.
Therefore, (4.2) is shown and the theorem follows immediately. B2
It remains to show Claim 2 which will be done now.
Claim 2 X
I⊂[d]Y
i∈I
Φ(x(i))Y
i/∈I
(1 −Φ(x(i))) = 1 −
d
Y
i=1
Φ(x(i))
Proof of Claim 2. By induction on d.
For d= 2, it follows immediately that the claimed equality holds. The induction step
d−1→dfollows also easily. For ease of notation, we use the following abbreviation.
Let
f(d) := X
I⊂[d]Y
i∈I
Φ(x(i))Y
i/∈I
(1 −Φ(x(i))) .
36
4.2 Upper Bounds for the Smoothed Case
It is then
f(d) = f(d−1) ·Φ(x(d)) + f(d−1) ·(1 −Φ(x(d))) +
d−1
Y
i=1
Φ(x(i))·(1 −Φ(x(d)))
= (1 −
d−1
Y
i=1
Φ(x(i))) ·(Φ(x(d)) + (1 −Φ(x(d)))) +
d−1
Y
i=1
Φ(x(i))−
d
Y
i=1
Φ(x(i))
= 1 −
d
Y
i=1
Φ(x(i)),
which concludes the proof. B2Claim 2
4.2 Upper Bounds for the Smoothed Case
In this section we consider the smoothed number of extreme points. A general lemma for
random noise from continuous d-dimensional product probability distributions is derived
and explicitly applied to noise from the Gaussian normal and the uniform distribution in a
hypercube.
We start with a formal description of the perturbation. Consider a set Pof input points
p1, . . . , pdwhere all input points come from the unit hypercube [0,1]dfor reasons of nor-
malization. Let r1, . . . , rdbe independent and identically distributed random d-vectors
from a fixed continuous d-dimensional product probability distribution. We denote the
random vectors as noise vectors and their distribution as the noise distribution. The set of
perturbed points e
P={ep1,...,epd}is then given by
epk=pk+rk,for 1≤k≤d .
We observe that each perturbed point is itself a random vector from a continuous d-
dimensional probability distribution of the following kind. Consider the input point pk
and its corresponding perturbed point epk=pk+rkwhere rkis a random vector from a
fixed noise distribution. The noise distribution is the d-fold product of a 1-dimensional
probability distribution and all the components of rkare from this same 1-dimensional
distribution. Let ϕ: IR →IR be the 1-dimensional integrable density function of the 1-
dimensional distribution of the components of the random noise and let Φ : IR →[0,1] be
the corresponding distribution function.
The components of epkare not anymore from an identical but from slightly different prob-
ability distributions. The distributions of the components of epkdepend on the components
of the input point pk, e.g., the 1-dimensional density function of the i-th component of epkis
ϕ(x−p(i)
k)and the corresponding distribution function is Φ(x−p(i)
k), for all 1≤i≤d. The
density and distribution functions of the components of epkare thus slightly shifted copies
37
4 Extreme Points
of the density and distribution function of the 1-dimensional noise distribution, namely of
ϕand Φ, respectively.
In this sense, also e
Pis a set of independent but not identically distributed random points
and the distribution of a particular point epkis the d-fold product of similar but slightly
shifted 1-dimensional distributions.
Now we will start with the actual analysis of the smoothed number of extreme points.
Indeed, the approach is the same as for the average case analysis in the previous Section
4.1. Instead of extreme points we will again consider maximal points to upper bound
the number of extreme points. As before we will bound the probability that for a fixed
input point pkthe perturbed point epkis maximal by considering a fixed orthant of epkand
computing the probability that this orthant is empty.
Let the perturbed point have the coordinates epk:= (x(1), . . . , x(d)). Without loss of
generality we fix again orthant o[d](epk) = Qd
i=1(−∞, x(i)]. We will now derive an integral
expression for the probability that o[d](epk)is empty. For any other input point pj∈ P −
{pk}it holds that
Prepj/∈o[d](epk)=X
I⊂[d]
Pr[epj∈oI(epk) ]
=X
I⊂[d]Y
i∈I
Φ(x(i)−p(i)
j)Y
i/∈I
(1 −Φ(x(i)−p(i)
j))
= 1 −Φ(x(1) −p(1)
j)···Φ(x(d)−p(d)
j)
where the last step follows by Claim 2. This yields
Pro[d](epk)is empty=ZIRd
ϕ(x(1) −p(1)
k)···ϕ(x(d)−p(d)
k)·(4.6)
Y
j6=k1−Φ(x(1) −p(1)
j)···Φ(x(d)−p(d)
j)dx(1) ··· dx(d),
which is the “smoothed” analogue to (4.5).
The approach to solve this integral is very similar to the approach in Section 3.2 where
we considered the smoothed number of left-to-right maxima. The main idea is to subdivide
the unit hyper-cube into m:= d1/δedsmaller axis-aligned hypercubes of side length δ.
Then the input set Pis divided into sets P1,...,Pmwhere P`is the subset of Pthat is
located in the `-th small hypercube, where some ordering among the small hypercubes is
assumed. Now we can compute for all subsets P`the expected number of maximal points
and exploit that
EhV(e
P)i≤EhD(e
P)i≤
m
X
`=1
EhD(e
P`)i.(4.7)
The motivation for this approach is the same as in the previous chapter. Intuitively, the
advantage is that for small enough δthe input points of a subset P`lie so close together
that after perturbation the points behave almost as in the random average case.
38
4.2 Upper Bounds for the Smoothed Case
Note that differently to Section 3.2 it is not necessary to establish an analogue to lemma
1. The reason is that the number of left-right-maxima in a sequence is depending on the
ordering of the sequence. This is of course not the case for the number of extreme/maximal
points since this number is independent of the ordering in which the input points are con-
sidered.
Without loss of generality assume now that the input subset P`lies in the small hyper-
cube [0, δ]dand that P`is of magnitude n`. Consider pk∈ P`, and let ¯
δ= (δ, . . . , δ)and
¯
0 = (0,...,0). The integral in (4.6) can be simplified by the following observation. The
probability that for any other point pj∈ P`−{pk}the perturbed point epjlies not in o[d](epk)
is maximized if pk=¯
0and pj=¯
δ. This yields
Pro[d](epk)is empty≤ZIRd
ϕ(x(1))···ϕ(x(d))·(4.8)
(1 −Φ(x(1) −δ)···Φ(x(d)−δ))n`−1dx(1) ··· dx(d).
In order to solve the integral (4.8) we will expand the product of density functions by a
multiplication in the following way
ϕ(x(1))···ϕ(x(d)) = ϕ(x(1) −δ)···ϕ(x(d)−δ)·ϕ(x(1))
ϕ(x(1) −δ)··· ϕ(x(d))
ϕ(x(d)−δ).(4.9)
If now the ratios ϕ(x)/ϕ(x−δ)were bounded by some parameter rwe could replace in
the integral (4.8) the ratios by the parameter rand solve the remaining integral very easily
as seen in the average case analysis in the previous section. In the following lemma this is
actually done, namely to identify the regions where the ratios of densities are bounded by
rand where they exceed this bound, and to solve the integral (4.8) for both regions.
The bounded ratios of density functions formalize what was meant when writing “be-
have almost as in the average case”. The parameters δand renable us to trade between the
number of subsets mand the size of the regions where the ratios are not bounded by r.
Now we can state the main lemma of this section which is also a d-dimensional analogue
to Lemma 2, the main lemma about the smoothed number of the left-to-right maxima.
Lemma 3 For a fixed continuous d-dimensional product probability distribution with one
dimensional density function ϕand for positive parameters δand rdefine the set
Zϕ
δ,r := {x∈IR |ϕ(x)> r ·ϕ(x−δ)}.
Let Zbe the probability of set Zϕ
δ,r, i.e., let
Z:=
d−1
X
i=0 d
iZZϕ
δ,r ···ZZϕ
δ,r
| {z }
d−i
ZIR−Zϕ
δ,r ···ZIR−Zϕ
δ,r
| {z }
i
ϕ(x(1))···ϕ(x(d)) dx(1) ··· dx(d).
39
4 Extreme Points
For random noise from the fixed probability distribution, the smoothed number of ex-
treme points over all input sets Pof npoints from [0,1]dis
max
P
EhV(e
P)i≤max 2d·rd·d1/δed·H(n)d−1+n·Z,H(n)d−1.
Proof. As already described earlier we plan to exploit inequality (4.7) and consider
therefore the set P`⊂ P of n`points lying in [0, δ]d. For a point pk∈ P`we saw
already in (4.8) an expression for the probability that epkhas a fixed empty orthant. We will
now further transform this integral by subdividing the domain IRdof the integral into 2d
subdomains in the following way
Pro[d](epk)is empty
≤ZIRd
ϕ(x(1))···ϕ(x(d))·(1 −Φ(x(1) −δ)···Φ(x(d)−δ))n`−1dx(1) ··· dx(d)
=
d
X
i=0 d
iZZϕ
δ,r ···ZZϕ
δ,r
| {z }
d−i
ZIR−Zϕ
δ,r ···ZIR−Zϕ
δ,r
| {z }
i
ϕ(x(1))···ϕ(x(d))·
(1 −Φ(x(1) −δ)···Φ(x(d)−δ))n`−1dx(1) ··· dx(d)
≤ Z +ZIR−Zϕ
δ,r ···ZIR−Zϕ
δ,r
ϕ(x(1))···ϕ(x(d))·
(1 −Φ(x(1) −δ)···Φ(x(d)−δ))n`−1dx(1) ··· dx(d).
The last step follows by the observation that (1 −Φ(x(1) −δ)···Φ(x(d)−δ)) ≤1.
Thus the first dsummands can be bounded by Zand it remains to treat the last summand.
Indeed, for the last summand we can expand the product of density functions as described
before in (4.9) and then bound the ratios ϕ(x)/ϕ(x−δ)by rbecause Zϕ
δ,r was defined in
this way. This gives us then for the last summand
ZIR−Zϕ
δ,r ···ZIR−Zϕ
δ,r
ϕ(x(1))···ϕ(x(d))·
(1 −Φ(x(1) −δ)···Φ(x(d)−δ))n`−1dx(1) ··· dx(d)
≤rd·ZIR−Zϕ
δ,r ···ZIR−Zϕ
δ,r
ϕ(x(1) −δ)···ϕ(x(d)−δ)·
(1 −Φ(x(1) −δ)···Φ(x(d)−δ))n`−1dx(1) ··· dx(d)
≤rd·ZIRd
ϕ(x(1))···ϕ(x(d))·(1 −Φ(x(1))···Φ(x(d)))n`−1dx(1) ··· dx(d)
=rd·1
n`
n`
X
i1=1
1
i1
i1
X
i2=1
1
i2···
id−2
X
id−1=1
1
id−1≤rd·H(n`)d−1
n`
.
40
4.2 Upper Bounds for the Smoothed Case
To see the second last step we refer to the proof of Theorem 6, the average case analysis.
It remains to conclude that
EhD(e
P`)i≤2d·(rd·H(n`)d−1+Z ·n`).
Remember that we have m=d1/δedsubsets P`. From (4.7) it follows that
EhD(e
P)i≤
m
X
`=1
EhD(e
P`)i≤2d·(rd·d1/δed·H(n`)d−1+Z ·n).
Since this result holds for all sets Pof input points from [0,1]d, Lemma 3 is proven.
B2
4.2.1 Normal Gaussian Noise
We will apply now Lemma 3 to the case that the random noise comes from the Gaussian
normal distribution with expectation 0and variance σ2, also denoted as N(0, σ). The 1-
dimensional density function of the Gaussian normal distribution is
ϕ(x) := 1
√2π·σ·e−x2
2σ2.
Theorem 8 For random noise from the standard Gaussian normal distribution N(0, σ),
the smoothed number of extreme points over all input sets Pof npoints from [0,1]dis
max
P
EhV(e
P)i≤max (26d+2 ·dd/2·1
σd
·ln(n)d/2·H(n)d−1,H(n)d−1)
=O 1
σd
·log(n)3
2·d−1+ log(n)d−1!.
Proof. In order to utilize Lemma 3 we need to choose the two parameters rand δ. Let
δ:= σ/β where β:= rln 1/d
p1+1/n −1. For x≤ −√2σβ it holds that
ϕ(x)
ϕ(x−δ)=e−δ
σ2·x+δ2
2σ2=e−x
σ·β+1
2β2≤e√2+ 1
2β2≤e3.
41
4 Extreme Points
Therefore, if we choose r:= e3, we can conclude that Zϕ
δ,r ⊂−∞,−√2σβ. With
this approximation we can take the next crucial step, namely to bound Z. It is
Z=
d−1
X
i=0 d
iZZϕ
δ,r ···ZZϕ
δ,r
| {z }
d−i
ZIR−Zϕ
δ,r ···ZIR−Zϕ
δ,r
| {z }
i
ϕ(x(1))···ϕ(x(d)) dx(1) ··· dx(d)
≤
d−1
X
i=0 d
iZ−√2σβ
−∞
. . . Z−√2σβ
−∞
| {z }
d−i
Z∞
−∞
. . . Z∞
−∞
| {z }
i
ϕ(x(1))···ϕ(x(d)) dx(1) ··· dx(d)
=
d−1
X
i=0 d
i Z−√2σβ
−∞
ϕ(x) dx!d−i
.(4.10)
From Claim 1 on page 21 it follows, that we can estimate the tail of the standard Gaus-
sian normal probability distribution N(0, σ)in the following way. It is R−kσ
−∞ ϕ(x) dx≤
e−k2/2for any k≥1/√2π. Hence we have
Z−√2σβ
−∞
ϕ(x) dx≤e−β2=d
r1 + 1
n−1.(4.11)
Combining (4.10) and (4.11) we get
Z ≤
d−1
X
i=0 d
i d
r1 + 1
n−1!d−i
= 1 + d
r1 + 1
n−1!d
−1 = 1
n.
We can now apply Lemma 3 with r=e3and Z ≤ 1/n and it follows
EhV(e
P)i≤max 2d·e3d·d1/δed·H(n)d−1+ 1,H(n)d−1.
It remains to consider δwhich was earlier chosen to be σ/β. We will exploit the follow-
ing claim.
Claim 3
d
√1 + b≥1 + b
2d∀0< b < 1
Proof of Claim 3.
1 + b
2dd
=
d
X
i=0 d
ib
2di
≤1 +
d
X
i=0 d
i·b
2d= 1 + b
B2Claim 3
42
4.2 Upper Bounds for the Smoothed Case
It follows that
β=rln 1/d
p1+1/n −1≤pln(2d·n)≤pd·ln(n),
and thus we get
d1/δe ≤ (1/σ)d·βd+ 1 ≤2·dd/2·(1/σ)d·ln(n)d/2.
Now we combine the results and conclude that for every input set Pthe expected number
of extreme points under Gaussian normal noise is at most
EhV(e
P)i≤max 26d+2 ·dd/2·(1/σ)d·ln(n)d/2·H(n)d−1,H(n)d−1,
which proves Theorem 8.
B2
4.2.2 Uniform Noise
In this section, we will now consider random noise that is uniformly distributed in a hy-
percube of side length 2centered at the origin. This distribution has for its components
the 1-dimensional density function
ϕ(x) = (1
2if x∈[−, ]
0else .
Theorem 9 For random noise from the uniform distribution from a hyper-cube of side
length 2, the smoothed number of extreme points over all input sets Pof npoints from
[0,1]dis
max
P
EhV(e
P)i≤max (2d+1 ·d·n
2d
d+1
·H(n)d−1
d+1 ,H(n)d−1)
=O n·log(n)
d
d+1
+ log(n)d−1!.
Proof. Again we want to utilize Lemma 3. We choose r= 1, then it follows that for
0< δ < 2we have Zϕ
δ,r ={x∈IR |ϕ(x)> ϕ(x−δ)}= [−, −+δ]. In the next step
43
4 Extreme Points
we need to compute Zwhich is given by
Z=
d−1
X
i=0 d
iZδ−
−
. . . Zδ−
−
| {z }
d−i
Z
δ−
. . . Z
δ−
| {z }
i
1
2d
dx(1) ··· dx(d)
=
d−1
X
i=0 d
i·1
2d
·δd−i·(2−δ)i=1
2d(2)d−(2−δ)d
= 1 −1−δ
2d
≤1−1−d·δ
2=d·δ
2.
We can now apply Lemma 3 and it follows that for every input set Pthe expected
number of extreme points under uniform noise is at most
EhV(e
P)i≤max 2d·d1/δed·H(n)d−1n+n·d·δ
2,H(n)d−1.
If we choose δ= (2·H(n)d−1/(d·n))1/(d+1) we obtain the theorem. B2
4.3 Lower Bounds for the Smoothed Case
In this section we consider lower bounds for the smoothed number of extreme and maximal
points.
For random noise from the Gaussian normal distribution we can refer to the average
case bounds which directly imply lower bounds for the smoothed case. In Theorem 6
we saw that the expected number of maximal points is Θ(log(n)d−1). Raynaud showed
that the expected number of extreme points is Θ(log(n)(d−1)/2)[Ray70]. We recall that in
Theorem 8 the smoothed number of maximal and extreme points under Gaussian normal
noise was shown to be at most O((1/σ)d·log(n)3/2·d−1+ log(n)d−1). For the smoothed
number of maximal points, the gap between this upper bound and the average case bound
is thus roughly a factor of log(n)d/2. For the smoothed number of extreme points, the gap
is roughly a factor of log(n)d.
We will now show that the smoothed number of extreme points for uniform noise from
a hyper-cube is significantly larger than for the case of normally distributed noise. We do
this by constructing an input set of points such that the set of perturbed points has a large
expected number of extreme points.
Before we start with this construction we will introduce the notion of spherical caps on
the unit sphere. Let
Ωd:= ((x1, . . . , xd)∈IRd
d
X
i=1
x2
i= 1)
44
4.3 Lower Bounds for the Smoothed Case
x
ff
Figure 4.2: Spherical cap capd(x, φ)and the corresponding region (shaded).
denote the d-dimensional Euclidean sphere of unit radius and let
Sd=d·πd/2
Γ(d/2 + 1)
be the (d−1)-dimensional content (surface area) of Ωd.
The angular separation between two points x, y ∈Ωdis the angle between the line
segment joining the origin with xand the line segment joining the origin with y. The
angular separation is thus arccos(x·y)where x·yis the inner (dot) product4of xand y.
The set of points on Ωdwhose angular separation from a fixed point x∈Ωdis at most φ
is called a spherical cap centered at xwith angular radius φand is denoted by capd(x, φ),
i.e.
capd(x, φ) := y∈Ωdx·y > cos(φ).
When the center of a spherical cap is not relevant, the notation may be abbreviated as
capd(φ). Furthermore, we will consider the convex closure of capd(φ). Let us denote
capd(x, φ) := conv(capd(x, φ))
=(d
X
i=1
λi·ziz1, . . . , zd∈capd(φ), λi≥0,
d
X
i=1
λi= 1)
as the region of spherical cap capd(x, φ), see also Figure 4.2.
An important property of spherical caps is expressed in the following observation.
4For x= (x1, . . . , xd)and y= (y1, . . . , yd)the inner dot product is defined as x·y=Pd
i=1 xi·yi.
45
4 Extreme Points
Observation 1 Consider a set Pof points lying inside the sphere Ωdand an arbitrary
x∈Ωd. If the region capd(x, φ)is non-empty it contains at least one point of Pthat is an
extreme point of conv(P).
Our plan is now the following. First we try to place a large number of non-intersecting
spherical caps on Ωd. Then we select the position of the input points in set Psuch that it
is guaranteed, that after the perturbation no point of e
Plies outside the unit sphere Ωdand
that the number of spherical caps with non-empty region is large.
So in a first step we will investigate how many spherical caps of fixed angular radius φ
can be placed on the unit sphere Ωdsuch that they are non-intersecting. This problem is
also studied in the context of spherical codes. A spherical code is a so-called channel code
(or error-correcting code) and consists of a finite set of points on Ωd. Spherical codes have
important applications to transmission over the Gaussian channel and to many other areas
[CS88]. The minimum angular separation of a spherical code C ⊂ Ωdis the minimum over
all pairwise angular separations and is denoted by sep(C), i.e.
sep(C) := min arccos(c1·c2)c1, c2∈ C ⊂ Ωd.
A desirable property of a spherical code is to have a large minimum angular separation.
The maximum number of points of a spherical code in ddimensions having a minimum
angular separation greater than or equal to γis commonly denoted by M(d, γ), i.e.
M(d, γ) := max |C| C ⊂ Ωdand sep(C)≥γ.
This is also interesting for us since a lower bound on M(d, 2φ)provides also a lower
bound on the number of non-intersecting spherical caps of angular radius φthat can be
placed on Ωd. The reason is that for any two points in capd(φ), the angular separation is
at most 2φ. In other words, we can place in each point of a spherical code of minimum
angular separation 2φthe center of a spherical cap with angular radius φsuch that all
spherical caps are non-intersecting.
We obtain a lower bound on M(d, γ)by the following simple observation. Consider
an optimal spherical code C={c1, . . . , cm} ⊂ Ωdsuch that |C| =m=M(d, γ)and
sep(C) = γ. Now we place at each point ciof the code Cthe center of a spherical cap of
angular radius γand consider their union, i.e. ∪m
i=1capd(ci, γ).
If there is now a point x∈Ωdand x /∈ ∪m
i=1capd(ci, γ), it follows immediately that
arccos(x·ci)≥γ. Thus C ∪{x}is also a spherical code of minimum angular separation
γwith m+ 1 points, a contradiction to m=M(d, γ)being the maximum. Therefore we
have Ωd=∪m
i=1capd(ci, γ)and M(d, γ)· S(capd(γ)) ≥ Sd, where S(capd(γ)) denotes
the (d−1)-dimensional content (surface area) of capd(γ).
We conclude that
M(d, γ)≥Sd
S(capd(γ)) .
46
4.3 Lower Bounds for the Smoothed Case
ci
Ri
Figure 4.3: Spherical cap capd(ci, φ)and the range cube Ri.
Lemma 4 The (d−1)-dimensional content of a spherical cap of angular radius γis
S(capd(γ)) = Sd−1·Zγ
0
sin(ϑ)d−2dϑ
=Sd−1·1
d−1·γd−1−d−2
6(d+ 1) ·γd+1 +O(γd+3).
It follows immediately that M(d, γ) = Ω(γ−(d−1)). The proof of this lemma is deferred to
the end of this section.
For a given vector φlet now `=`(φ)be the number of non-intersecting spherical caps
on Ωdand let them be centered at points c1, . . . , c`∈Ωd, i.e. the spherical caps are given
by capd(c1, φ),...,capd(c`, φ)where ci·cj>cos(2φ)for all 1≤i < j ≤`.
In the next step we will now consider the positions of the input points. Let again
P= (p1, . . . , pn)⊂IRdbe the set of input points and consider independently and identi-
cally distributed random noise vectors r1, . . . , rnchosen from the d-dimensional uniform
distribution in the hyper-cube [−, ]d. The perturbed point epk=pk+rkis then uniformly
distributed in the hyper-cube Qd
i=1[p(i)
k−, p(i)
k+]which we will denote as the range cube
for input point pk.
For every spherical cap capd(ci, φ)we try to place a bunch of at least bn/`cinput points
at exactly the same position such that one vertex of their common range cube lies in ci, for
1≤i≤`. Let Ridenote the common range cube for the points placed in such a way at
spherical cap capd(ci, φ), see also Figure 4.3.
Furthermore, if for a spherical cap capd(ci, φ)the input points can be placed such that
their common range cube Rilies completely inside Ωdit can be shown that the intersection
volume between Riand the region capd(ci, φ)is large. Therefore it will be likely that one
47
4 Extreme Points
{
b
Figure 4.4: In the 2-dimensional case, the spherical segment seg(1)
2()consists of the two
indicated parts of Ωd. What remains when they are removed from Ωdare two
spherical caps each of angular radius β= arccos().
of the points from the range cube Rilies in capd(ci, φ)after perturbation. By exploiting
Observation 1 we can then derive a lower bound on the smoothed number of extreme
points.
We call the spherical cap capd(ci, φ)valid if we can place input points as just described,
such that their common range cube Riis contained inside Ωdand a vertex of it lies in ci.
In the next lemma we will investigate the number of valid spherical caps which will be
denoted by `v(φ) = `v.
Lemma 5 Let ≤1/√2. Choose φsuch that = sin(φ). The number of valid spherical
caps of angular radius φis then
`v(φ)≥2d·S(capd(π/2−φ)) −(d−1) ·Sd
S(capd(2φ)) = Ω φ−(d−1).
Proof. A spherical cap capd(ci, φ)is non-valid if the corresponding range cube Rilies
not completely inside Ωd. We define now dspherical segments which will be denoted by
seg(1)
d(),...,seg(d)
d(), where
seg(i)
d() = x= (x1, . . . , xd)∈Ωd−≤xi≤
for 1≤i≤d, see also Figure 4.4. From Figure 4.5 it follows immediately that capd(ci, φ)
is non-valid if and only if its center ciis from one of these spherical segments since then
the corresponding range cube juts out of the unit sphere.
48
4.3 Lower Bounds for the Smoothed Case
Figure 4.5: Range cubes of valid spherical caps (filled) and of non-valid spherical caps
(non-filled).
Let us now consider a fixed spherical segment seg(i)
d(). Indeed, what remains from
the sphere Ωdwhen seg(i)
d()is removed are two spherical caps each of angular radius
β:= arccos() = π/2−φ. The (d−1)-dimensional content (surface area) of the spherical
segment seg(i)
d()is then given by Sd−2·S(capd(β))). We have now
`v(φ)≥Sd−d·(Sd−2·S(capd(β))))
S(capd(2φ))
=2d·S(capd(π/2−φ)) −(d−1) ·Sd
S(capd(2φ))
= Ω(φ−(d−1)),
where the last step follows with Lemma 4. B2
In the next lemma we consider the intersection between the region of a valid spherical
cap and the corresponding range cube.
Lemma 6 Let capd(ci, φ)be a valid spherical cap and let Ribe the corresponding range
cube of side-length 2, i.e. a vertex of Rilies in ciand Riis completely inside Ωd. The
d-dimensional volume of intersection between the region capd(ci, φ)and Riis at least
min (11
24φ2d
·d−1·p1−(d−1) ·2,(2)d).
49
4 Extreme Points
ci
i
Ri
Bi
Figure 4.6: The intersection volume between capd(ci, φ)and Ri.
Proof. Consider the line segment that joins the origin and point ciand let us denote that
part of it that lies inside the region capd(ci, φ)by δi, see Figure 4.6. If φ≤1the length of
δiis then given by
||δi||2= 1 −cos(φ)≥1−(1 −1
2φ2+1
24φ4)≥11
24φ2.
Now we need to find a lower bound on the intersection volume between capd(ci, φ)and
Ri. Therefore consider the axis-aligned box Bithat has one vertex lying in ci, is completely
contained in capd(ci, φ), and has δias the diagonal that joins the vertex at ciwith the
‘opposite’ vertex of Bi. It follows immediately that Biis also completely contained in
Ri. We will now approximate the intersection volume between capd(ci, φ)and Riby the
volume of box Bi.
Let x1, . . . , xddenote now the side-lengths of Bi. The volume of Biis then given by
vol(B) = Qd
i=1 xi. Since δiis a diagonal of Bi, it follows that
xd=q||δi||2
2−x2
1−. . . −x2
d−1.(4.12)
Since capd(ci, φ)is a valid spherical cap we know about the components of its center
ci= (c(1)
i, . . . , c(d)
i)that c(i)
i/∈[−, ]for all 1≤i≤d, where again = sin(φ). We can
conclude that xi≥·||δi||2for all 1≤i≤d. It remains to find out about the minimum
volume of box Bi, which is done with the following claim.
Claim 4 The volume of Biis minimal if d−1of the sides of Biare of length ·||δi||2.
The proof of this claim is deferred for now.
50
4.3 Lower Bounds for the Smoothed Case
Without loss of generality we can assume now that x1=··· =xd−1=·||δi||2, and it
follows by (4.12) that xd=||δi||2·p1−(d−1) ·2. The volume of box Biis then
vol(Bi) = ||δi||d
2·d−1·p1−(d−1) ·2.
Since the intersection volume between capd(ci, φ)and Rishould not drop below the
volume of Riwhich is (2)d, Lemma 6 follows immediately. B2
It remains to show that Claim 4 holds.
Proof of Claim 4. For ease of notation we abbreviate b:= ·||δi||2. Let again x1, . . . , xd
denote the side-lengths of Bi. Without loss of generality we assume that the xj’s are in
increasing order and that xkis the smallest one not equal to b, i.e. b=x1=. . . =xk−1<
xk≤xk+1 ≤. . . ≤xd. Let also c:= ||δi||2
2−x2
1−. . .−x2
k−1−x2
k+1 −. . . x2
d−1. It follows
then by (4.12) that xd=pc−x2
kand therefore
vol(Bi) = x1···xd−1·qc−x2
k.
The plan is now to decrease the side-length xkand to increase xdaccordingly such that
the diagonal has still a length of ||δi||2. Therefore, consider now the axis-aligned box b
Bi
with side-lengths y1, . . . , ydsuch that y1=. . . =yk=b, and yj=xjfor k+1 ≤j≤d−1.
Again by (4.12) it follows then that yd=√c−b2. Now we have that
vol(Bi)−vol( b
Bi) = x1···xk−1·xk+1 ···xd−1·xk·qc−x2
k−b·qc−b2>0.
The last step follows since xk> b and pc−x2
k=xd> b.B2Claim 4
In the next lemma we are ready to find out about the probability that the region of a
valid spherical cap contains at least one point and we thus have an extreme point after
perturbation for every valid spherical cap. Recall that the number of valid spherical caps
is denoted by `v(φ).
Lemma 7 For ka sufficiently large constant, if φ=k·(/n)1/(3d−1), the region of every
valid spherical cap is nonempty with probability at least 1−1/e, after perturbation.
Proof. Let `v(φ), the number of valid spherical caps, be as in Lemma 5. For every valid
spherical cap cap(ci, φ)we place a bunch of at least bn/`v(φ)c=O(n·φd−1)input points
in the described way, such that a vertex of their common range cube Rilies in ciand that
Riis completely contained inside Ωd.
From Lemma 6 it follows immediately that the probability that none of these points lies
in the region cap(ci, φ)after perturbation is
Pr[ cap(ci, φ)is empty]
≤
1−
min n11
24 φ2dd−1·p1−(d−1) ·2,(2)do
(2)d
bn/`v(φ)c
.
51
4 Extreme Points
For ka sufficiently large constant, we choose φ=k·(/n)1/(3d−1) such that
(2)d
(11
24 φ2)d·d−1·p1−(d−1) ·2≤n
`v(φ).
Lemma 7 is thus proven.
B2
By combining Lemmas 5 and 7 the next theorem follows immediately.
Theorem 10 For random noise from the uniform distribution in a d-dimensional hyper-
cube of side-length 2≤√2, the smoothed number of extreme points over all input sets P
of npoints is
max
P
EhV(e
P)i= Ω min n
d−1
3d−1, n .
It remains to prove Lemma 4.
Lemma 4 The (d−1)-dimensional content of a spherical cap of angular radius γis
S(capd(γ)) = Sd−1·Zγ
0
sin(ϑ)d−2dϑ
=Sd−1·1
d−1·γd−1−d−2
6(d+ 1) ·γd+1 +O(γd+3).
Proof. Consider the spherical cap of angular radius γcenter at e1:= (1,0,...,0) ∈Ωd
which is given by capd(e1, γ) = x∈Ωde1·x > cos(γ).
In 3-dimensional Euclidean space we can use Pappus’ Centroid Theorem [Wei] which
is also known as Guldin’s First Rule to compute the surface area of a spherical cap as
follows. The theorem gives a general formula to compute the 2-dimensional content of a
surface of revolution. Consider the curve of the integrable function f: [a, b]→IR that
does not intersect the x1-axis. This curve is called the generating curve and its length is
given by Rb
ap1 + f0(x)2dxwhere f0(x) = df(x)/dx. The content Sf(a, b)of the surface
generated by the revolution of the generating curve about the x1-axis is then given by
Sf(a, b) = Zb
aS2·f(x)p1 + f0(x)2dx= 2πZb
a
f(x)p1 + f0(x)2dx .
Note that S2·f(x) = 2π·f(x)denotes the 1-dimensional content of a 2-dimensional
sphere of radius f(x).
In our case, the generating function is that of a semi-circle, namely f(x) = √1−x2
and f0(x) = −x/√1−x2, and a= cos(γ)and b= 1, so we get that
cap3(γ)=2πZ1
cos(γ)
1 dx= 2π·(1 −cos(γ)) .
52
4.3 Lower Bounds for the Smoothed Case
abx1
f x
( )
x
x3
2
Figure 4.7: Generating curve of function f(x)revolves around the x1-axis.
The Guldin-Pappus’ Theorem has been extended to higher dimensions [Kur53]. Con-
sider a (d−1)-dimensional surface whose intersection with a hyperplane perpendicular to
the x1-axis is a (d−1)-dimensional hypersphere of radius f(x), where f: [a, b]→IR is
an integrable function that does not intersect the x1-axis. The (d−1)-dimensional content
Sf(a, b)of this surface is then given by
Sf(a, b) = Zb
aSd−1·f(x)d−2p1 + f0(x)2dx .
Note that Sd−1·f(x)d−2denotes the (d−2)-dimensional content of a (d−1)-dimensional
sphere of radius f(x).
To compute the (d−1)-dimensional content of the surface of capd(e1, γ)we use again
that f(x) = √1−x2and f0(x) = −x/√1−x2, and a= cos(γ)and b= 1, so we get that
S(capd(γ)) = Sd−1·Z1
cos(γ)
√1−x2d−2·r1 + x2
1−x2dx
=Sd−1·Z1
cos(γ)
√1−x2d−3dx .
By a linear substitution x= cos(ϑ),dx=−sin(ϑ) dϑand by the series expansion of
53
4 Extreme Points
sin(ϑ)we get that
S(capd(γ)) = Sd−1·Zγ
0
sin(ϑ)d−2dϑ
=Sd−1·Zγ
0 ∞
X
i=0
(−1)iϑ2i+1
(2i+ 1)!!d−2
dϑ
=Sd−1·Zγ
0
ϑd−2−d−2
6·ϑd+O(ϑd+2) dϑ
=Sd−1·1
d−1·γd−1−d−2
6(d+ 1) ·γd+1 +O(γd+3),
which concludes the proof of Lemma 4.
B2
4.4 Conclusion
The following table gives an overview on the results of this chapter. Depicted are upper
and lower bounds for the smoothed number of extreme/maximal points for noise from
the Gaussian normal distribution and the uniform distribution. The bounds are given in
O-notation, the dimension dis considered as a constant.
Upper Bounds Lower Bounds
Ωlog(n)(d−1)/2(?)
Gaussian N(0, σ)O(1/σ)d·log(n)3
2·d−1+ log(n)d−1Ωlog(n)d−1(??)
uniform in [−, ]dO(n·log(n)/)d
d+1 + log(n)d−1Ωmin{(n/)d−1
3d−1, n}
The lower smoothed case bounds for random noise from the Gaussian normal distri-
bution are obtained from the average case bounds on the number of extreme points (?)
[Ray70] and on the number of maximal points (??), see also Theorem 6.
We observe that for Gaussian normal noise the lower and upper smoothed bounds leave
a gap of roughly log(n)d/2for the number of maximal points and roughly log(n)dfor the
number of extreme points. The gap for the uniform noise is much smaller, the bounds
differ only by a factor of roughly log(n)d/(d+1). This might be due to the fact that for
Gaussian normal noise we do not have an explicit lower bound constructions and rely on
the average case bounds.
However, we observe analogously to the results of the previous chapter, that there is
a significant difference between the behavior under Gaussian normal noise and uniform
noise.
54
4.4 Conclusion
From the upper bound results we observe again that our analysis method cannot be ap-
plied for Gaussian normal noise of arbitrary deviation. For σ≤ O(plog(n)) we obtain the
average case bound of O(log(n)d−1). If σ≥Ω(log(n)3/2−1/d/n1/d)we obtain O(n)many
extreme points which means that our analysis cannot distinguish between the perturbed
and unperturbed case. For uniform noise we observe the same. Here the upper bound are
meaningless if ≤ O(n/ log(n)d−1−1/d)or ≥Ω(log(n)/n1/d).
55
4 Extreme Points
56
5 Bounding Box of a Moving Point Set
The goal of this chapter is to present an interesting application of smoothed analysis in the
area of analysing motion and the complexity of motion. When talking about motion, we
consider a non-static scenario in IRdwhere given (input) points move. The movement of
each point is predictable for some time in the future. The motivation to consider motion
comes from the fact that many applications are based on algorithms dealing with moving
objects. There has been diverse research on moving objects and the question how to deal
with motion computationally and algorithmically.
This chapter gives a brief introduction into this area of research where we focus on a
complexity measure for movement of objects, the motion complexity. We then introduce
smoothed motion complexity which is an extension of motion complexity that is based, as
the name points out, on smoothed analysis. The motivation for using smoothed analysis
in this context comes from the observation that in applications usually the data about po-
sitions of moving objects are inherently noisy due to measurement errors. Again we will
model this measurement error by Gaussian normal noise.
To illustrate the concept of motion complexity and smoothed motion complexity, we
consider as an example the problem to maintain a smallest orthogonal bounding box of a
moving point set under linear motion.
Outline. In Section 5.1, a brief introduction into the area of analysing motion with a fo-
cus on kinetic data structures is given. We introduce also motion complexity and smoothed
motion complexity.
In Section 5.2, the concept of motion complexity is illustrated by an example. We
consider the problem to maintain the smallest orthogonal bounding of a linearly moving
point set in IRd. We show that the motion complexity of the bounding box is closely related
to the number of extreme points of a set of points. Thus we obtain bounds on the motion
complexity of the bounding box applying the bounds on the number of extreme points
from the previous Chapter 4. At the end of this section, we see how the upper bounds on
the smoothed motion complexity can be improved. This is done by applying results from
Chapter 3 on the number of left-to-right maxima.
The last Section 5.3 briefly summarizes this chapter and gives some conclusions.
57
5 Bounding Box of a Moving Point Set
5.1 Analysing Motion
The task to process a set of continuously moving objects arises in a broad variety of ap-
plications, e.g. in mobile ad-hoc networks, traffic control systems, and computer graphics
(rendering moving objects). Therefore, researchers investigated data structures for certain
attributes of moving point sets that can be efficiently maintained under continuous motion,
e.g. to answer proximity queries [BGZ97], maintain a clustering [Har04], a convex hull
[BGH99], or some connectivity information of the moving point set [HS01].
5.1.1 Kinetic Data Structures
Basch et al. [BGH99] introduce kinetic data structures which as a framework for data
structures for moving objects. In kinetic data structures, the (near) future motion of all
objects is known and can be specified by so-called pseudo-algebraic functions of time, i.e.
linear functions or low-degree polynomials. This specification is called a flight plan. The
flight plan may change from time to time and these updates are reported to the kinetic data
structure. The goal is to maintain the description of a combinatorial structure as the objects
move according to the flight plan.
For a kinetic data structure, the number of combinatorial changes in the description of
the maintained attribute that occur during linear (or low degree algebraic) motion are called
external events. Events that are processed by the data structure because of internal needs
are called internal events.
The efficiency of a kinetic data structures is then analyzed by comparing the worst case
number of internal events and external events it processes against the worst case number
of external events. Using this framework many interesting and efficient kinetic data struc-
tures have been developed, e.g. for connectivity of discs [GHSZ01] and rectangles [HS01],
convex hulls [BGH99], proximity problems [BGZ97], and collision detection for simple
polygons [KSS02].
Basch et al. [BGH99] develop also a kinetic data structure to maintain a bounding box of
a moving point set in IRd. The number of events these data structures process is O(nlog n)
which is close to the worst case motion complexity of Θ(n), as we will see later. Agarwal
and Har-Peled [AH01] show that it is possible to maintain an (1+)-approximation of such
a bounding box efficiently. The advantage of this approach is that the motion complexity
of this approximation is only O(1/√).
5.1.2 Motion Complexity
We will use now the concept of external events in order to introduce motion complexity as a
complexity measure for motion. Thus, motion complexity is already implicitly contained
in the framework of kinetic data structures. We consider here moving point sets in IRd
under linear motion that are defined as follows.
58
5.2 Motion Complexity of the Bounding Box
Definition 7 (Moving Point Set) Given is a set Pof npoints in IRd. We call Palinearly
moving point set or a points set under linear motion if the following holds.
The position posi(t)of the ith point of Pat time tis given by a linear function of t. Thus
we have posi(t) = pi+si·twhere piis the initial position and sithe speed vector of the
ith point.
For linearly moving point sets we consider certain geometric structures such as the con-
vex hull or the Voronoi diagram of the point sets. The worst case number of external events
with respect to the maintainance of such a structure over time is denoted as the worst case
motion complexity. Analogously, we denote the average case number of external events as
the average case motion complexity of that structure.
The worst case motion complexity is the maximum number of external events over all
choices of speed values and initial positions. The average motion complexity is the ex-
pected number of external events, where all speed values and initial positions are indepen-
dent and identically distributed random vectors chosen from a fixed probability distribu-
tion.
The average case motion complexity has already been considered in the past. If nparti-
cles are drawn independently from the unit square then it has been shown that the expected
number of combinatorial changes to the description of the convex hull is Θ(log(n)2)and
of the Voronoi diagram Θ(n3/2), and to the closest pair problem Θ(n)[ZDBI97].
5.1.3 Smoothed Motion Complexity
Many applications are based on algorithms dealing with moving objects, but usually data
about positions of moving objects are inherently noisy due to measurement errors. There-
fore we introduce smoothed motion complexity that considers this imprecise information
and uses smoothed analysis to model noisy data.
In the context of mobile data this means that both the speed vector and the starting posi-
tion of an input point are slightly perturbed by random noise from a fixed noise distribution.
The smoothed motion complexity is then the worst case expected motion complexity over
all input instances perturbed in such a way. The speed vectors and initial positions are
normalized such that pi, si∈[−1,1]d.
5.2 Motion Complexity of the Bounding Box
To illustrate the concept of motion complexity and smoothed motion complexity we con-
sider the problem of maintaining a bounding box of a moving point set under linear motion.
This problem is formally described in the following definition.
Definition 8 (Bounding Box) Given is a set Pof nlinearly moving points in IRd.
At a particular point of time t0, the bounding box of set Pwith given initial positions
p1, . . . , pnand speed vectors s1, . . . , snis then the smallest orthogonal box containing
59
5 Bounding Box of a Moving Point Set
all points of P. At any time the bounding box is uniquely defined and combinatorially
described by at most 2dbounding points, i.e. the points that attain the maximum and
minimum value in each of the ddimensions.
For example, in the one dimensional case, the bounding box problem can be interpreted
as a race where all participants (drivers) have slightly different starting positions. (Without
loss of generality, we assume that all drivers have the same direction.) The radio reporter
has to tell the audience each time when the leading position changes, i.e. another driver
becomes the leader. At a particular point of time, no further changes will occur, namely
when the fastest driver has become the leader. The number of times that the radio reporter
announces a change in the leading position is the number we are interested in.
More generally, for a set Pof linearly moving points, if the combinatorial description
of the bounding box of Pchanges, i.e. any bounding point of Pchanges, then an external
event occurs. The motion complexity of the bounding box is thus the number of combi-
natorial changes over time to the set of at most 2dbounding points defining the bounding
box.
Clearly the worst case motion complexity of the bounding box is at most 2d·n= Θ(n).
In the best case, the motion complexity of the bounding box is 0, while the average case
motion complexity is O(log(n)), as we will see later.
When we consider the smoothed motion complexity of the bounding box we add to
each coordinate of the speed vector and each coordinate of the initial position of every
input point an i.i.d. random vector from a fixed probability distribution over IRd, e.g. the
d-dimensional Gaussian normal distribution. The smoothed motion complexity is then
the worst case expected motion complexity over all choices of speed vectors and initial
positions.
In the following we will see, that the 1-dimensional bounding box problem for linearly
moving point sets is dual to the 2-dimensional convex hull of a point set. The results from
the previous chapter carry thus immediately over to the bounding box problem.
5.2.1 Duality between Bounding Box and Convex Hull
We make the following simplifications. We will consider only the 1-dimensional prob-
lem, i.e. all points move along a line such that their ordering changes only when they
overtake each other. Since all dimensions are independent from each other, a bound for
the 1-dimensional problem can be multiplied by dto yield a bound for the problem in d
dimensions.
We map now each point with initial position piand speed value sito a point Pi=
(si,−pi)in IR2. Then we can utilize that the number of combinatorial changes to the
description of the 1-dimensional bounding box is equal to the number of extreme points of
the convex hull of the Pi’s. This relation is easily seen by the following considerations.
In a first step we consider the following scenario. For all 1≤i≤n, we consider for
the ith point with initial position piand speed value sithe function posi(t) = pi+si·t
60
5.2 Motion Complexity of the Bounding Box
4
1
2
3
3
2
P
1
P
4
P
P
2
3
4
5
1
1/2 21 3/2
1 2
−1
−2
−3
−4
−5
pos ( ) = 1 + 2tt
tpos ( ) = 4 + 1/2 t
pos ( ) = 2 + t
pos ( ) = 3 − 2t t
t
−2 −1
Figure 5.1: The upper and lower envelope of a line arrangement and the corresponding
dual set of points with the upper and lower convex hull are depicted.
which gives us the position of the ith point at any point of time. Considering the graphs
of the position functions of all points in the set P, we obtain a line arrangement which
we will denote as `(P). The upper and lower envelope of the line arrangement `(P)is
the boundary of the top and bottom cell of `(P), which is a chain of edges defined as
the maximum and minimum of the linear functions whose graphs are the lines in `(P),
respectively. We observe now the following.
The edges of the upper envelope of `(P)give us exactly the points that are rightmost and
thus the boundary points on the right side of the bounding box over time. By symmetry,
this holds also for the lower envelope of `(P), which gives us the points that are leftmost,
i.e. the boundary points on the left side of the bounding box. So by the number of edges
on the upper and lower envelope of `(P)we obtain immediately the number of different
bounding points for ‘both’ boundaries and thus the motion complexity of the bounding
box of P.
In a second step we will consider the following simple duality transform [dvOS00]. For
each line `:y:= b+m·xin IR2we consider the point `?= (m, −b)in IR2called its
dual. The dual of a point p= (px, py)is then the line p?:y:= −py+px·x. We observe
that this duality transform preserves ordering, i.e. a point plies above a line `if and only
if the point `?lies above line p?.
From this observation it follows immediately that the line to function posi(t) = pi+si·t
belongs to the lower envelope of `(P)if and only if its dual, the point Pi= (si,−pi)is a
vertex of the upper convex hull of P1, . . . , Pnwhich consists of the convex hull edges that
have all remaining points below their supporing line. Of course, the same holds for the
lower envelope, the point Piis then a vertex of the lower convex hull, see also Figure 5.1.
61
5 Bounding Box of a Moving Point Set
By this method it follows immediately that the number of extreme points in 2dimen-
sions is equal to the number of edges of the lower and upper envelope of the dual line
arrangement and thus equal to the motion complexity of the bounding box in 1dimension.
The bounds on the average and smoothed number of extreme points in 2dimensions from
Chapter 4 carry thus over to the bounding box problem.
5.2.2 Average Motion Complexity of the Bounding Box
The result of Renyi and Sulanke [RS63] on the average number of extreme points of the
convex hull when points are independent and identically distributed random vectors chosen
from the 2-dimensional Gaussian normal distribution implies the following theorem.
Corollary 2 The average motion complexity of the bounding box of a set of nlinearly
moving points in d-dimensional space, where initial positions and speed vectors are inde-
pendent and identically distributed random vectors chosen from the d-dimensional Gaus-
sian normal distribution, is
Oplog(n).
Another bound on the average motion complexity of the bounding box follows from the
2-dimensional version of Theorem 7 for all continuous probability distributions.
Corollary 3 The average motion complexity of the bounding box of a set of nlinearly
moving points in d-dimensional space, where initial positions and speed vectors are inde-
pendent and identically distributed random vectors chosen from a d-dimensional continu-
ous probability distribution, is
O(log(n)) .
5.2.3 Upper Bounds on the Smoothed Motion Complexity
From the 2-dimensional version of Theorem 8 which upper bounds the smoothed number
of extreme points under Gaussian normal noise we get an upper bound on the smoothed
motion complexity of the bounding box under Gaussian normal noise.
Corollary 4 The smoothed motion complexity of the bounding box over all sets of nlin-
early moving points in d-dimensional space, with initial positions and speed vectors from
[−1,1]dperturbed by random noise from the Gaussian normal distribution of deviation σ,
is
O 1
σ2
·log(n)2+ log(n)!.
By Theorem 9, the smoothed number of extreme points under uniform noise is covered.
This gives us the following corollary.
62
5.2 Motion Complexity of the Bounding Box
Corollary 5 The smoothed motion complexity of the bounding box over all sets of nlin-
early moving points in d-dimensional space, with initial positions and speed vectors from
[−1,1]dperturbed by random noise from the uniform distribution in a hypercube of side
length 2, is
O n·log(n)
2/3
+ log(n)!.
5.2.4 Lower Bounds on the Smoothed Motion Complexity
Also the lower bounds on the smoothed number of extreme points carry over to the motion
complexity of the bounding box. By the average case bound of Renyi and Sulanke [RS63]
we get the following lower bound on the smoothed motion complexity under Gaussian
normal noise.
Corollary 6 The smoothed motion complexity of the bounding box problem over all sets
of nlinearly moving points in d-dimensional space, with initial positions and speed vec-
tors from [−1,1]dperturbed by random noise from the Gaussian normal distribution of
deviation σ, is
Ωplog(n).
From the 2-dimensional version of Theorem 10 follows the next corollary.
Corollary 7 The smoothed motion complexity of the bounding box problem over all sets of
nlinearly moving points in d-dimensional space, with initial positions and speed vectors
from [−1,1]dperturbed by random noise from the uniform probability distribution in a
hypercube of side length 2, is
Ωmin 5
rn
2, n .
5.2.5 Improved Upper Bounds on the Smoothed Motion
Complexity
In this subsection we show how the upper bounds on the smoothed motion complexity can
easily be improved by a simple consideration. Again we consider only the 1-dimensional
problem and exploit that the problem is dimension-wise independent. Results hold thus
also for the d-dimensional case.
We observe that adding a constant to all initial positions and speed values, or multiplying
these values by a constant does not change the motion complexity of the bounding box.
Thus we assume that the points are ordered by their increasing initial positions and that
they are all moving to the left with absolute speed values between 0and 1. We count
63
5 Bounding Box of a Moving Point Set
thus only events that occur because the leftmost point of the 1-dimensional bounding box
changes.
A necessary condition for the jth point to cause an external event is that all its “pre-
ceding” points have smaller absolute speed values, i.e. that si< sj, for all i < j. If this
is the case, then sjis clearly a left-to-right maximum as seen in Chapter 3. Since we are
interested in upper bounds we can neglect the initial positions of the points and need only
to focus on the sequence of absolute speed values (s1, . . . , sn)and count the left-to-right
maxima in this sequence.
It follows immediately that the results on the number of left-to-right maxima carry over
to the bounding box problem. Theorem 2 in Chapter 3 implies thus directly the following
corollary.
Corollary 8 The smoothed motion complexity of the bounding box problem over all sets
of nlinearly moving points in d-dimensional space, with initial positions in IRdand speed
vectors from [−1,1]dperturbed by random noise from the Gaussian normal distribution of
deviation σ, is
O1
σ·log(n)3/2+ log(n).
We can also use Theorem 4 for unimodal noise distributions immediately. Recall, that a
random noise distribution is unimodal if the corresponding density function is monotoni-
cally increasing on IR≤0and monotonically decreasing on IR≥0.
Corollary 9 The smoothed motion complexity of the bounding box problem over all sets
of nlinearly moving points in d-dimensional space, with initial positions in IRdand speed
vectors from [−1,1]dperturbed by random noise from a continuous unimodal probability
distribution with 1-dimensional density function ϕ, is
Opn·log(n)·ϕ(0) + log(n).
These improved bounds on the smoothed motion complexity of the bounding box imply
something else. The bounds on the smoothed number of extreme points as derived in
Chapter 4 are not exactly tight, at least for the 2-dimensional case.
5.3 Conclusion
In this chapter an introduction to the analysis of motion was given. We introduced motion
complexity and smoothed motion complexity as a measure for the complexity of maintain-
ing combinatorial structures of moving data, i.e. points.
We saw that for the problem of maintaining the bounding box of a set of linearly moving
points, the smoothed motion complexity differs significantly from the worst case motion
complexity. This makes it unlikely that the worst case is attained in typical applications.
64
5.3 Conclusion
Therefore it seems promising to reconsider the use of worst case analysis for algorithms
dealing with moving objects. Especially in the development of kinetic data structures this
might lead to interesting new results.
65
5 Bounding Box of a Moving Point Set
66
6 Voronoi Diagram and Delaunay
Triangulation
The Voronoi diagram together with its dual structure the Delaunay triangulation are two
very important and fundamental structures in computer science. Especially in computa-
tional geometry they constitute a central topic in research [Aur91, For97] with many ap-
plications. Both structures are also well known and widely used in several other fields of
(natural) science. Besides mathematics and computer science, Voronoi diagrams and De-
launay triangulations can be found in physics, geology, agriculture, geography, and many
other disciplines.
Voronoi diagrams have the great advantage to be a rather simple but quite elegant struc-
ture. There are also many extensions of the basic Voronoi diagrams which are obtained by
varying metric, sites, environment, and constraints. In computer science they are widely
used in clustering, mesh generation, graphics, curve and surface reconstruction, and other
applications [OBS92].
Voronoi diagrams are named after the Russian mathematician Voronoi [Vor08] who gen-
eralized an original idea of Gauss [Gau40] to higher dimensions. Gauss’ work was mo-
tivated by the study of quadratic forms and was also exploited and further developed by
Dirichlet [Dir50]. Voronoi diagrams have been ‘reinvented’ by other researchers, e.g. by
the physicists Wigner and Seits [WS33], the meteorologist Thiessen [Thi11] and the bi-
ologist Blum [Blu73]. In these fields of science, the Voronoi diagram is thus known by
other names such as Wigner-Seitz diagram, Thiessen diagram, and Blum transform. In
mathematics the Voronoi diagram is usually also known as Dirichlet tessellation.
Definition 9 (Voronoi diagram) Given is a set Pof npoints – also called sites – in IRd.
The Voronoi cell of a site pconsists of all points that are strictly closer to pthan to any
other site in P −{p}.
The Voronoi face of a nonempty subset Tof Pconsists of all points that are equidistant
to all sites of Tand closer to any site of Tthan to any other site in P −T .
The Voronoi diagram of P– denoted VD(P)– is the collection of all nonempty Voronoi
faces and forms a cell complex partitioning IRd.
The Voronoi cell of a site pis always a nonempty, open, convex, full-dimensional subset
of IRd. The one-dimensional and two-dimensional Voronoi faces are also called Voronoi
vertices and Voronoi edges, respectively.
In his work, Voronoi [Vor08] introduced also the Delaunay triangulation for sites that
form a lattice. Later Delaunay [Del34] extended this definition to irregularly placed sites
67
6 Voronoi Diagram and Delaunay Triangulation
Figure 6.1: The Voronoi diagram and Delaunay triangulation of a set of points in IR2.
and the structure was then named after him.
Definition 10 (Delaunay triangulation) Given is a set Pof npoints – also called sites –
in IRd.
Let Tbe a subset of Psuch that a sphere through all the sites of Tis empty, i.e. all other
sites in P −T are lying exterior of this sphere. The Delaunay face of Tis the (relative)
interior of the convex hull of T.
The Delaunay triangulation of P– denoted DT(P)– is the collection of all Delaunay
faces and forms a cell complex partitioning the convex hull of P.
Throughout this chapter we assume that the set Pis in general position, i.e. no d+2 sites
lie on a common d-sphere and no k+ 2 sites lie on a common k-flat, for k < d. It follows
that the Delaunay triangulation of Pis a simplicial cell complex, i.e. all d-dimensional
Delaunay faces are simplices. Therefore we will consider from now on only Delaunay
simplices.
Duality. From Figure 6.1 we see that there is an obvious one-to-one correspondence
between the Voronoi diagram and the Delaunay triangulation of a set P. By mapping the
Voronoi face of a set T ⊆ P to the corresponding Delaunay face of Twe obtain a duality
between cell complexes that reverses face ordering. The dimensions of the Voronoi and
Delaunay face of a particular set T ⊆ P sum up to the dimension d.
Relation to Convexity. There is a close connection between Delaunay triangulations
in IRdand convex hulls in IRd+1, and between Voronoi diagrams in IRdand half-space
intersections in IRd+1. Brown [Bro79, Bro80] was the first to give a transform that relates
the dual of Voronoi diagrams (i.e. Delaunay triangulations) in IR2to convex hulls in IR3via
a stereographical projection that maps the sites into points lying on a 3-sphere. Brown’s
result and further extensions to higher dimensions, enabled the complete analysis of the
68
6.1 Average Case Analysis
combinatorial complexity of Voronoi diagrams and Delaunay triangulations [Kle80, Sei87]
in arbitrary dimensions since known results on the size of polytopes carry over.
Related Work. The Voronoi diagram can be computed in linear time from the Delaunay
triangulation, using the one-to-one correspondence between their faces. A vast variety of
basic and (relatively) simple algorithms exists for the construction of Delaunay diagrams
such as the plane sweep [For87] and the divide-and-conquer [Sha78] algorithm in IR2, and
the (randomized) incremental [GKS92, Cha91], and the gift-wrapping [CK70] algorithm
in arbitrary dimensions.
In fact, most of these algorithms are actually specialized convex hull algorithms (except
the plane sweep algorithm) due to the close relation to convexity. Any (d+1)-dimensional
convex hull algorithm can be used to compute a d-dimensional Delaunay triangulation.
All these algorithms depend in their run time on the number of faces of the Delaunay
triangulation. Unfortunately, in ddimensions this number is Θ(ndd/2e)in the worst case
[Kle80, Sei87] (for the ‘general’ diagram with the Euclidean metric).
Recent research attempts to quantify situations when the complexity (= number of faces)
of the Voronoi diagram and Delaunay triangulation is low or when it is high [Eri01]. For
sets Pin general position, the number of all faces of either structure is asymptotically equal
to the number of Delaunay simplices or Voronoi vertices, respectively. In this chapter we
will thus concentrate on these two.
Average Case Complexity. The average case complexity was considered by Dwyer
[Dwy91] who showed that for nindependent and identically distributed random point sites
chosen uniformly from the unit d-ball the expected number of Delaunay simplices is Θ(n).
It has been conjectured that this bound also holds for any uniform distribution in a convex
domain but until now no proofs were given [Dwy91, GN03].
In this chapter we consider the case that the point sites are chosen uniformly from inside
an axis-aligned hypercube. Our contribution is the first published proof that shows that
the expected complexity of Voronoi diagram and Delaunay triangulation is then linear.
The proof is based on a rather technical lemma (Section 6.2) that bounds the intersection
volume between the unit hypercube and a randomly chosen ball. How this lemma helps to
bound the expected number of Delaunay simplices is shown in the following section.
6.1 Average Case Analysis
In this section we will consider the case that Pis a set of nindependent and identically
distributed random points chosen uniformly from inside the unit d-hypercube [0,1]d. We
will derive a bound on the expected number of Delaunay simplices in DT (P)by exploiting
the following observation. Any simplex that is the convex hull of d+ 1 sites from Pis a
Delaunay simplex if and only if its circumball is empty, i.e. contains no other site from P.
69
6 Voronoi Diagram and Delaunay Triangulation
Figure 6.2: For a triangle ∆in [0,1]2,circumball(∆) ∩[0,1]2is depicted.
We will now consider all subsets of Pwith d+1 elements and without loss of generality
we assume some ordering among these subsets. For all 1≤i≤n
d+1, let Xibe a random
{0,1}variable such that Xi= 1 if and only if the ith subset of Phas the following
property: the convex hull of the ith subset is a Delaunay simplex, i.e. no other point is
contained inside this simplex.
Generally, we can then use that
E[number of Delaunay simplices in DT(P)] = E"X
i
Xi#
=X
i
Pr[Xi= 1 ] = n
d+ 1·Pr[ circumball(∆) is empty],
where ∆is the convex hull of d+ 1 independent and identically distributed random points
chosen uniformly from [0,1]d. By circumball(∆) we denote the circumball of ∆which is
the smallest d-dimensional ball enclosing ∆.
Let vol(circumball(∆)) denote the d-dimensional volume (content) of circumball(∆).
Unfortunately, in general it is
Pr[ circumball(∆) is empty]6=1−vol(circumball(∆))n−(d+1)
for the following reason. All random point sites are chosen from inside [0,1]d, but some
part of circumball(∆) might lie outside of [0,1]d. Of course, the probability for a random
point site to be in a part of circumball(∆) that is not in [0,1]dis equal to 0and therefore
we must not consider these ‘outer’ parts of circumball(∆). Therefore we have to bound
the volume of circumball(∆) ∩[0,1]d, which causes the main difficulty in our analysis,
see also Figure 6.2.
Fortunately, we can show the following lemma that is crucial for the further analysis.
The rather technical proof of this lemma is deferred to Section 6.2.
70
6.1 Average Case Analysis
Lemma 8 Let ∆be a random d-simplex, i.e. ∆is the convex hull of d+ 1 independent
and identically distributed random points chosen uniformly from [0,1]d. For any constant
a∈[0,1] it holds that
Prvol(circumball(∆) ∩[0,1]d)≤a≤constd·ad,
where
constd=d3d+1 ·2d·max 22d·Γ(1 + d/2)
πd/2, d!d
≤(c·d)d2,
for csome constant factor. Here Γdenotes the Gamma-function where Γ(1/2) = √π, and
for all x∈IN it is Γ(x+ 1) = x!and Γ(x+ 1/2) = (2x)! ·√π/(x!·22x).
Based on this lemma we will now establish the main theorem of this section.
Theorem 11 For nindependent and identically distributed random points chosen uni-
formly from [0,1]dit is
E[number of Delaunay simplices]≤n·constd·(d+ 4) ·2(d+4)·d+ 2=O(n)
where constd≤(c·d)d2is the same constant as in Lemma 8.
Proof. The main idea of this proof is to consider in a first step (classes of) simplices with
a ‘large’ circumball. Then it is more likely that another point site lies in the circumball of
these simplices and that they are therefore not Delaunay simplices. In a second step we
show that the remaining simplices with a ‘small’ circumball are only very few.
Without loss of generality we assume that nis a power of 2. Let us now consider the
n
d+1possible simplices that have d+ 1 of the given nrandom point sites as vertices.
For the simplices with ‘large’ circumball we define classes C0,...,Clog(n)−1such that for a
simplex ∆it holds that
∆∈ Ci⇐⇒ 1
2i+1 <vol(circumball(∆) ∩[0,1]d)≤1
2i.
From Lemma 8 it follows immediately that
Pr[ ∆ ∈ Ci]≤Prvol(circumball(∆) ∩[0,1]d)≤1
2i≤constd·1
2id
.
The probability for a simplex ∆∈ Cito be a Delaunay simplex is
Prcircumball(∆) is empty ∆∈ Ci≤1−1
2i+1 n−(d+1)
≤1
en−(d+1)
2i+1
≤1
2n−(d+1)
2i+1
.
71
6 Voronoi Diagram and Delaunay Triangulation
Now we can bound the expected number of Delaunay simplices for each class Ci. For
0≤i≤log(n)−1we get that
E[number of Delaunay simplices ∈ Ci]
≤n
d+ 1·Pr[ ∆ ∈ Ci]·Prcircumball(∆) is empty ∆∈ Ci
≤n
d+ 1·constd·1
2id
·1
2n−(d+1)
2i+1
.
The expected number of Delaunay simplices for all classes C0,...,Clog(n)−1is then
log(n)−1
X
i=0
E[number of Delaunay simplices ∈ Ci]
≤n
d+ 1·constd
log(n)−1
X
i=0 1
2i·d+n−(d+1)
2i+1
=n
d+ 1·constd
log(n)−1
X
i=0 1
2(log(n)−(i+1))·d+n−(d+1)
2log(n)−(i+1)+1
=n
d+ 1·constd
log(n)−1
X
i=0 1
2log(n)·d+2i·n−(d+1)
n−(i+1)·d
=n
d+ 1·constd·1
nd
log(n)−1
X
i=0 1
22i·(1−d+1
n)−(i+1)·d
≤n·constd·((d+ 4) ·2(d+4)·d+ 1) .(6.1)
The last step follows immediately if d+ 3 ≥log(n)−1since
d+3
X
i=0 1
22i·(1−d+1
n)−(i+1)·d
≤
d+3
X
i=0
2(i+1)·d≤(d+ 4) ·2(d+4)·d.
In the case that d+ 3 <log(n)−1we can bound the rest of the sum as follows
log(n)−1
X
i=d+4 1
22i·(1−d+1
n)−(i+1)·d
≤
log(n)−1
X
i=d+4 1
2i
≤1.
Here we exploit that n≥2·(d+ 1) and i≥d+ 4, since then it holds for all dthat
2i·1−d+ 1
n−(i+ 1) ·d≥2i−1−(i+ 1) ·d≥i .
72
6.2 Proof of Lemma 8
The expected number of remaining simplices with ‘small’ circumball can be bounded
using Lemma 8, too. Let Cre denote the set of simplices such that for a simplex ∆it holds
that
∆∈ Cre ⇐⇒ vol(circumball(∆) ∩[0,1]d)≤1
n.
The expected cardinality of Cre is then
E[number of simplices ∈ Cre]≤n
d+ 1·Prvol(circumball(∆) ∩[0,1]d)≤1
n
≤nd+1 ·constd·1
nd=n·constd.(6.2)
Since there are so few simplices with small circumball in expectation we do not need to
find out how many of these are possibly Delaunay simplices, and we can rather count them
all.
Now we can combine the results (6.1) and (6.2) and by linearity of expectation it follows
that
E[number of Delaunay cells]≤
log(n)−1
X
i=0
E[number of Delaunay simplices ∈ Ci]
+E[number of simplices ∈ Cre]
≤n·constd·(d+ 4) ·2(d+4)·d+ 2,
which concludes the proof of Theorem 11. B2
6.2 Proof of Lemma 8
Let p1, . . . , pd+1 ∈[0,1]dbe d+ 1 independent and identically distributed random points
chosen uniformly from the d-dimensional unit hypercube. Let ∆ = ∆(p1, . . . , pd+1)be
the convex hull of the random points p1, . . . , pd+1. For abbreviation we denote ∆also as
the random simplex.
The volume of circumball(∆) is given by Vd·rdwhere r=r(∆) is the radius of
circumball(∆) and Vd=πd/2/Γ(1+d/2) is the volume of the unit d-ball. We can approx-
imate the radius r(∆) and thus the volume of circumball(∆) by the following observation.
Observation 2 With the just made definitions it holds that
2·r(∆) ≥max
1≤i<j≤d+1 kpi−pjk2
≥max
1≤i<j≤d+1 kpi−pjk∞=: maxwidth(∆) ,
73
6 Voronoi Diagram and Delaunay Triangulation
and therefore it is
vol(circumball(∆)) ≥1
2d·Vd·maxwidth(∆)d.
The term maxwidth(∆)dcan also be interpreted as the volume of a smallest hypercube
that contains all the points p1, . . . , pd+1. The smallest hypercube is of course not uniquely
defined but we know that its side-length is exactly maxwidth(∆) by definition. In other
words, we approximate the volume of circumball(∆) by the volume of a smallest hyper-
cube containing all the vertices of simplex ∆.
It is convenient to reformulate the random process under which this average case analy-
sis is carried out in the following way. Instead of considering d+ 1 many d-dimensional
random variables (= random point sites) we combine the elements of the random variables
coordinate-wise, which leads to dsets of d+ 1 random numbers each.
Formally speaking, let us consider the random point sites p1, . . . , pd+1 ∈[0,1]dwhere
pi= (p(1)
i, . . . , p(d)
i)for 1≤i≤d+ 1. Let then P1,...,Pdbe the sets such that Pj=
{p(j)
1, . . . , p(j)
d+1}for 1≤j≤d. Note that both random processes are equivalent.
Furthermore, let
width(Pj) := max Pj−min Pj
denote the maximal distance between two elements in Pj. With the just made definition
we can now redefine the variable maxwidth in the following way as
maxwidth(P1,...,Pd) := max
1≤j≤dwidth(Pj),
which is consistent with the earlier definition. Indeed, for a set of point sites p1, . . . , pd+1 it
is maxwidth(∆) = maxwidth(P1,...,Pd)where ∆is the convex hull of the point sites.
When the set of point sites is clear from the context we use only maxwidth.
Since we actually want to find a lower bound on the volume of circumball(∆) ∩[0,1]d
we consider the (smallest) hypercube containing all point sites that has minimal volume
when intersected with [0,1]d. In order to have a minimal intersection volume the hypercube
might jut out of [0,1]din some dimensions. In Figure 6.3 two examples are given.
Therefore, we introduce the variable value that indicates how much each dimension con-
tributes to the volume of the minimal intersection between a smallest hypercube containing
all the point sites and [0,1]d. If for a fixed dimension the coordinates of all point sites are
close to 0 (or 1) then this dimension might contribute less than maxwidth to the volume,
namely only the distance of the maximal coordinate to 0 (or the minimal coordinate to 1).
Formally, we define now the value of set Pjto be
value(Pj) :=
maxwidth(P1,...,Pd)if max Pj−maxwidth ≥0
and min Pj+ maxwidth ≤1
min {max Pj,1−min Pj}else .
74
6.2 Proof of Lemma 8
Figure 6.3: Two random triangles in [0,1]2and the smallest enclosing sphere and small-
est enclosing square with minimal intersection area are depicted. In the first
example the x1-coordinates of the three triangle’s vertices lie close to 0, in the
second example close to 1, and so the squares jut out of [0,1]2accordingly.
With these definitions we can formulate the following lemma.
Lemma 9 With the just made definition it holds that
vol(circumball(∆) ∩[0,1]d)≥min (1
22d
·Vd,1
d!)·
d
Y
j=1
value(Pj).
Proof. In order to prove the lemma we will consider two cases, namely that the center of
circumball(∆) lies inside [0,1]d(case i) and that it does not (case ii).
(i) If the center of circumball(∆) lies inside [0,1]dit follows immediately that at least a
fraction of (1/2)dof circumball(∆) lies inside [0,1]d. Together with Observation 2
we get that
vol(circumball(∆) ∩[0,1]d)≥1
2d
·volcircumball(∆)
≥1
2d
·Vd·maxwidth(∆)
2d
≥1
22d
·Vd·
d
Y
j=1
value(Pj).
75
6 Voronoi Diagram and Delaunay Triangulation
(ii) Let B=B(circumball(∆) ∩[0,1]d)be the smallest axis parallel box containing
circumball(∆) ∩[0,1]dand let b1, . . . , bdbe the width of box Bin each dimension,
i.e. vol(B) = Qd
i=1 bi. In a first step we want to show that
d!·vol(circumball(∆) ∩[0,1]d)≥vol(B).(6.3)
We will now distinguish two cases, namely that circumball(∆) ∩[0,1]dcontains at
least d+ 1 of the 2dvertices of Band that circumball(∆) ∩[0,1]dcontains less than
d+ 1 vertices of B.
So, consider the case that circumball(∆) ∩[0,1]dcontains at least d+ 1 vertices
of B. Let e1, . . . , edbe the unit vectors, i.e. the j-th entry in ejis a one and all
other entries are 0. Without loss of generality we assume that ¯
0 = (0,...,0) is
a vertex of Band that ¯
0, b1·e1, . . . , bd·edare the vertices of Bthat lie also in
circumball(∆) ∩[0,1]d. The convex hull of these vertices, namely the simplex S:=
conv(¯
0, b1·e1, . . . , bd·ed)is then also completely contained in circumball(∆)∩[0,1]d
and therefore it is vol(circumball(∆) ∩[0,1]d)≥vol(S). From geometry [HRZ97]
it is known that
vol(S) = 1
d!·vol(B)
and therefore (6.3) follows.
Let us now consider the case that circumball(∆)∩[0,1]dcontains less than d+1 ver-
tices of B. Our goal is now to place a collection of simplices inside circumball(∆)∩
[0,1]dsuch that their sum of volumes is also equal to 1/d!·vol(B).
Let c:= (c1, . . . , cd)be the center of circumball(∆) and consider the dhyper-planes
x1=c1, . . . , xd=cdthat subdivide circumball(∆) into 2dequal parts. These
hyper-planes subdivide also Binto at most 2d−1smaller boxes. (Remember, the cen-
ter cis not contained in [0,1]d, therefore we cannot get more than 2d−1of them.)
For each of the smaller boxes we will find at least d+ 1 vertices that lie also in
circumball(∆) ∩[0,1]d. As before we can take their convex hull to construct the
desired simplices, see also Figure 6.4. It follows immediately that their sum of vol-
umes is equal to 1/d!·vol(B). Thus (6.3) is shown.
In the next step we want to show that
vol(B) =
d
Y
i=1
bi≥
d
Y
j=1
value(Pj)(6.4)
which follows immediately with the following Claim 5, though we defer its proof to
the end of the proof of Lemma 9.
Claim 5 It holds that value(Pj)≤bjfor all 1≤j≤d.
76
6.2 Proof of Lemma 8
S
B
S2
S1
B
Figure 6.4: Depicted are the two possible cases in IR2. In the first case three vertices of box
Bare contained in circumball(∆) ∩[0,1]2and their convex hull, the simplex
Slies also completely in circumball(∆) ∩[0,1]2. In the second case only
two vertices of box Blie in circumball(∆) ∩[0,1]2. The hyperplane x1=c1
subdivides Binto two smaller boxes that have both three vertices contained in
circumball(∆) ∩[0,1]2. The convex hull of these give the two simplices S1
and S2.
By combining now (6.3) and (6.4) we see that
d!·vol(circumball(∆) ∩[0,1]d)≥vol(B)≥
d
Y
j=1
value(Pj)
which concludes the case (ii) and therefore the proof of Lemma 9.
B2
It remains to show that Claim 5 holds.
Proof of Claim 5. Again we will consider two cases, namely that circumball(∆) ∩[0,1]d
and therefore Bcontains at least one vertex of [0,1]d(case a) and that it does not contain a
vertex of [0,1]d(case b).
(a) Let us assume that circumball(∆) ∩[0,1]dcontains a vertex of [0,1]d, say v=
(v1, . . . , vd)where vj∈ {0,1}for 1≤j≤d. Since Bcontains all vertices of the
simplex ∆we can conclude that either max Pj≤bjif vj= 0 or that 1−min Pj≤bj
if vj= 1 for 1≤j≤d.
If value(Pj) = min {max Pj,1−min Pj}then the claim follows immediately. If
value(Pj) = maxwidth then max Pj−maxwidth ≥0and min Pj+maxwidth ≤1.
It follows that maxwidth ≤bjand therefore value(Pj)≤bjfor 1≤j≤d.
77
6 Voronoi Diagram and Delaunay Triangulation
(b) Let us now assume that circumball(∆) ∩[0,1]dcontains no vertex of [0,1]d. Since
the center of circumball(∆) /∈[0,1]dwe can assume that there is some number k,
1≤k < d such that up to ordering
b1=··· =bk> bk+1 >··· > bd.
In other words, there is a k-dimensional face Fof [0,1]dsuch that the intersection
of [0,1]dand Fis a k-ball. (If we would ‘add’ the next dimension we would obtain
a(k+ 1)-dimensional spherical cap.)
Since the box Bcontains all vertices of the simplex ∆it follows immediately that
b1=··· =bk≥maxwidth. Therefore we can conclude that value(Pj)≤bjfor
1≤j≤k.
Now consider some number j > k. Let Fxj=0 be the facet (= (d−1)-dimensional
face) of [0,1]dthat is contained in the hyperplane xj= 0 and let Fxj=1 be the facet
of [0,1]dthat is contained in the hyperplane xj= 1. Since bj< b1the box B
‘touches’ either Fxj=1 or Fxj=0, i.e. facets of Bare either contained in Fxj=1 or in
Fxj=0. And again, since Balso contains all vertices of the simplex ∆it follows that
either max Pj≤bjor that 1−min Pj≤bj. Analogously to case (a) it follows that
maxwidth ≤bjand therefore value(Pj)≤bjfor k < j ≤d.
2Claim 5
We can utilize Lemma 9 in the following way. We will show that for any value a∈[0,1]
it is
Pr"d
Y
j=1
value(Pj)≤a#≤d3d+1 ·2d·ad.(6.5)
We know that vol(circumball(∆) ∩[0,1]d)≥min (1/22d)·Vd,1
d!·Qd
j=1 value(Pj)
by Lemma 9. So we can conclude that for any value a∈[0,1] it is
Prvol(circumball(∆) ∩[0,1]d)≤a≤constd·ad,
where constd=d3d+1 ·2d·max 22d/Vd, d!d. Thus Lemma 8 is also shown.
In order to show (6.5) we will now establish two lemmas. Lemma 10 will cover the
case that maxwidth(P1,...,Pd)is at most d
√a, while Lemma 11 will cover the case that
maxwidth(P1,...,Pd)is larger than d
√a.
Before we proceed let us briefly recall the (reformulated) random process. Instead of
random point sites p1, . . . , pd+1 we consider dsets P1,...,Pdeach of d+ 1 independent
and identically distributed random numbers chosen uniformly from the interval [0,1].
Lemma 10 For any value a∈[0,1] it holds that
Pr"d
Y
j=1
value(Pj)≤a∧maxwidth(P1,...,Pd)≤d
√a#≤(d+ 1)d·ad.
78
6.2 Proof of Lemma 8
Proof. First of all we notice that from maxwidth(P1,...,Pd)≤d
√ait follows immedi-
ately that Qd
j=1 value(Pj)≤aand therefore it is
Pr"d
Y
j=1
value(Pj)≤a∧maxwidth(P1,...,Pd)≤d
√a#ABSTANDs
=Prmaxwidth(P1,...,Pd)≤d
√a.
Furthermore, it suffices to bound only the probability that width(Pj)≤d
√a, because it
also holds that
Prmaxwidth(P1,...,Pd)≤d
√a=
d
Y
j=1
Prwidth(Pj)≤d
√a.
The idea is now to fix for set Pjthe two elements4that attain the maximal distance, i.e.
the elements max Pjand min Pj. Now we can bound the probability that their distance
does not exceed d
√aand that the remaining d−1elements in Pjhave values between
max Pjand min Pj. It is
Prwidth(Pj)≤d
√a= (d+ 1) ·d·Z1
0Zy
max{0,y−d
√a}
(y−x)d−1dxdy(6.6)
where the outer integral denotes the range of element max Pj(= y)and the inner integral
the range of element min Pj(= x). The integration boundaries assure that the distance of
xand yis at most d
√a. The integrand (y−x)d−1denotes exactly the probability that all
remaining d−1elements of Pjlie between yand x. The fore-factor (d+ 1) ·dcomes
from fixing the maximal and minimal element in Pj.
In order to solve integral (6.6) we will split it up in the following way to remove the
maximum expression from the integration boundary of the inner integral
Z1
0Zy
max{0,y−d
√a}
(y−x)d−1dxdy
=Zd
√a
0Zy
0
(y−x)d−1dxdy+Z1
d
√aZy
y−d
√a
(y−x)d−1dxdy
=1
d· Zd
√a
0
yddy+Z1
d
√a
ady!=1
d·1
d+ 1 ·ad+1
d+a−ad+1
d
=1
d·a·1−1−1
d+ 1·a1/d≤1
d·a .
4Note that all elements are distinct with probability 1.
79
6 Voronoi Diagram and Delaunay Triangulation
It follows that
Prwidth(Pj)≤d
√a≤(d+ 1) ·a⇒Prmaxwidth ≤d
√a≤(d+ 1)d·ad,
which concludes the proof of Lemma 10.
B2
Lemma 11 For any value of a∈[0,1] it holds that
Pr"d
Y
j=1
value(Pj)≤a∧maxwidth(P1,...,Pd)>d
√a#≤d3d+1 ·2d·ad.
Proof. Without loss of generality, we assume some ordering on the sets P1,...,Pdas
described now. Let the first set P1attain the maximal width, i.e. width(P1)≥width(Pj)
for 2≤j≤d. It follows that maxwidth(P1,...,Pd) := width(P1).
Before we proceed let us briefly recall the definition of the function value, i.e.
value(Pj) :=
maxwidth if max Pj−maxwidth ≥0
and min Pj+ maxwidth ≤1
min {max Pj,1−min Pj}else .
For the remaining sets P2,...,Pdlet dfdenote the number of sets for which the if-case
is true (the elements of these sets lie far away from 0 or 1) and let dcdenote the number
of sets for which the else-case is true (the elements of these sets lie close to 0 or 1), such
that d= 1 + df+dc. Furthermore, let the sets be ordered such that the if-case is true for
the sets P2,...,Pdf+1 and that the else-case is true for the sets Pdf+2,...,Pd. Note that
for given dfand dcthere are exactly d!/(1! ·df!·dc!) ways to fix the described ordering
for the sets P1,...,Pd.
We will summarize the considerations just made in the following definition of three
conditions. Let
A : width(P1)>d
√a
B(df) : ^
2≤j≤df+1 width(Pj)≤width(P1)∧
max Pj≥width(P1)∧1−min Pj≥width(P1)
C(df) : ^
df+2≤j≤dwidth(Pj)<width(P1)∧
max Pj<width(P1)∨1−min Pj<width(P1).
80
6.2 Proof of Lemma 8
For condition C(df), if (max Pj<width(P1)∨min Pj<1−width(P1)) is fulfilled
it follows immediately that (width(Pj)<width(P1)) is also fulfilled.
We can now rewrite
Pr"d
Y
j=1
value(Pj)≤a∧maxwidth(P1,...,Pd)>d
√a#
=
d−2
X
df=0
d!
1! ·df!·dc!·Pr"d
Y
j=1
value(Pj)≤a∧A∧B(df)∧C(df)#,
where dc=d−df−1. The sum goes only up to df=d−2since dchas to be greater than 0
in order to make it possible that Qd
j=1 value(Pj)≤a, since otherwise it is value(Pj)>d
√a
for all j. Furthermore, by condition B(df)we know that value(Pj) = width(P1)for
1≤j≤df+ 1 and we can conclude that
Pr"d
Y
j=1
value(Pj)≤a∧A∧B(df)∧C(df)#
=Pr
d
Y
j=df+2
value(Pj)≤a
width(P1)df+1 ∧A∧B(df)∧C(df)
.(6.7)
Our goal is now to find an integral expression for (6.7). It seems useful to consider first
the three conditions A,B(df)and C(df)separately. While conditions B(df)and C(df)are
mutually independent, they both depend on condition A.
So in a first step we will find an expression for the probability that condition Aholds,
i.e. width(P1)>d
√a. As in the proof of Lemma 10 we fix the two elements in set P1that
have maximal distance, i.e. max P1(= y)and min P1(= x). Then we can write
Pr[ A ] = (d+ 1) ·d·Z1
d
√aZy−d
√a
0
(y−x)d−1dxdy . (6.8)
In a second next step we will bound the probability that condition B(df)is true. By
(6.8), we assume that width(P1) = (y−x). It is then
Pr[ B(df) ] ≤
df+1
Y
j=2
Pr[ width(Pj)≤(y−x) ]
≤(d+ 1) ·(y−x)ddf,
where the last step follows analogously to the proof of Lemma 10 on page 79.
In a third step we will consider the probability for condition C(df)to be true. The
condition C(df)holds if for all sets Pj,j∈ {df+ 2, . . . , d}, either max Pj<width(P1)
or 1−min Pj<width(P1)is true.
81
6 Voronoi Diagram and Delaunay Triangulation
We define now index sets Iand I0, where I ∪ I0={df+ 2, . . . , d}and I ∩ I0=∅,
such that for Pj,j∈ I the first case and for Pj,j∈ I0the second case is true. Then we
can write
Pr[ C(df) ] =
d
Y
j=df+2
Pr[ max Pj<width(P1)∨1−min Pj<width(P1) ]
≤X
I,I0 Y
j∈I
Pr[ max Pj<(y−x) ] ·Y
j∈I0
Pr[ 1 −min Pj<(y−x) ]!
= 2dc·
d
Y
j=df+2
Pr[ max Pj<(y−x) ] ,
where the last step follows since Pr[ 1 −min Pj<(y−x) ] = Pr[ max Pj<(y−x) ].
We can now conclude for (6.7) that
Pr
d
Y
j=df+2
value(Pj)≤a
width(P1)df+1 ∧A∧B(df)∧C(df)
= (d+ 1) ·d·Z1
d
√aZy−d
√a
0
(y−x)d−1·Pr[ B(df) ] ·
Pr
d
Y
j=df+2
value(Pj)≤a
(y−x)df+1 ∧C(df)
dxdy
≤(d+ 1)df+1 ·d·2dc·Z1
d
√aZy−d
√a
0
(y−x)d−1+df·d·
Pr
d
Y
j=df+2
max Pj≤¯a∧^
df+2≤j≤d
max Pj<(y−x)
dxdy
where ¯a:= a/(y−x)df+1. What remains to be shown is captured by the following claim.
Claim 6 For any value of ¯a∈[0,1] it holds that
Pr
d
Y
j=df+2
max Pj≤¯a∧^
df+2≤j≤d
max Pj<(y−x)
≤2·(d+ 1)dc−1·(dc−1)dc−1·¯ad·(y−x)dc≤ O(d)·¯ad·(y−x)dc.
The proof of Claim 6 is deferred to the end of this subsection.
82
6.2 Proof of Lemma 8
From Claim 6 it follows that
(6.7) ≤(d+ 1)df+1 ·d·2dc·2·(d+ 1)dc−1·(dc−1)dc−1·
ABSTANDABSTAND Z1
d
√aZy−d
√a
0
¯ad·(y−x)d−1+df·d+dcdxdy
= (d+ 1)d−1·d·2dc+1 ·(dc−1)dc−1·ad·Z1
d
√aZy−d
√a
0
(y−x)dc−1dxdy .
Now for the integral in this last expression we get
Z1
d
√aZy−d
√a
0
(y−x)dc−1dxdy=1
dc·Z1
d
√a
ydc−d
√adcdy
=1
dc·1
dc+ 1 −d
√adc−1
dc+ 1 ·d
√adc+1 −d
√adc+1
=1
dc·1
dc+ 1 −d
√adc·1−1−1
dc+ 1·d
√a
| {z }
>0
≤1
dc·(dc+ 1) .
And finally it follows that
Pr"d
Y
j=1
value(Pj)≤a∧maxwidth(P1,...,Pd)>d
√a#
≤
d−2
X
df=0
d!
1! ·df!·dc!·(d+ 1)d−1·d·2dc+1 ·(dc−1)dc−1·1
dc·(dc+ 1) ·ad
≤d3d+1 ·2d·ad
which concludes the proof of Lemma 11. B2
From Lemma 10 and Lemma 11 it follows that (6.2) holds for
constd=d3d+1 ·2d·max 22d
Vd
, d!d
≤(c·d)d2,
for some constant factor c, and thus Lemma 8 is shown.
It remains to prove Claim 6 from the previous page. Recall that ¯a=a/(y−x)df+1 and
that d=df+dc+ 1.
83
6 Voronoi Diagram and Delaunay Triangulation
Claim 6 For any value of ¯a∈[0,1] it holds that
Pr
d
Y
j=df+2
max Pj≤¯a∧^
df+2≤j≤d
max Pj<(y−x)
≤2·(d+ 1)dc−1·(dc−1)dc−1·¯ad·(y−x)dc≤ O(d)·¯ad·(y−x)dc.
Proof of Claim 6. For ease of notation the enumeration of the sets Pdf+2,...,Pdis changed
to P1,...,Pdc. For 1≤j≤dc−1it is then
Pr[ max Pj<(y−x) ] = (d+ 1) ·Z(y−x)
0
zd
jdzj
where the fore-factor (d+ 1) comes from fixing the maximal element max Pj(= zj). The
integrant zd
jdenotes exactly the probability that the remaining delements in Pjare at most
zj. By the integration boundaries it follows that all elements in Pjare smaller than (y−x).
Now for the set Pdc, in order to guarantee that Qdc
j=1 max Pj≤¯ait is necessary that
max Pdcdoes not exceed ¯a/z1···zdc−1(and also not (y−x)). It is
Prmax Pdc<min (y−x),¯a
z1···zdc−1
= (d+ 1) ·Zmin(y−x),¯a
z1···zdc−1ff
0
zd
dcdzdc
=min (y−x),¯a
z1···zdc−1d+1
=: K.
From the independence of the events max Pj≤¯ait follows that
Pr"dc
Y
j=1
max Pj≤¯amax Pj<(y−x),1≤j≤dc#
= (d+ 1)dc−1·Z(y−x)
0···Z(y−x)
0
zd
1···zd
dc−1·K dz1··· dzdc−1(6.9)
where the fore-factor (d+ 1)dc−1comes from fixing the maximal element in the sets
P1,...,Pdc−1.
In order to solve the integral in (6.9) we start with some preliminary observation. For
all k∈IN let
R(k) := ¯a
(y−x)k.
84
6.2 Proof of Lemma 8
Observation 3 Since ¯a=a/(y−x)d−dcand (y−x)>d
√ait follows that
R(dc−1) <(y−x).
Now we will split up the outermost integral in (6.9) into two integrals, one going from
0to R(dc−1) and the other from R(dc−1) to (y−x). The first integral can be solved in
a straightforward way. To solve the second integral we split it up again into two integrals
with appropriate integration boundaries. This process continues and leads finally to a sum
of solvable integrals.
It is now
Z(y−x)
0···Z(y−x)
0
zd
1···zd
dc−1·K dz1··· dzdc−1
=ZR(dc−1)
0Z(y−x)
0···Z(y−x)
0
zd
1···zd
dc−1·K dz1··· dzdc−1(6.10)
+Z(y−x)
R(dc−1) Z(y−x)
0···Z(y−x)
0
zd
1···zd
dc−1·K dz1··· dzdc−1.(6.11)
Inintegral (6.10)thevariable zdc−1is bounded by R(dc−1) and thevariablesz1, . . . , zdc−2
are bounded by (y−x). Therefore, we can conclude that
¯a
z1···zdc−1≥¯a
(y−x)dc−2·R(dc−1) = (y−x).
It follows then that K= (y−x)d+1 and therefore it is
(6.10) = ZR(dc−1)
0Z(y−x)
0···Z(y−x)
0
zd
1···zd
dc−1·(y−x)d+1 dz1··· dzdc−1
=ZR(dc−1)
01
d+ 1dc−2
·(y−x)(d+1)·(dc−1) ·zd
dc−1dzdc−1
=1
d+ 1dc−1
·(y−x)(d+1)·(dc−1) ·¯ad+1 ·1
(y−x)(d+1)·(dc−1)
=1
d+ 1dc−1
·¯ad+1 .
In order to solve integral (6.11) we will split up the second outermost integral into two
integrals, one going from 0to R(dc−2)/zdc−1and the other from R(dc−2)/zdc−1to
(y−x).
(6.11) = Z(y−x)
R(dc−1) ZR(dc−2)/zdc−1
0···Z(y−x)
0
zd
1···zd
dc−1·K dz1··· dzdc−1ABS(6.12)
+Z(y−x)
R(dc−1) Z(y−x)
R(dc−2)/zdc−1···Z(y−x)
0
zd
1···zd
dc−1·K dz1··· dzdc−1(6.13)
85
6 Voronoi Diagram and Delaunay Triangulation
The integral (6.12) can be solved in a straightforward way. Since the variable zdc−2is
bounded by R(dc−2)/zdc−1we can conclude that
¯a
z1···zdc−1≥¯a·zdc−1
(y−x)dc−3·R(dc−2) ·zdc−1
= (y−x).
It follows again that K= (y−x)d+1 and therefore it is
(6.12) = Z(y−x)
R(dc−1) ZR(dc−2)/zdc−1
0···Z(y−x)
0
zd
1···zd
dc−1·(y−x)d+1 dz1··· dzdc−1
=Z(y−x)
R(dc−1) ZR(dc−2)/zdc−1
01
d+ 1dc−3
·zd
dc−2·zd
dc−1·(y−x)(d+1)·(dc−2) dzdc−2dzdc−1
=Z(y−x)
R(dc−1) 1
d+ 1dc−2
·¯ad+1 ·1
zdc−1
dzdc−1
=1
d+ 1dc−2
·¯ad+1 ·ln (y−x)dc
¯a.
In order to solve integral (6.13) we will split up the third outermost integral into two
integrals, one going from 0to R(dc−3)/(zdc−2·zdc−1)and the other from Rdc−3/(zdc−2·
zdc−1)to (y−x). The whole process continues now analogously. The computation of the
next integral is briefly outlined for reasons of better understanding although the depiction
becomes more and more uncomfortable. It is
(6.13) = Z(y−x)
R(dc−1) Z(y−x)
R(dc−2)/zdc−1ZR(dc−3)/(zdc−2·zdc−1)
0···Z(y−x)
0
. . . ABS(6.14)
+Z(y−x)
R(dc−1) Z(y−x)
R(dc−2)/zdc−1Z(y−x)
R(dc−3)/(zdc−2·zdc−1)···Z(y−x)
0
. . . (6.15)
As before we can conclude from the ranges of the variables z1, . . . , zdc−1that again
K= (y−x)d+1. After solving the inner integrals up to the two outermost ones it remains
that
(6.14) = Z(y−x)
R(dc−1) Z(y−x)
R(dc−2)/zdc−11
d+ 1dc−3
·¯ad+1 ·1
zdc−2·zdc−1
dzdc−2dzdc−1
=1
d+ 1dc−3
·¯ad+1 ·Z(y−x)
R(dc−1)
ln zdc−1·(y−x)dc−1
¯a·1
zdc−1
dzdc−1
≤1
d+ 1dc−3
·¯ad+1 ·ln (y−x)dc
¯a·Z(y−x)
R(dc−1)
1
zdc−1
dzdc−1
=1
d+ 1dc−3
·¯ad+1 ·ln (y−x)dc
¯a2
.
86
6.2 Proof of Lemma 8
With integral (6.15) we proceed analogously. To summarize the results so far we con-
clude that
(6.9) ≤(d+ 1)dc−1·¯ad+1 ·
dc
X
i=1 1
d+ 1dc−i
·ln (y−x)dc
¯a
| {z }
>1i−1
.(6.16)
This can be simplified by the following observation.
Observation 4 For all x > 1and all k≥1it is ln(x)k≤(k/e)k·x.
It follows that
(6.16) ≤(d+ 1)dc−1·¯ad+1 ·
dc
X
i=1 1
d+ 1dc−i
·i−1
ei−1(y−x)dc
¯a
≤2·(d+ 1)dc−1·(dc−1)dc−1·¯ad·(y−x)dc
and thus Claim 6 is shown. 2Claim 6
Finally, let us have a brief look at Observation 4 which follows also easily. Consider the
following function together with its first and second derivative, namely
fk(x) := ln(x)k/x
f0
k(x)=(k·ln(x)k−1−ln(x)k)/x2
f00
k(x)=(k·(k−1) ·ln(x)k−2−3k·ln(x)k−1+ 2 ·ln(x)k)/x3.
It holds now that f0
k(x)=0 ⇐⇒ k·ln(x)k−1= ln(x)k⇐⇒ x=ek. Since
f00
k(ek) = −kk−1/e3k<0it follows that for x=ekthe function f(x)attains a maximum.
Therefore it is
fk(x)≤fk(ek) = k
ek
for x > 1and k≥1.
87
6 Voronoi Diagram and Delaunay Triangulation
88
7 Summary and Open Problems
In this thesis, the concept of smoothed analysis is applied to the area of computational
geometry. In the past, the use of smoothed analysis had a basically complexity theoreti-
cal motivation which holds of course also for problems in computational geometry. But
besides this, we identified two other reasons that motivate the use of smoothed analysis
particularly well in the field of computational geometry.
In many applications, concepts and methods from computational geometry are applied
to data coming from physical measurements which are imprecise and thus afflicted with
some noise. By the assumption that such measurement errors are distributed according to
the Gaussian normal distribution, smoothed analysis provides a new complexity measure
for this class of inputs. Another motivation lies in the fact that computers use only fixed
precision arithmetic. This error can be modeled by the assumption that an input point is
uniformly distributed in a hypercube around its real position.
In this thesis, the complexity of a fundamental geometric structure is considered and
analysed in the smoothed case, namely the number of extreme points of the convex hull of
a point set. It seems very promising to continue this work and to consider the smoothed
complexity of other geometric structures such as the Voronoi diagram or Delaunay trian-
gulation of point sets.
A first step toward the smoothed analysis of the Voronoi diagram is already done. The
average case analysis for points chosen uniformly from a hypercube might be a good start-
ing point. Since the Voronoi diagram is a rather relevant geometric structure that can be
found in a large variety of applications, a smoothed analysis of this structure is definitively
very interesting.
Another interesting and surprising result is surely that different probability distributions
lead to a different smoothed complexity. E.g. for the number of extreme points of the
convex hull, there is a significant gap between the smoothed complexity under Gaussian
normal and uniform noise. The smoothed number of extreme points under Gaussian nor-
mal noise is only poly-logarithmic in the number of input points, while it is polynomial
under uniform noise. This result implies directly the following questions and open prob-
lems.
•For which probability distributions is the smoothed complexity low or high?
•What is the decisive property of these distributions to cause either low or high
smoothed complexity?
•Is the smoothed complexity under Gaussian normal noise the ‘best’ we can get?
89
7 Summary and Open Problems
•Is the smoothed complexity under uniform noise the ‘worst’ we can get?
It remains to mention that smoothed analysis is also very well motivated in the context
of analysing motion. In this thesis, a new complexity measure for motion is introduced,
the smoothed motion complexity. Especially in the development of algorithms and data
structures smoothed analysis might lead to very interesting new results. A first step might
be to develop a kinetic data structure for maintaining the bounding box of a linearly moving
point set that is efficient compared to the smoothed motion complexity instead of the worst
case motion complexity.
90
Bibliography
[AH01] P. Agarwal and S. Har-Peled. Maintaining approximate extent measures of
moving points. In Proceedings of the 12th ACM-SIAM Symposium on Dis-
crete Algorithms (SODA), pages 148–157, 2001.
[Aur91] F. Aurenhammer. Voronoi diagrams – a survey of a fundamental geometric
data structure. ACM Computing Surveys, 23:345–405, 1991.
[AW91] F. Affentranger and J. A. Wieacker. On the convex hull of uniform randowm
points in a simple d-polytope. Discrete & Computational Geometry, 6:291–
305, 1991.
[BD02] A. Blum and J. Dunagan. Smoothed analysis of the perceptron algorithm.
In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 905–914, 2002.
[BDMS05] M. Bienkowski, V. Damerow, F. Meyer auf der Heide, and C. Sohler. Av-
erage case complexity of voronoi digrams of nsites from the unit cube. In
Proceedings of the 21st European Workshop on Computational Geometry
(EWCG), pages 167–170, 2005.
[BGH99] J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data.
Journal of Algorithms, 31(1):1–28, 1999.
[BGZ97] J. Basch, L. J. Guibas, and L. Zhang. Proximity problems on moving points.
In Proceedings of the 13th Annual ACM Symposium on Computational Ge-
ometry (SoCG), pages 344–351, 1997.
[BKST78] J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson. On the
average number of maxima in a set of vectors. Journal of the Association for
Computing Machinery, 25:536–543, 1978.
[BLMS+03] L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Sch¨
afer, and T. Vre-
develd. Average and smoothed competitive analysis of the multi-level feed-
back algorithm. In Proceedings of the 44th IEEE Symposium on Foundations
of Computer Science (FOCS), pages 462–471, 2003.
[Blu73] H. Blum. Biological shape and visual science (Part i). Journal of Theoretical
Biology, 38:205–287, 1973.
91
Bibliography
[BMB03] C. Banderier, K. Mehlhorn, and R. Beier. Smoothed analysis of three com-
binatorial problems. In Proceedings of the 28th International Symposium on
Mathematical Foundations of Computer Science (MFCS), pages 198–207,
2003.
[BMS04] V. Bansal, F. Meyer auf der Heide, and C. Sohler. Labeling smart dust. In
Proceedings of the 12th European Symposium on Algorithms (ESA), pages
77–88, 2004.
[Bor80] K. H. Borgwardt. The simplex method: a probabilistic analysis. Springer,
1980.
[Bro79] K. Q. Brown. Voronoi diagrams from convex hulls. Information Processing
Letters, 9:223–228, 1979.
[Bro80] K. Q. Brown. Geometric transforms for fast geometric algorithms. PhD
thesis, Carnegie-Mellon University, Pittsburgh, Pennsylvania, USA, 1980.
[BTT85] C. Buchta, F. Tichy, and R. F. Tichy. Stochastical approximation of convex
bodies. Mathematische Annalen, 271(2):225–235, 1985.
[Buc89] C. Buchta. On the average number of maxima in a set of vectors. Information
Processing Letters, 33:63–65, 1989.
[BV04a] R. Beier and B. V¨
ocking. Random knapsack in expected polynomial time.
Journal of Computer and System Sciences, 69(3):306–329, 2004. Also in
Proceedings of the 35th Annual ACM Symposium on Theory of Computing
(STOC), pages 232–241, 2003.
[BV04b] R. Beier and B. V¨
ocking. Typical properties of winners and losers in discrete
optimization. In Proceedings of the 36th ACM Symposium on Theory of
Computing (STOC), pages 343–352, 2004.
[Car70] H. Carnal. Die konvexe H¨
ulle von nrotationssymmetrisch verteilten Punk-
ten. Zentralblatt f¨
ur Wahrscheinlichkeitstheorie und verwandte Gebiete,
15:168–176, 1970.
[Cha91] B. Chazelle. An optimal convex hull algorithm and new results on cuttings.
In Proceedings of the 32th IEEE Symposium on Foundations of Computer
Science (FOCS), pages 29–38, 1991.
[Cha96a] T. M. Chan. Optimal output-sensitive convex hull algorithms in two and
three dimensions. Discrete & Computational Geometry, 16:361–368, 1996.
[Cha96b] T. M. Chan. Output-sensitive results on convex hulls, extreme points, and
related problems. Discrete & Computational Geometry, 16:369–378, 1996.
92
Bibliography
[CK70] D. R. Chand and S. S. Kapur. An algorithm for convex polytopes. Journal
of the ACM, 17(1):78–86, 1970.
[Cla94] K. L. Clarkson. More output-sensitive geometric algorithms. In Proceedings
of the 35th IEEE Symposium on Foundations of Computer Science (FOCS),
pages 695–702, 1994.
[CM95] B. Chazelle and J. Matouˇ
sek. Derandomizing an output-sensitive convex
hull algorithm in three dimenisons. Comput. Geom. Theory Appl., 5:27–32,
1995.
[CS88] J. H. Conway and N. J. A. Sloane. Sphere Packing, Lattices and Groups.
Springer-Verlag, New York, 1988.
[Del34] B. N. Delaunay. Sur la sphere vide. Bulletin of Academy of Sciences of the
USSR, pages 793–800, 1934.
[Dir50] G. L. Dirichlet. ¨
Uber die Reduction der positiven quadratischen Formen mit
drei unbestimmten ganzen Zahlen. Journal f¨
ur die Reine und Angewandte
Mathematik, 40:209–227, 1850.
[DMR+03] V. Damerow, F. Meyer auf der Heide, H. R¨
acke, C. Scheideler, and C. Sohler.
Smoothed motion complexity. In Proceedings of the 11th European Sympo-
sium on Algorithms (ESA), pages 161–171, 2003.
[DS04a] V. Damerow and C. Sohler. Extreme points under random noise. In Proceed-
ings of the 12th European Symposium on Algorithms (ESA), pages 264–274,
2004.
[DS04b] V. Damerow and C. Sohler. Smoothed number of extreme points under uni-
form noise. In Proceedings of the 20th European Workshop on Computa-
tional Geometry (EWCG), pages 93–96, 2004.
[DST03] J. Dunagan, D. A. Spielman, and S.-H. Teng. Smoothed analysis of interior-
point algorithms: Condition number. Computing Research Repository,
cs.DS/0302011, 2003.
[dvOS00] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computa-
tional Geometry. Springer, 2 edition, 1997, 2000.
[Dwy90] R. A. Dwyer. Kinder, gentler average-case analysis for convex hulls and
maximal vectors. SIGACT News, 21:64–71, 1990.
[Dwy91] R. A. Dwyer. Higher-dimensional Voronoi diagrams in linear expected time.
Discrete & Computational Geometry, 6:343–367, 1991. Also in Proceedings
of the 5th Annual ACM Symposium on Computational Geometry (SoCG),
pages 326–333, 1989.
93
Bibliography
[Efr65] B. Efron. The convex hull of a random set of points. Biometrika, 52:331–
343, 1965.
[Eri01] J. Erickson. Nice point sets can have nasty Delaunay triangulations. In Pro-
ceedings of the 17th Annual ACM Symposium on Computational Geometry
(SoCG), pages 96–105, 2001.
[FF04] A. D. Flaxman and A. M. Frieze. The diameter of randomly perturbed di-
graphs and some applications. In Proceedings of the 7th International Work-
shop on Approximation Algorithms for Combinatorial Optimization Prob-
lems and 8th International Workshop on Randomization and Computation
(APPROX-RANDOM), pages 345–356, 2004.
[For87] S. Fortune. A sweepline algorithm for Vorono diagrams. Algorithmica,
2:153–174, 1987.
[For97] S. Fortune. Voronoi diagrams and Delaunay triangulations, chapter 20 in
J. E. Goodman and J. O’Rourke, editors, Handbook of discrete and compu-
tational geometry, pages 377–388. CRC Press, 1997.
[Gau40] C. F. Gauss. Recursion der Untersuchungen ¨
uber die Eigenschaften der po-
sitiven tern¨
aren quadratischen Formen von Ludwig August Seeber. Journal
f¨
ur die Reine und Angewandte Mathematik, 20:312–320, 1840.
[GHSZ01] L. J. Guibas, J. Hershberger, S. Suri, and L. Zhang. Kinetic connectivity for
unit disks. Discrete & Computational Geometry, 25(4):591–610, 2001.
[GKS92] L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construc-
tion of Delaunay and Voronoi diagrams. Algorithmica, 7(4):381–413, 1992.
Also in Proceedings of the 17th International Colloquium on Automata, Lan-
guages and Programming (ICALP), pages 414–431, 1990.
[GN03] M. J. Golin and H.-S. Na. On the average complexity of 3D-Voronoi di-
agrams of random points on convex polytopes. Computational Geometry,
25:197–231, 2003.
[Har98] S. Har-Peled. On the expected complexity of random convex hulls. Technical
Report 330, School of Mathematical Science, Tel-Aviv University, Tel-Aviv,
Israel, 1998.
[Har04] S. Har-Peled. Clustering motion. Discrete & Computational Geometry,
31(4):545–565, 2004. Also in Proceedings of the 42th IEEE Symposium
on Foundations of Computer Science (FOCS), pages 84–93, 2001.
94
Bibliography
[HRZ97] M. Henk, J. Richter-Gebert, and G. M. Ziegler. Basic Properties of Convex
Polytopes, chapter 13 in J. E. Goodman and J. O’Rourke, editors, Handbook
of discrete and computational geometry, pages 243–270. CRC Press, 1997.
[HS01] J. Hershberger and S. Suri. Simplified kinetic connectivity for rectangles and
hypercubes. In Proceedings of the 12th ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 158–167, 2001.
[Kem84] R. Kemp. Fundamentals of the Average Case Analysis of Particular Algo-
rithms. B. G. Teubner, John Wiley & Sons, 1984.
[Kle80] V. Klee. On the complexity of d-dimensional Voronoi diagrams. Archiv der
Mathematik, 34:75–80, 1980.
[KM72] V. Klee and G. J. Minty. How good is the simplex algorithm? In Shisha, O.,
editor, Inequalities – III, pages 159–175, Academic Press, 1972.
[Knu97] D. E. Knuth. The Art of Computer Programming, volume 1. Addison Wesley
Longman, 3 edition, 1997.
[KS86] D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm?
SIAM Journal on Computing, 15:287–299, 1986.
[KSS02] D. Kirkpatrick, J. Snoeyink, and B. Speckmann. Kinetic collision detection
for simple polygons. International Journal of Computational Geometry and
Applications, 12(1-2):3–27, 2002.
[Kur53] M. Kurita. On some formulas about volume and surface area. Nagoya Math-
ematical Journal, 6:109–117, 1953.
[LL83] G. Louchard and G. Latouche, editors. Probability Theory and Computer
Science. Academic Press, 1983.
[Mat93] J. Matouˇ
sek. Linear optimization queries. Journal of Algorithms, 14:432–
448, 1993. Also with O. Schwartzkopf in Proceedings of the 8th Annual
ACM Symposium on Computation Geometry (SoCG), pages 16–25, 1992.
[McM70] P. McMullen. The number of faces of a convex polytope. Mathematika,
17:179–184, 1970.
[Meg84] N. Megiddo. Linear programming in linear time when the dimension is fixed.
Journal of the Association for Computing Machinery, 31:114–127, 1984.
[OBS92] A. Okabe, B. Boots, and K. Sugihara. Spatial Tesselation: Concepts and
Applications of Voronoi Diagrams. Wiley, Chichester, 1992.
95
Bibliography
[Ray65] H. Raynaud. Sur le comportement asymptotique de l’enveloppe con-
vexe d’un nuage de points tir´
es au hasard dans Rn.Comptes Rendus de
l’Acad`
emie des Sciences Paris, 261:627–629, 1965.
[Ray70] H. Raynaud. Sur l’enveloppe convexe des nuages de points al´
eatoires dans
Rn.Journal of Applied Probability, 7:35–48, 1970.
[RS63] A. R´
enyi and R. Sulanke. ¨
Uber die konvexe H¨
ulle von nzuf¨
allig gew¨
ahlten
Punkten I. Zentralblatt f¨
ur Wahrscheinlichkeitstheorie und verwandte Gebi-
ete, 2:75–84, 1963.
[RS64] A. R´
enyi and R. Sulanke. ¨
Uber die konvexe H¨
ulle von nzuf¨
allig gew¨
ahlten
Punkten II. Zentralblatt f¨
ur Wahrscheinlichkeitstheorie und verwandte Ge-
biete, 3:138–147, 1964.
[RV05] H. R¨
oglin and B. V¨
ocking. Smoothed analysis of integer programming. In
Proceedings of the 11th Conference on Integer Programming and Combina-
torial Optimization, pages 276–290, 2005.
[San04] A. Sankar. Smoothed Analysis of Gaussian elimination. PhD thesis, Mas-
sachussetts Institute of Technology, Boston, Massachusetts, USA, 2004.
[Sei87] R. Seidel. On the number of faces in higher-dimensional Voronoi dia-
grams. In Annual ACM Symposium on Computational Geometry (SoCG),
pages 181–185, 1987.
[Sei97] R. Seidel. Convex hull computations, chapter 19 in J. E. Goodman and J.
O’Rourke, editors, Handbook of discrete and computational geometry, pages
361–375. CRC Press, 1997.
[Sha78] M. I. Shamos. Computational Geometry. PhD thesis, Yale University, New
Haven, Connecticut, USA, 1978.
[Spi] D. A. Spielman. http://www-math.mit.edu/˜spielman/
SmoothedAnalysis/mfcs03comment.html.
[SST03] A. Sankar, D. A. Spielman, and S.-H. Teng. Smoothed analysis of the con-
dition numbers and growth factors of matrices. Computing Research Repos-
itory, cs.NA/0310022, 2003.
[ST03a] D. A. Spielman and S.-H. Teng. Smoothed analysis: motivation and dis-
crete models. In Proceedings of the 8th Workshop on Algorithms and Data
Structures (WADS), pages 256–270, 2003.
96
Bibliography
[ST03b] D. A. Spielman and S.-H. Teng. Smoothed analysis of interior-point al-
gorithms: termination. Computing Research Repository, cs.NA/0310022,
2003.
[ST04] D. A. Spielman and S.-H. Teng. Smoothed analysis of algorithms: Why
the simplex algorithm usually takes polynomial time. Journal of the ACM,
51(3):385–463, 2004. Also in Proceedings of the 33th Annual ACM Sympo-
sium on Theory of Computing (STOC), pages 296–305, 2001.
[Thi11] A. H. Thiessen. Percipitation average for large area. Monthly Weather Re-
view, 39:1082–1084, 1911.
[Vor08] M. G. Voronoi. Nouvelles applications des parametres continus `
a la the-
orie des formes quadratique, deuxi`
eme m´
emoire: recherches sur les par-
all´
ello`
edres primitifs. Journal f¨
ur die Reine und Angewandte Mathematik,
134:198–287, 1908.
[Wei] E. W. Weisstein. Pappus’s centroid theorem. From MathWorld–
A Wolfram Web Resource. http://mathworld.wolfram.com/
PappussCentroidTheorem.html.
[WS33] E. Wigner and F. Seitz. On the constitution of metallic sodium. Physical
Reviews, 43:804–810, 1933.
[ZDBI97] L. Zhang, H. Devarajan, J. Basch, and P. Indyk. Probabilistic analysis for
combinatorial functions of moving points. In Proceedings of the 13th An-
nual ACM Symposium on Computational Geometry (SoCG), pages 442–444,
1997.
97
