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:
Wednesday 12-14 (building 90, room 139)
Thursday 10-12 (building 90, room 123)
Course Description:
This
is an introductory course to computational geometry and its applications. We
will present data structures, algorithms and general techniques for solving
fundamental 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
(both exact and approximate) for 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.
Some of the exercises in the HW assignments are taken
from [dBCvKO].
Assignment 1 (due Nov. 14,
2018)
Assignment 2 (due Dec. 6 9, 2018)
Assignment 3 (due Jan. 3 6, 2019)
Assignment 4 (due Jan. 10,
13, 2019)
Some old exams: exam 2005 A;
exam 2005 B;
exam 2007 A;
exam 2007 B;
exam 2009 A;
exam 2009 B;
exam 2016 A
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 of 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.
Simplex range
searching.
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.
17.10.18
Introduction
18.10.18
The convex
hull of a set
of points in the plane (gift wrapping, quickhull, an O(n log n)-time
incremental algorithm)
24.10.18
A
divide and conquer algorithm
for computing the CH in the plane. Remarks concerning the CH in higher
dimensions. The diameter and width of a set of points in the plane; rotating
calipers.
25.10.18
Sweeping;
an output-sensitive algorithm for line segment intersection.
31.10.18
Sweeping with a ray
1.11.18
The doubly-connected edge list representation (DCEL) for planar maps; Map overlay (problem definition and statement of result only); Boolean operations on polygons
7.11.18
The
art gallery theorem, introduction to guarding
8.11.18
Partitioning a polygon into y-monotone pieces
14.11.18
Triangulating a y-monotone polygon
15.11.18
Orthogonal range searching – Inro,
Kd-trees
21.11.18
Kd-tree continued,
Orthogonal Range Trees
22.11.18
Segment trees
28.11.18
Computing the area of a set of n axis-parallel rectangles
in O(n log n) time
29.11.18
Computing the intersection of n half planes in O(n log n) time. Inro to linear
programming
5.12.18
Linear programming - A randomized incremental algorithm
for linear programming in the plane
6.12.18
Planar point location, vertical decomposition /
trapezoidal map, a randomized incremental algorithm
12.12.18
Point location - continued. Intro to Voronoi
diagrams
13.12.18
Voronoi diagrams – definitions,
properties, and extensions
19.12.18
Measures of similarity between curves, the Fréchet distance, etc. (Omrit Filtser)
20.12.18
Triangulation of a set of points in the plane; the Delaunay
triangulation.
26.12.18
Arrangement of lines; duality; k-set/k-level.
27.12.18
Optimization: A 3/2-approximation algorithm for TSP in
the plane.
2.1.19
Optimization: Intro to piercing and covering.
3.1.19
Optimization: Covering continued; radio networks and the
power assignment problem.
9.1.19
Optimization: radio networks continued.
10.1.19
Summary
Last
update: January 9, 2019