Tamal Dey
Ohio State University
Surface Reconstruction and Meshing: Algorithms with Mathematical Analysis


Surface Reconstruction and Meshing : Algorithms with Mathematical Analysis
The problem of meshing a surface arises in various applications of
science and engineering with different requirements on input and output.
Surface reconstruction is the meshing problem when the input
is a mere point sample. The first part of the tutorial will
focus on the recent development of epsilonsampling theory
and Delaunay based algorithms for surface reconstruction. We will
go over some of the key algorithms and their proofs of guarantees.
Most of these materials including exercises will be drawn
from a book recently finished by the speaker.
In the second part of the tutorial we will go over Delaunay
refinement methods that have been developed for
meshing of polyhedral and smooth surfaces. For polyhedral surfaces
we first present a Delaunay refinement method that works for
inputs with no acute angles and then present an extension
of it to handle small angles. For smooth surfaces
we discuss a Delaunay refinement technique which is motivated
by the epsilonsampling theory where toplogy plays a significant role.
Most of these algorithms have been implemented and
we will present results from implementation.

Joel Spencer
New York University
Lecture I: Erdos Magic
Lecture II: The ErdosRenyi Phase Transition


I Erdos Magic
Sixty years ago Paul Erdös started a methodology to prove
the existence of mathematical objects. In modern terms, a randomized
algorithm is given that may create the desired object. If one can prove
the algorithm has a positive probability of success then the object must
exist. We examine several examples:

finding an independent set in a graph. (Idea: Greedy Algorithm)

given sets A1,
…, An finding (not always possible!) a
two coloring of the underlying points so that no
Ai is monochromatic.
(Idea: Color Randomly)

given n sets A1
, …, An
on n vertices find a twocoloring of the underlying points so that for each
Ai the
"discrepency", the difference between the number of points in
Ai in the two
colors, is small. (Idea: Color Randomly)

Find n points in the unit square so that none of the triangles
formed by any three of the points is "too small." (Idea: Throw down
points at random but then appropriately "modify".)
We further discuss "derandomization," replacing the Erdöstype
argument with an explicit and rapid algorithm.
II The ErdosRenyi Phase Transition
Some forty five years ago Paul Erdös and Alfred
Rényi wrote "On the Evolution of Random Graphs." We begin with
a general discussion of the random graph G(n,p), having n vertices
and probability p of adjacency. Erdös and Rényi
recognized that the random graph G(n,p) undergoes a
fundamental change when p ~ 1/n. Parametrizing p=c/n,
while c<1 all components are small and simple but when c>1 a
complex giant component has emerged. Today we recognize this as a
phase transition. Phase transitions (= sudden change, e.g., freezing)
appear in mathematical physics (e.g., bond percolation on
Zd),
computer science (e.g., random kSAT) and other places and we give a
general discussion of them. For ErdösRényi percolation we can
expand the c=1 value and we explain why the "proper" parametrization for
the "critical window" is p=
n1 +
λ n4/3.
We explore this percolation phenomenon from a variety of viewpoints.
One new approach (joint with Remco van der Hofstad) involves a novel
analysis of the Breadth First Search algorithm on the random graph G(n,p).
abstract.pdf

Ingo Wegener
Universität Dortmund
Randomized Search Heuristics: Concept and Analysis


I Concepts of randomized search heuristics and tools for their analysis
Randomized search heuristics are in the world and find many applications for
realworld problems. Their common concept will be explained and it will be
discussed when randomized search heuristics are more appropriate than
problemspecific algorithms. Algorithms which are applied should be analyzed with
respect to the necessary resources. The basic tools to analyze randomized search
heuristics are presented and applied in typical situations.
II Simulated annealing vs. Metropolis and the blackbox complexity of search problems
Simulated annealing is often not more efficient than the Metropolis algorithm with
an optimal temperature. Jerrum and Sinclair have stated the problem to present an
example from combinatorial optimization where simulated annealing with a reasonable
cooling schedule beats the Metropolis algorithm with an arbitrary temperature. The
problem is solved by the investigation of the minimum spanning tree problem. In
complexity theory, we are interested in lower bounds on the resources necessary
to solve a problem. The theory of blackbox complexity leads to such lower bounds.
The theory is presented and applied.
