# Computational Geometry (CS504)

## Spring Semester 2006

Computational geometry studies algorithms and data structures for processing and storing geometric objects. This courses discusses algorithm design techniques such as plane sweep and geometric divide & conquer; data structures such as point location structures, interval trees, segment trees, and BSP trees; and geometric structures such as arrangements, triangulations, Voronoi diagrams, and Delaunay triangulations.

Undergraduate students: I have deliberately asked for the course number to be changed from CS604 to CS504 so that undergraduate students can also attend this course. Computational Geometry is well suited for undergraduate students with an interest in algorithms. If you liked Algorithms (CS300), you'll probably also like Computational Geometry!

#### Lecturer:

Otfried Cheong. Office: E3-1 3434, Phone: 3542.

#### Prerequisite

A graduate or undergraduate algorithms course (such as CS300 or CS500, or an undergraduate algorithms course you took before coming to KAIST).

#### Lectures

The class meets Mondays and Wednesdays from 13:00 to 14:30 in classroom 4 (room 2245) in the EECS building (E3-1). Lectures are given in English.

• Homework (30%), Midterm (30%), Project (30%), Participation (10%). (There will be no final exam.)

#### Literature

We will be using the book Computational Geometry: Algorithms and Applications (second edition), by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, Springer-Verlag 2004.

Another good reference for the course are David Mount's lecture notes.

#### Tentative syllabus

The 16 weeks of the semester may be filled roughly like this:

1. Introduction
2. Line Segment Intersection
3. Polygon Triangulation
4. Linear Programming
5. Orthogonal Range Searching
6. Point Location
7. Voronoi Diagrams
8. Midterm exam
9. Arrangements
10. Interval & Segment Trees
11. Convex Hulls
12. Delaunay Triangulations
13. Robot motion planning
14. Mesh Generation
15. Simplex Range Searching

#### Course progress

The material covered in the lectures so far (Chapter 1 of the textbook is available on-line at the book website):

 03-06 Introduction, Planar convex hulls 1.3, 1.2 (up to page 5) 03-13 Planar convex hulls, fixed-radius near neighbors 1.2, David Mount's notes 03-15 Fixed-radius near neighbors, line segment intersection pg. 20-22 03-20 Line segment intersection 2.1 03-22 Planar maps, DCEL representation 2.2 03-27 Polygon triangulations 3.1 03-29 Triangulating a simple polygon 3.2, 3.3 04-03 Intersection of half-spaces, duality 4.1, 4.2, 8.2 04-05 Lower envelopes and upper convex hulls 11.4 04-10 Incremental linear programming 4.3 04-12 Randomized incremental LP 4.4 04-17 Randomized incremental LP 4.4 04-19 No class, midterm exam 19:00-22:00 04-24 No class (midterm week) 04-26 Midterm review, Trapezoidal map 6.1 05-01 Cancelled (instructor was sick) 05-03 Point location 6.2 05-08 Expected query time, degeneracies and symbolic perturbation 6.2, 6.3 05-10 Voronoi Diagrams 7.1 05-12 Delaunay triangulations 9.1, 9.2 05-15 Computing the Delaunay triangulation 9.3 05-17 Range trees, kd-trees 5.1, 5.2, 5.3 05-22 Interval trees, segment trees 10.1, 10.3 05-24 Minkowski sums 13.3 05-29 Minkowski sums and robot motion planning 13.2, 13.4 05-31 No class (election day) 06-05 No class (conference) 06-07 No class (conference) 06-12 Project presentations 06-14 Project presentations

#### Midterm exam

The midterm exam will be held on April 19, from 19:00 to 22:00 in the evening, in our usual class room (classroom 4, room 2245). The exam will be open book - you can bring our text book and the notes you have taken in the course. No other books or printouts are allowed.

#### Homework

There will be a few (3 to 5) homework assignments in this course. You will have one or two weeks to complete an assignment. Homeworks can be turned in in English or Korean.

• Homework 1 (due March 24, 15:00)
• Homework 2: Exercises 2.11, 3.1, 3.3, 3.11 (due April 7, 15:00)
• Homework 3: Exercises 4.4, 4.10, 4.14. Bonus: 4.6 (due April 19, 15:00)
• Homework 4: Exercises 8.6, 8.7, 8.9, 6.5, 6.6, 6.7 (due May 15, 15:00)

#### Project

In the second half of the course, students will form teams of two or three students ("groups" of one student can be permitted with good reason, you need my approval), and select a topic for the final project. The project can be one of the following:

• An implementation or experimental study of a geometric algorithm. You can pick any algorithm from the book that is interesting enough, or find a problem and an algorithm for it from the literature. You should implement and properly test the algorithm. I would also be interested in animated algorithms, that can be used to explain the algorithm (the next time I teach the course :-). You could also package your algorithm as an ipelet. You need to submit code and a short document describing your implementation.
• A survey paper of at least 10 pages in English on an interesting topics. Here are some suggestions:
1. We used DCEL to represent planar maps. There are other data structures such as the quad-edge and winged-edge data structure. Such data structure are interesting because they are also used to store meshes (representations of surfaces in 3D). Describe the different data structures, their advantages and disadvantages.
2. Abstract Voronoi diagrams: What are they, how are they used?
3. Learn enough about oriented projective geometry to explain what it is and how duality works there. Explain why convex hulls and half-plane intersections are perfectly dual in oriented projective geometry.
4. Point set surfaces: What are they, how are they used?
5. Spanners: What are they, how are they used?
You are free to suggest another topic.
• Here is a nice list of 16 geometric problems (made by Bettina Speckmann for her course--you should ignore all text before the first problem). Solve one of these problems, and write a paper of at least 10 pages about your solution.

For all these problems solutions can be found in the literature or the internet. You are not supposed to search for such a solution, but to solve the problem yourself using the knowledge you've gained in the course (and reading the book).

The deadline for the project is June 12 at the beginning of the class. We will have presentations for all projects during the class hours on June 12 and June 14.

Project groups so far:

• Mi-kyung Kang, Minkoo Seo, and Sawhney Mrinalini. Implementation of Line Intersection Algorithm.
• Jim Pryor and Adrian Bauer. Smallest enclosing box for a simple polygon.
• Mira Lee. NP-hardness of minimum dilation tree.
• Chang-Yul Choi. Largest axially-symmetric subset of a convex polygon.
• Hyo-Sil Kim. Surface reconstruction using Voronoi diagram.
• Jihye Kim and Yong-joon Lee. Clustering problem.
• Jung Gun Lim and Gyu-Hwan Dong. River flows on triangulated irregular terrains.
• Jeong Hyeon Park. Survey on Abstract Voronoi Diagrams.
• Hyun Sun Ko and Jang-hwan Kim. Voronoi diagram of spheres.
• Dohyung Kim, Kyungmin Min, and Hyungjin Yang. Maximal and dominating points.
• Thai Quang Tung. Point location in Triangulations.
• Jin-Woo Koh. Visibility in terrains.
• Youngki Lee and Taiwoo Park. Efficient processing of continuous range queries.

#### Bulletin board

Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

Otfried Cheong