Prerequisite:
Algorithms
Announcements:
Additional office hours: Thursday, 14.1.10, 15:00-16:00
Instructor:
Matya Katz ( matya@cs.bgu.ac.il )
Office hours: Monday 12:00-14:00, Alon
building (37), room 212, Tel: (08) 6461628
Teaching Assistant:
Rom
Aschner
Office hours:
Class Time:
Monday 10-12 (building 97, room 205)
Wednesday 9-11 (building 90, room 136)
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
[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 roughly 3-5
homework assignments (4% each) and a final exam.
Many of the exercises in the HW assignments below are
taken from [dBCvKO]
HW assignment no. 1
(due November 16)
HW assignment no. 2
(due December 7)
HW assignment no. 3
(due January 4)
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.
19.10.09
Introduction
21.10.09
The convex hull of a set of points in the plane
26.10.09
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
28.10.09
Segment intersection alg
continued; sweeping with a ray
2.11.09
Implementing the decision problem “do two
line segments intersect?” and a more general discussion on implementation
issues and general position.
The doubly-connected edge list representation
for thematic maps. Handout of homework assignment 1
4.11.09
Map overlay
9.11.09
The art gallery theorem; An
introduction to polygon triangulation
11.11.09
Polygon triangulation – partitioning a simple polygon
into y-monotone polygons
16.11.09
Polygon triangulation – triangulating a y-monotone
polygon
18.11.09
Orthogonal range searching – kd trees
23.11.09
Orthogonal range searching – range trees
25.11.09
Segment trees; computing the area of the union of
rectangles
30.11.09
Intro to linear programming (casting), half-plane
intersection
2.12.09
Randomized incremental algorithm for
2-dimensonal linear programming
7.12.09
Point location, trapezoidal decomposition
9.12.09
Point location continued
14.12.09
Voronoi
diagrams – definitions and properties
16.12.09
Voronoi
diagrams continued; triangulation of a point set
21.12.09
Delaunay triangulation, MST is contained in
DT
23.12.09
Euclidean TSP (a 3/2-approximation
algorithm); Duality
28.12.09
Duality and computing the discrepancy
30.12.09
k-piercing of
rectangles
4.1.10
Fatness – definitions, properties,
applications (point enclosure)
6.1.10
DCG day - class canceled
11.1.10
Fatness continued (HSR)