# COMPUTATIONAL GEOMETRY and SCIENTIFIC COMPUTING

COURSE INFO
 Professor: Shang-Hua Teng Lecture Time: 11:00-12: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: Scribe notes: Each lecture will have an assigned "scribe", whose job is to take notes for later distribution to the class. The notes should not be a simple copy of what is written on the white/blackboard. It has to be written to show that the scribe understands the material. I recommend to use the latex package that Professor Jeff Erickson has prepared to help scribing. The scribed notes should be return to me in a week and I will post the latex as well as the ps-files. Homework Problems: Throughout the semester, I will assign all together 4 or 5 problems (not problem sets) to help enhance the understanding of the class materials. Class Projects: There will be two projects: The first one is a programming project. The second one (the major one) will be either a programming project or a 15-page survey document. Presentation: Everyone will will be asked to make a 25 minutes presentation in the class about his/her final project.

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 c-median 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 0--5, 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 divide-and-conquer 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 NP-hard. 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) Miller-Teng-Thurston-Vavasis 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 Li-Teng 3D Well-Shaped 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

steng@cs.bu.edu