CMPT 813: Computational Geometry (Fall 2011)

 

 

 

Instructor: Binay Bhattacharya Office: TASC I 8017, e-mail: binay@cs.sfu.ca, phone: (778)782-3133



Messages/Hand-outs


  • 01/10/2011: Homework 3 is assigned in the class. The due date is Oct 11, 2011.
  • 20/09/2011: Homework 2 is assigned. The due date is Sept 29, 2011.
  • 15/09/2011: Homework 1 is assigned. The due date is Sept 20, 2011.

    Course outline

    Lectures

    Tuesday - 1:30-2:20; Thursday - 12:30 - 2:20

     


    Week

    Date

    Topics

    Reference

    1
    06/09 Course Organization
    08/09 Fixed radius neighbor search problem Mount's lecture notes (Lecture 2)

    2

    13/09

    Convex Hulls Notes

    		 Mount's lecture notes (Lectures 3 and 4; Text: Chapter 1)
    15/09 Convex Hulls

    3

    20/09

    Solving problems using rotating calipers

    		 Rotating caliper paper
    22/09 Finishing Convex hull

    4

    27/09

    Convex Hulls Finished

    		 Mount's lecture notes (Lectures 3 and 4; Text: Chapte r 1)
    29/09 Segment Intersection Mount's lecture notes (Lecture 5; Text: Chapter 2)

    5

    04/10

    Balaban's Algorithm

    		 Balaban's paper
    06/10 Polygon Triangulations Mount's lecture notes (Lecture 6 and 7; Text: Chapter 3)

    6

    11/10

    Polygon Triangulations (contd)
    13/10 DCEL, Randomized Trapezoidation DCEL Notes
    Trapezoidation Notes

    7

    18/10

    Trapezoidation (contd)
    20/10 DCEL, Randomized Trapezoidation

    8

    25/10

    Range Search

    		 Range Search Notes
    Range Queries Notes
    27/10 DCEL, Range Search (contd)

    9

    02/11

    Voronoi Diagrams
    04/11 Voronoi Diagram (contd.) Voronoi Diagram Notes.1
    VD Notes.2
    VD Notes.2

    10

    09/11

    Extensions of Voronoi Diagrams

    		 Extensions of VD
    11/11 Line Arrangement and Duality Arrangements

    11

    16/11

    Line Arrangement and Duality
    18/11 Problem Solving Sessions Problem set used by Prof. Mount
    Practice Problems used by Prof.Sacristan

     

    Prerequisites

    • Experiences in algorithmic design: proof of correctness; asymptotics; amortized complexity; probability theory; divide-and-conquer; dynamic programming; data structures - balanced trees, heaps.

    Textbook

    • Computational geometry: algorithms and applications by de Berg, van Kreveld, Overmars, Schwarzkopf

    • Lecture notes of Prof. David Mount

      LectureNotes

    Other useful resources

    Reference books

    • Computational geometry in C by O'Rourke
    • Computational geometry: an introduction" by Preparata and Shamos
    • Handbook of discrete and computational geometry by Goodman and O'Rourke
    • Computational geometry: an introduction through randomized algorithms" by Mulmuley

    Web Pages

    Finding Papers

    Coursework


  • 01/10/2010: Homework 2 hw2.pdf