### CSE 546: Computational Geometry, Fall 2016

This course considers data structures and algorithms for spatial data sets, collections of points, lines, planes, polygons and polyhedra that live in 2 or 3 dimensional space. These data structures form the basis for modern work in Computer Graphics, Geographic Information Systems, and, to a lesser extent, Computer Vision and Machine Learning.

##### Time and Room:
on T,Th, 2:30-4:00, Crow 206

##### Office Hours
• [TA] Tue 12:00-13:00 Jolley 421
• [TA] Wed 10:00-11:00 Jolley 421
• [Pless] Wed 11:00-12:00 Jolley 404

##### Textbook:
"Computational Geometry: Algorithms and Applications", Third Edition. This textbook is highly recommended. It is a fantastic book, and relatively inexpensive. The Second or First edition of the textbook is acceptable. I also recommend reading Dave Mount's (wonderful) Lecture Notes. Suggested readings from the book and the lecture notes are highlighted below.

##### Course Discussions:
There is a Piazza page to enable questions and discussions about the course materials. You can sign up with this link: piazza.com/wustl/fall2016/cse546, and the link to the course page is piazza.com/wustl/fall2016/cse546/home.

You are required to be familiar with and follow the academic integrity policy posted on this page, which is essentially copied from the policies of Jeremy Buhler in 441/541.

##### Class Resources
A page with a collections of useful pointers to online resources for this class.

##### Office Hours:
Robert Pless, Wednesday 11-12, Jolley 404
TA office hours will be announced soon.

Voronoi Diagrams and Delauney triangulations are data structures to reason about points and regions in space...

... not to be confused with the abstract, Paul Klee like work of Robert Delaunay.

#### Final Exam Topics

• Duality (Dual of a point, of a line, of a line segment, of a slab. Given a set of points, what is the dual of the set of points? what is the dual of its convex hull? Ham-Sandwhich cuts.
• Zone Theorem and applications of arrangements. Constructing an arrangement. size (number of vertices edges and faces of the arrangement).
• K-D trees. Construction. Rectangle searches (counting and reporting)
• Orthogonal Range Trees and Fractional Cascading.
• Nearest Neighbor Searching with KD trees