Prerequisite:
Algorithms
Announcements:
Exam A (with partial solutions)
Instructor:
Matya Katz ( matya@cs.bgu.ac.il )
Office hours: Wednesday 12:00-14:00, Alon
building (37), room 212, Tel: (08) 6461628
Teaching Assistant:
Rom
Aschner
Office hours:
Class Time:
Monday 10-12 (building 34, room 107)
Wednesday 10-12 (building 34, room 205)
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, Voronoi
diagrams and Delaunay triangulations, polygon triangulation, and linear
programming. We will also present several applications of geometric algorithms
to problems in robotics, computer graphics, GIS (geographic information
systems), communication networks, facility location, manufacturing, 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
submission: November 28, 2011
Assignment no. 2 submission:
December 19, 2011
Assignment no. 3
submission: January 9, 2012
Assignment no. 4
submission: January 25, 2012
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.
Casting; transforming
the problem of determining whether a polyhedron P with n faces is castable into n instances of the problem of finding a
point in the intersection of n half-planes. 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.
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.
31.10.11
Introduction
2.11.11
The convex hull of a set of points in the plane (gift
wrapping, quick hull, incremental O(n log n) alg.)
7.11.11
The diameter and width of a set of points, rotating
calipers
An output sensitive alg for
reporting all intersection points in a set of line segments in the plane;
sweeping with a line
9.11.11 (one hour)
Segment intersection alg
continued
14.11.11
Sweeping with a ray
Implementing the decision problem “do two line segments
intersect?” and a more general discussion on implementation issues and general
position
Handout of homework assignment 1
16.11.11
The doubly-connected edge list representation for
thematic maps
21.11.11
Map overlay
23.11.11
The art gallery theorem; An
introduction to polygon triangulation
28.11.11
Polygon triangulation – partitioning a simple polygon
into y-monotone polygons
30.11.11
Polygon triangulation – triangulating a y-monotone
polygon
Introduction to orthogonal range searching
5.12.11
Orthogonal range searching – kd trees
Handout of homework assignment 2
7.12.11
Orthogonal range searching – range trees;
Segment trees
12.12.11
Segment trees continued; computing the area of the union
of axis-parallel rectangles
14.12.11
Introduction to linear programming (casting), half-plane
intersection
19.12.11
Randomized incremental algorithm for
2-dimensonal LP
21.12.11
LP continued; Point location, trapezoidal
decomposition
26.12.11
Point location continued
Handout of homework assignment 3
28.12.11
Voronoi
diagrams – definitions and properties
2.1.12
Triangulation of a point set; Delaunay
triangulation
4.1.12
Delaunay triangulation continued, EMST, RNG,
GG are contained in DT
9.1.12
Computing the discrepancy
11.1.12
Duality; Arrangement of lines in the plane
16.1.12
Euclidean TSP (a 3/2-approximation algorithm)
18.1.12
Rectilinear piercing and covering
23.1.12
The technique of Frederickson and Johnson
25.1.12
Summary