Computational Geometry
Fall,
20102011
Prof.
Klara kedem
Office hours: by email 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 sol1, sol2, sol3, sol4, sol5 was wrong! so I put sol4 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, SpringerVerlag,
3^{rd} 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:Multidimensional Searching and Computational
geometry'', SpringerVerlag, 1984.
· [OR]
J. O'Rourke, ``Computational Geometry in C'', SpringerVerlag,
1994.
·
[PS] F. Preparata and M.I. Shamos,
``Computational Geometry'', SpringerVerlag, 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. 886891
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

Halfplane intersections and linear programming in small
dimensions. Backward analysis

25/10/10

Chapters 4.24.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.16.2

Voronoi diagrams,
practical examples definitions, properties, the empty circle of L_{1}, L_{2}, L_{∞}
Fortune's
algorithm.

15/11/10
17/11/10

Chapters 7.17.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.19.2

Arrangements and duality,
the zone thm

1/12/10
6/12/10

Chapter 8.28.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. 212218.

interval
trees

15/12/10

10.1,10.3

Minkowski sums and Robot
motion planning

20/12/10
22/12/10

Chapter 13.113.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/
