CS 591 T1  

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.

    • Ruppert's paper.

    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

    solution

    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