Computational Geometry - CS 6/76110

Spring 2006

Tuesday, Thursday 12:30 pm - 01:45 pm
MSB 276

Instructor
Office Hours

Email
Telephone

Dr. Feodor Dragan
Room 254 MSB
TR 3:00 - 5:00 PM
and by appointment
dragan at cs dot kent dot edu
(330)672-9058

WWW http://www.cs.kent.edu/~dragan/CS6-76995-CG.html
Outline

Geometric structures are the underlying model of several important applications, including robotics, graphics, CAD/CAM, VLSI layout, and information visualization. The field of computational geometry, which studies algorithms for geometric problems, has attracted increasing research interest in the last years, and is currently one of the most active areas of investigation in theoretical computer science. The course focuses on two-dimensional geometry.

Prerequisites

Data Structures -CS 33001, Design & Analysis of Algorithms - CS 4/56101

Text

F.P. Preparata, M.I. Shamos, Computational Geometry: an introduction, Springer-Verlag, 1993 (5th printing).

Supplementary Text

J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1998 (Second Edition).
G.Di Battista, P. Eades, R. Tamassia, I.G. Tollis, Graph Drawing, Prentice-Hall, 1999.
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 1997.
Some recent journal papers.

Topics will include: This is a graduate level course. We will cover the following topics (the topics and order listed are tentative and subject to change).

Basic Geometric Concepts: points, lines, polygons; subdivisions; arrangements; polytopes; cell complexes.

Geometric Searching: fractional cascading; segment tree; interval tree, range tree; priority search tree.

Point Location: slab method; trapezoid method; chain method; bridged chain method.

Plane-Sweep Algorithms: intersection of segments; intersection of rectangles; trapezoidation.

Convex Hulls: 2-dimensional convex hull; dynamic convex hull; 3-dimensional convex hull.

Proximity: closest pair; furthest pair; Voronoi diagrams; triangulations.

Applications: Computational Geometry methods in Wireless networks

Graph Drawing: planar drawings; straight-line drawings; orthogonal drawings; polyline drawings.

Visibility Graphs: shortest paths; computing visibility graphs.

Course Requirements

Homework	-	-	-	40%
Midterm Exam	TBA	March ??, 2006	12:30 - 01:45 p.m.	30%
Final Exam	Tuesday	May 9, 2006	12:45 - 03:00 p.m.	30%

Milestone for successful completion of the course

Attend the classes regularly,
Perform the homework thoroughly and independently,
Read the book carefully and several times.

Students with Disabilities

University policy 3342-3-18 requires that students with disabilities be provided reasonable accommodations to ensure their equal access to course content. If you have a documented disability and require accommodations, please contact the instructor at the beginning of the semester to make arrangements for necessary classroom adjustments. Please note, you must first verify your eligibility for these through Student Disability Services (contact 330-672-3391 or visit www.kent.edu/sds for more information on registration procedures).

F. F. Dragan
dragan at cs dot kent dot edu
Springl 2006