Computational Geometry
Fall,
2010-2011
Prof.
Klara kedem
Office hours: by e-mail klara@cs.bgu.ac.il
Announcement
10.1.2011 Your final grades moed alef are on my door
Announcement
10.11.10 : All graduate students (MSc,
PhD) can take one exam in moed A or B
Assignment 5 is now online
previous assignments 1, 2,
3 , 4
And solutions sol-1, sol-2, sol-3, sol-4, sol-5 was wrong! so I put sol-4 again!!
Announcement
23.11.10 : îåòã à 9.1.11 áúàøéê åîåòã á
16.2.11 áúàøéê
Course
prerequisites: Algorithms
Level:
Advanced, BA, BSc, and higher degrees
Course
Description
Computational Geometry is the
study of algorithms for solving geometric problems. The core of the field
consists of a set of techniques for the design and analysis of such
algorithms. It has deep connections to classical mathematics, theoretical
computer science, and practical applications, that arise, e.g., in areas like
statistics, computer vision, graphics, engineering, and more. The problems
dealt with are typically posed as queries on sets of geometric objects, such
as points, segments and polygons in the plane, or points, segments and polytopes in higher dimensions.
Tentative Scope of
the Course
In this course we will cover lines' and polygons' intersection
problems, convex hulls, point location and range queries, proximity problems
(Voronoi diagrams and Delaunay triangulations) and
geometric optimization. We will study a variety of techniques, such as the sweepline paradigm, divide and conquer, and randomized
algorithms. We will learn some geometric data structures. We will deal with
applications of computational geometry to image matching, collision free
robot's motion planning, and more.
Homework and grading
(tentative):
There will be up to 6 written homework assignments -
for a total of 20 grade points.
Textbook:
The course’ textbook is
``Computational Geometry: Algorithms and Applications'', by M. de Berg, M.
van Kreveld,M. Overmars and O. Schwarzkopf, Springer-Verlag,
3rd edition 2008, also in paperback.
There
are 5 copies of the textbook in the Arrane library,
search for “author” “de Berg and Overmars” – the
book does not show up in search of “title” “computational geometry : algorithms
and applications”
Other books that cover
some of the topics:
· [CLR]
Cormen, Leiserson and Rivest, ``Introduction to Algorithms'', MIT Press, 1991.
· [Me]
K. Mehlhorn, ``Data Structures and Algorithms
3:Multi-dimensional Searching and Computational
geometry'', Springer-Verlag, 1984.
· [OR]
J. O'Rourke, ``Computational Geometry in C'', Springer-Verlag,
1994.
·
[PS] F. Preparata and M.I. Shamos,
``Computational Geometry'', Springer-Verlag, 1988.
|
Schedule + book chapters
from previous years
Notice: This is a
tentative schedule which might get updated.
|
Topics
|
Date
|
Chapter numbers are from the course’ textbook [DKOS] above
|
|
Introduction. Motivation and an example: a convex
hull.
On the idea of general position and the issue of
robustness. Application domains.
|
11/10/10
|
beginning of the textbook and Chapter 1.1, 1.2,
1.3, & [PS]
|
|
The sign test and its usage in geometric problems.
Logarithmic time algorithms for queries on convex polygons.
Segment intersection and the sweepline
paradigm.
|
13/10/10
|
Chapter 2.
|
|
Detecting/reporting all the intersections among n line
segments.
The doubly connected edge list - a data structure for
planar graphs.
|
18/10/10
|
[CLR] pp. 886-891
Chapters 2.1, 2.2
|
|
Planar subdivisions. Proof of
complexity of a planar graph.
Computing the overlay of two subdivisions.
|
20/10/10
|
Chapter 2.3
|
|
Half-plane intersections and linear programming in small
dimensions. Backward analysis
|
25/10/10
|
Chapters 4.2-4.5
|
|
Orthogonal range searching, range trees,
kd trees. Quad trees
Fractional
cascading.
|
27/10/10
3/11/10
5/11/10
|
Chapters
5.1- 5.3
Chapter 5.6
PPT on Frac_Casc
|
|
Point location. Vertical decomposition, proof of O(log(n)
expected search time, by backward analysis
|
8/11/10
10/11/10
|
6.1-6.2
|
|
Voronoi diagrams,
practical examples definitions, properties, the empty circle of L1, L2, L∞
Fortune's
algorithm.
|
15/11/10
17/11/10
|
Chapters 7.1-7.3
[OR]
|
|
The minimum Hausdorff
distance. Rasterized HD following the theoretical algorithm,
GPU application, and partial HD including outlier
|
22/11/10
24/11/10
29/11/10
|
Sections 1+2 of the attached paper1 and paper2
|
|
Delaunay triangulation
|
29/11/10
1/12/10
|
Chapter 9.1-9.2
|
|
Arrangements and duality,
the zone thm
|
1/12/10
6/12/10
|
Chapter 8.2-8.3
|
|
end of proof, examples, levels
|
8/12/10
|
|
|
The geometry of axis parallel rectangles
Segment
trees, Klee's measure
|
8/12/10
13/12/10
|
10.1,10.3
[Me] pp. 212-218.
|
|
interval
trees
|
15/12/10
|
10.1,10.3
|
|
Minkowski sums and Robot
motion planning
|
20/12/10
22/12/10
|
Chapter 13.1-13.4
|
|
Convex hull of points in 3D
|
22/12/10
27/12/10
|
Chapter 11
|
|
Suggested – a class training exam
|
29/12/10
|
|
|
Suggested – a class moed alef exam
|
5/1/11
|
|
|
Links
- A visual implementation of Fortune's Voronoi algorithm. Click on Fortune
alg.
- VoroGlide
allows to watch how the structure of the Voronoi diagram/Delaunay triangulation/convex hull
changes as individual points are dragged across the plane. Click on VoroGlide
- See applet of Delaunay and Voronoi diagrams on APPLET
- Duality in : http://www.cs.unc.edu/~mantler/research/dual/
|