Instructor

•   Instructor    :  Yusu Wang

            Office Hour:  MW 9:30 - 10:30am
            Room          :  DL487
            Phone          :  2-1309
            Email          :  yusu at cse ...     
            URL            :  www.cse.ohio-state.edu/~yusu
    

Course Description

• Geometric objects appear naturally in many research fields, including computer graphics, robotics, vision, geographic information system (GIS), databses, and sensor networks. It is frequently necessary to process and manipulate such objects. This course introduces basic data structures and fundamental algorithms for geometric objects such as point sets, polygonal lines, and polygonal surfaces. In particular, topics include: various geometric search data structure (including range trees), nearest neighbors, Voronoi diagram, triangulations, point location, geometric duality, linear programming, and arrangements of geometric objects.

 
   

Textbook   /   Grading

• Textbook:

Computational Geometry Algorithms and Applications,  by  de Berg, van Kreveld, Overmars, and Schwarzkopf. 2nd ed., Springer-Verlag, 2000

• Reference books :

Algorithms in Combinatorial Geometry,  by  Edelsbrunner. SpringerVerlag, 1987

Computational Geometry in C,  by  O'Rourke, 2nd ed., Cambridge University Press, 1998.

• Grading policy :

There will be homeworks and a final survey/course project related to geometric algorithms. Grades are based on: Homeworks: 50%, Survey/project: 40%, Others: 10%. Each student need to schedule a 20-min time slot with me whether you do a survey or project.

   

Course Materials

• Schedule:

• Important dates:
• Jan. 3, 2007     : first class
• Jan 31, 2007     : Survey/project topic should be decided.
• Mar. 6-8, 2007   : Survey or Project reports due. Students need to schedule a 20-min time slot with me to present their results whether you do survey or projects.

• Lecture topics:
• Convex Hull
• Duality, halfplane intersection
• Voronoi diagram / Delaunay triangulation (note: this topic is moved forward)
• Linear programming
• Range searching
• Advanced data structures
• Point location, triangulation of polygons
• Arrangements of lines (planes)

• Homeworks :
• Homework 1 is available (pdf). It is due on Feb 7th (Wed) in class.
• Homework 2 is available (pdf). It is due on Feb 21 (Wed) in class.

• Related resources / Reading lists :
• A list of potential projects/survey topics is here (pdf).
• See Erickson's (CG page) for a quite comprehensive directory of computational geometry resources both on and off the Internet.
• See the CG (Open Problem Project) maintained by Demaine, Mitchell and O'Rourke about open problems in CG and related areas.

Announcements: