CS 591 T1COMPUTATIONAL GEOMETRY and SCIENTIFIC COMPUTING 
COURSE INFO
Professor:  ShangHua Teng 
Lecture Time:  11:0012:30 at Tuesday and Thursday
CAS B18B

Office Hour:  Tuesday 12:30pm  2pm or by appointment (Room 276) 
Prerequisites:  CS 530 or consent of the instructor. 
Recommended Textbook:  " Computational Geometry: Algorithms and Applications " Second Edition by Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf 
Requirements and Performance Evaluation: 
The class will not have any exams, but instead, the performance
will be evaluated based on the following:

Homework Problem 1:
Suppose X = {1,2,...,n} is a set of n numbers.
If we choose a random element x from X ,
it is not hard to show that x is a (1/4)median
with probability 1/2. Now suppose we choose a sample of
S of k random elements from X
and let s be the median of S , then
what is the probability that s is a cmedian of
X , where 0 < c < 1/2
We can write a program to run an experiment first to set up
your conjecture before you prove it.
Due date: January 31st, 2002
Note for grading: this homework is graded into three dimensional scores
(f,b,c) where each score is 05, 5 is highest, and
f: the formulation score, 5 for correct formulation.
b: for simplication and estimation.
c: for meaningful experiment.
Homework Problem 2:
Suppose P is a set of n points in
2 dimensions. Design a divideandconquer
algorithm that finds the pair of points in P
that are the closest among all pairs.
What is the complexity of your algorithm? Why?
Can you extend your algorithm to d dimensions?
What is the complexity of your algorithm in d dimensions?
Why?
Due date: Feb. 21st 2002
solution
Homework Problem 3:
Suppose P is a set of n points in
2 dimensions.
The Euclidean Travelling Saleman problem (ETS)
looks for an optimal (shortest in length) tour
that passes through every point in
P .
This problem is NPhard. In this homework,
design an algorithm that will return a tour
whose total distance is no more than 1.5 times the
optimal possible. Prove why this is the case with
your algorithm.
(Hint: Use Delaunay triangulation of the point set)
Due date: March 14th 2002
Programming Project 1:
Implement the random incremental Delaunay algorithm.
The input is a point set in two dimensions.
The output is the Delaunay triangulation.
Incorporate in a graphics package (even Matlab is ok)
to display the output.
Due date: April 11st 2002
LECTURE NOTES (This section of the webpage will be growing and evolving)
Number  Topic  Notes  
1 (Jan. 15)  Introduction and Median Approximation  ps, latex  
2 (Jan. 17)  Centerpoints, Helly Theorem and Convexity  ps, latex  
3 (Jan. 22)  Radon Iterations and Centerpoint Approximation  ps, latex  
4 (Jan. 24)  Nearest Neighbor Problems  ps, latex  
5 (Jan. 29)  Sphere Packing: Graph and Geometry  ps, latex  
6 (Jan. 31)  Conformal Mappings  ps, latex  
7 (Feb. 5)  Conformal Mappings  ps, latex  
8 (Feb. 7)  MillerTengThurstonVavasis Geometric Separator Theorem 
ps, latex  
9 (Feb. 12)  Koebe Embedding and Geometric Graphs  ps, latex  
10 (Feb. 14)  Voronoi Diagrams  ps, latex  
11 (Feb. 19)  Voronoi Diagrams and Delaunay Triangulations  ps, latex  
12 (Feb. 21)  Parallel Delaunay Refinement  ps, latex  
13 (Feb. 26)  Parallel Delaunay Refinement  ps, latex  
14 (Feb. 28)  Random Incremental Delaunay  ps, latex  
(March 5)  Spring Break  
(March 7)  Spring Break  
15 (March 12)  Randomized Point Location in Delaunay Construction  ps, latex  
16 (March 14)  Outlier Removal (John Dunagan MIT)  ps, latex  
17 (March 19)  Geometric Perturbation and LiTeng 3D WellShaped Meshing Algorithm  ps, latex  
18 (March 21)  Quadtree: Hierarchical Data Structures  ps, latex  
19 (March 26)  Approximate Voronoi Diagrams  ps, latex  
20 (March 28)  Geometric Sampling  ps, latex  
21 (April 2)  VC Dimensions  ps, latex  
22 (April 4)  Parallel Delaunay Refinement  ps, latex  n  
23 (April 9)  Geometric Approximation and VC Dimensions (Ben Hescott)  ps, latex  
24 (April 11)  Geometric Approiximation and VC Dimensions  ps, latex  
25 (April 16)  Rondomized Divide and Conquer  ps, latex  
26 (April 18)  Bogdan Buricea (I) )  ps, latex  
27 (April 23)  Nenad Dedic (I), Leo Grady  ps, latex  
28 (April 25)  Harrison Hong (I), Shawn Patterson (II), George Bozoric  ps, latex  
29 (April 30)  Robyn Cloud (I), Jason Ruel (II) and Russen Guggemos (III)  ps, latex  
30 (May 2)  Yangui Tao (I), Anna Karpovsky (II) Stephen Crampton (III)  ps, latex  