Program

Tamal Dey

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 epsilon-sampling 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 epsilon-sampling theory where toplogy plays a significant role. Most of these algorithms have been implemented and we will present results from implementation.

Joel Spencer

Lecture I: Erdos Magic

Lecture II: The Erdos-Renyi 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:

1. finding an independent set in a graph. (Idea: Greedy Algorithm)
2. given sets A1, …, An finding (not always possible!) a two coloring of the underlying points so that no Ai is monochromatic. (Idea: Color Randomly)
3. given n sets A1 , …, An on n vertices find a two-coloring 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)
4. 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ös-type argument with an explicit and rapid algorithm.

II The Erdos-Renyi 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 k-SAT) and other places and we give a general discussion of them. For Erdös-Rényi percolation we can expand the c=1 value and we explain why the "proper" parametrization for the "critical window" is p= n-1 + λ n-4/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

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 real-world problems. Their common concept will be explained and it will be discussed when randomized search heuristics are more appropriate than problem-specific 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 black-box 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 black-box complexity leads to such lower bounds. The theory is presented and applied.