CS504 Computational Geometry

2013 Spring Semester



Instructor : Sunghee Choi (Office : E3-1 3404, Tel : x3534)

TAs & contact information : Jeongho Son (Office : E3-1 3402, Tel : x7834) "sonjh@kaist.ac.kr"

Class Time : Tue/Thu 14:30~16:00

Location : Classroom 3 (Room #2443)

Textbook :
  • Computational Geometry Algorithms and Applications, 3rd Edition(by Berg, Cheong, Kreveld, Overmas , Springer)
  • David Mount's Lecture note

    Bulletin board : Please check the bulletin board regularly for announcements. You can also post your questions there.

    Office Hour :
  • Mon : 14:00 ~ 15:00
  • Wed : 14:00 ~ 15:00



    Prerequisite : Algorithm, Data structures

    Topics : The preliminary topics for the course include
  • Convex hulls
  • Intersection
  • Low-dimensional linear programming
  • Range Searching - Kd-trees, range trees, fractional cascading
  • Point location
  • Voronoi diagram / Delaunay triangulation
  • Poser diagram / Regular triangulation
  • Arrangements and duality
  • Curve / surface reconstruction
  • Mesh generation
  • Other topics depending on the interests of the class

    Grading :
  • Homework : 20%
  • Midterm : 20%
  • Attendance, presentation and participation : 30%
  • Project : 30%



    Presentation topics :
    ( Ʈ ˴ϴ)

    lectures
  • Doubly-connected edge list (C2.2-5, D23) -> Team 9 (JinYeong Bak, HanUl Jang)
  • Planar convex hull (C4 ~ C5)
  • Polygon triangulation (C3, D7, D22)
  • Interval trees, segment trees (C10)
  • Binary space partitions (C12)
  • Motion planning (C13, D34)
  • Visibility graphs (C15, D33)

    papers
  • Crust & Simple Curve Reconstruction (paper) (paper)
  • Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams (by Guibas and Stolfi) (paper)
  • Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms (by HERBERT EDELSBRUNNER and ERNST PETER MUCKE) (paper)
    Date Member Subject Slide Readings
    4/30 ȣ, ڿ Crust & Simple Curve Reconstruction Slide (paper) (paper)
    5/2 , Abou Quadtrees Slide C11
    5/7 , ȣ Interval trees & Segment trees Slide C10
    5/9 ڼ, ȣ Planar convex hull Slide D3, D4
    5/14 ȫ, , Motion planning Slide C13, D34
    5/16 , Binary space partitions Slide C12
    5/21 , ո Polygon triangulation Slide C3, D7, D22
    5/23 , Ѿ Doubly-connected edge list Slide D3, D4
    5/28 ̳, 赿 Visibility graphs Slide C15, D33





    Homework :

    (Late homeworks will not be considered!)

    Homework box : E3-1 2nd floor, a drawer in front of our classroom
    No. Subject. Problem number Solution. Due date.
    1. Homework #1 Chapter 5 : Exercises 1, 3, 10 Sol ~ 3/12 10:00 AM
    2. Homework #2 Chapter 2 : 10
    Chapter 6 : Exercises 2, 8, 12
    ~ 3/19 10:00 AM
    3. Homework #3 Chapter 9 : Exercise 13, 14, 15, 16 Sol ~ 3/28 10:00 AM
    4. Homework #4 Chapter 4 : Exercise 14, 15
    Chapter 8 : Exercise 1, 2, 7
    Sol ~ 4/9 10:00 AM
    5. Homework #5 Chapter 11 : Exercise 8, 9, 10 ~ 4/18 10:00 AM
    Homework 1~5 presentation
    6. Homework #6 Chapter 10 : Exercise 1, 6, 8
    Chapter 14 : Exercise 11
    ~ 5/16 10:00 AM




    Course progress :

    (Readings : C denotes textbook by 4M, D denotes the lecture note by David Mount)
    Date Subject Download Readings
    3/5 Introduction & Range query Slide C5, D17-18
    3/7 Range search Slide
    3/12 Intersection Slide C2, D6
    Point location Slide C6, D10-11
    3/19 Voronoi diagram Slide C7
    3/21 Delaunay traingulation Slide C9, D14
    3/26 Delaunay traingulation 2 Slide
    3/28 Linear programming Slide C4, D9, D24
    4/2 Arrangements and duality Slide C8, D15-16
    4/4 Polytopes and convex hulls in higher dimensions Slide C11, D5
    4/9 Incremental construction con BRIO Slide Paper
    4/11 Arrangement & Generalized Voronoi Diagrams Slide Paper1(Kenneth E. Hoff III)
    Paper2(Herbert Edelsbrunner)
    4/16 Delaunay-based shape analysis Slide 3D crust
    Ball pivoting
    Power crust
    Power theory
    3D alpha shape
    Union alpha
    alpha shape





    Useful links :

  • Computational Geometry : Algorithms and applications