Prerequisite:
Algorithms
Announcements:
Instructor:
Matya Katz ( matya@cs.bgu.ac.il )
Office hours: Sunday 12:00-14:00, Alon
building (37), room 212, Tel: (08) 6461628
Teaching Assistant:
Omrit
Filtser
Class Time:
Tuesday 14-16 (building 34, room 5)
Thursday 12-14 (building 34, room 5)
Course Description:
This is an introductory course to
computational geometry and its applications. We will present data structures,
algorithms and general techniques for solving geometric problems, such as
convex hull computation, line segment intersection, orthogonal range searching,
construction of Voronoi diagram and Delaunay triangulation,
polygon triangulation, and linear programming. We will also present several
geometric (optimization) algorithms to problems in robotics, computer graphics,
GIS (geographic information systems), communication networks, facility
location, and VLSI systems design.
The main textbook of the course is
[dBCvKO] Computational Geometry: Algorithms and Applications (3rd edition),
M. de Berg, O. Cheong, M. van Kreveld and M. Overmars,
Springer-Verlag, 2008.
Additional textbooks
[DO] Discrete and Computational
Geometry, S. Devadoss
and J. O’Rourke, Princeton University Press, 2011.
[E]
Algorithms in Combinatorial Geometry, H. Edelsbrunner,
Springer-Verlag, 1987.
[M]
Computational Geometry: An Introduction Through
Randomized Algorithms, K. Mulmuley, Prentice
Hall, 1994.
[O]
Computational Geometry in C (2nd
edition), J. O'Rourke, Cambridge University Press, 1998.
[PS]
Computational Geometry: An Introduction (2nd edition), F. Preparata and M. Shamos,
Springer-Verlag, 1988.
The final grade will be determined by 3-5 homework
assignments (4% each) and a final exam.
Many of the exercises in the HW assignments are taken
from [dBCvKO].
Assignment no. 1 (due November
27, 2016)
Assignment no. 2 (due December
20, 2016)
Assignment no. 3 (due January
10, 2017)
Assignment no. 4 (due January
26, 2017)
Some old exams: exam 2005 A;
exam 2005 B;
exam 2007 A;
exam 2007 B;
exam 2009 A;
exam 2009 B
The following list of topics is tentative.
The convex hull of
a set of points in the plane (applications: computing the diameter and width of
a point set).
An output sensitive
algorithm for computing the intersection points formed by a set of line
segments; the plane sweep technique.
A representation for planar
maps (based on doubly-connected edge lists).
Computing the overlay
of two planar maps; boolean
operations on two polygons (union, intersection, and difference).
The art gallery theorem;
introduction to polygon triangulation.
An O(n
log n) polygon triangulation algorithm (partitioning a polygon into y-monotone
pieces; triangulating a y-monotone polygon).
Orthogonal range
searching.
Computing the intersection
of n half planes in O(n log n) time.
Linear programming -
introduction; A randomized incremental algorithm for linear programming in the
plane.
Planar point location,
vertical decomposition / trapezoidal map, a randomized incremental algorithm.
Nearest site queries,
nearest site Voronoi diagram.
Triangulation of a set of
points in the plane; the Delaunay triangulation.
Arrangement of
lines; duality; computing the discrepancy of a set of points in
the unit square.
Segment trees;
computing the area of a set of n axis-parallel rectangles in O(n
log n) time.
Hidden surface removal:
problem definition, image space / object space, the z-buffer algorithm, depth
order, the painter's algorithm. Output sensitive hidden surface
removal algorithm for horizontal fat triangles.
Introduction to geometric
optimization through facility location optimization and wireless
networks.
Measures of similarity
between curves.
Below you will find, after each class, a brief summary of
the topics covered in class.
This should not be taken as a complete description of the course's content.
1.11.16
Introduction
3.11.16
The convex hull of a set of points in the plane (gift
wrapping, quickhull, an O(n log n)-time incremental
algorithm and a divide and conquer algorithm
8.11.16
The
diameter of a set of points; rotating calipers. The width of a set of points
(homework)
10.11.16
Sweeping;
an output sensitive algorithm for line segment intersection
15.11.16
Generalizations
of the line segment intersection algorithm, sweeping with a ray
17.11.16
Implementing
the decision problem “do two line segments intersect?” and a more general
discussion on implementation issues and general position
22.11.16
Map
overlay (sketch); Boolean operations
24.11.16
Introduction
to guarding problems
Partitioning
a polygon into y-monotone pieces
1.12.16
Orthogonal
range searching, kd-tree
6.12.16
Orthogonal range tree
8.12.16
Segment tree
13.12.16
Computing the area of the union of axis-aligned
rectangles; Intro to linear programming
15.12.16
Computing the intersection of n half planes in O(n log n) time.
Linear programming - A randomized
incremental algorithm for LP in the plane
20.12.16
Planar point location, vertical decomposition, a
randomized incremental algorithm
22.12.16
Planar point location – continued
27.12.16
Voronoi
diagram
29.12.16
Triangulation of a point set, Delaunay triangulation
3.1.17
Delaunay triangulation - continued
5.1.17
Duality, arrangements of lines
10.1.17
TSP and variants, Christofides approx.
algorithm
12.1.17
Intro to covering and piercing problems
17.1.17, 19.1.17
Fatness – definitions and algorithms for point enclosure
and hidden surface removal