"Questions in discrete geometry typically involve finite sets of points, lines, circles, planes, or other simple geometric o
bjects. For example, one can ask, what is the largest number of regions into which n lines can partition the plane, or what
is the minimum possible number of distinct distances occurring among n points in the plane (the former question is easy, t
he latter one is hard). More complicated objects are investigated too, such as convex polytopes or finite families of convex
sets. The emphasis is on "combinatorial" properties: which of the given objects intersect, or how many points are needed t
o intersect all of them, and so on. Characteristics like angle, distance, curvature, or volume, ubiquitous in other areas o
f geometry, are usually not of primary interest, although they can serve as useful tools.
Many questions in discrete geometry are very natural and worth studying for their own sake. Some of them, such as the struct
ure of 3-dimensional convex polytopes, go back to the Antiquity, and a lot of them are motivated by other areas of mathemat
ics. To a working mathematician or computer scientist, the contemporary discrete geometry offers results and techniques of
great diversity, a useful enhancement of the "bag of tricks" for attacking problems in her or his field."
- from the preface of "Lectures on Discrete Geometry"

Computational geometry is the study of design and analysis of algorithms dealing with geometric objects.
It emerged as a sub-discipline of theoretical computer science from 1970s, and has grown into a recognized
research discipline in computer sciecen and applied mathematics, with a large community of active researchers.
It had developed in several directions and forged links with other application domains such as computer aided design,
robotics, computer graphics, virtual reality, computer vision, bio-informatics, and geographic information system.
We believe that knowledge of computational geometry is important to solve geometric problems in application areas
efficiently. This course, therefore, covers a number of core geometric techniques that have been used to solve problems
from application areas, frome which we expect that, given a geometric problem, students are able to understand the
geometric properties of it and apply a proper algorithmic techniques and data structures.
We start with an introduction to computational geometry and study plane sweep algorithms. Then we cover the fundamental
techniques presented in the following chapters of the textbook.

Data Structures
Algorithm design and analysis

Participation(20%), Homework (20%), Midterm exam. (30%), Final exam. (30%)

Lectures on Discrete Geometry by Jiri Matousek.
Springer Graduate Texts in Mathematics , Vol. 212, 2002, ISBN: 978-0-387-95374-8

Computational Geometry
3rd Edition, 2008
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong

Week 1-2: Convexity, Minkowski Theorem, Convex hulls
Week 3: Line segment intersections
Week 4: Polygon Triangulation
Week 5: Linear Programming
Week 6: Incremental linear programming, unbounded linear programming
Week 7: Orthogonal range searching
Week 8: Midterm exam.
Week 9: Point location
Week 10: Voronoi diagrams
Week 11: Arrangements and Duality
Week 12: Delaunay triangulations
Week 13: Delaunay triangulations
Week 14: Geometric data structures
Week 15: Geometric data structures
Week 16: Final exam.