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

    1. A visual implementation of Fortune's Voronoi algorithm. Click on Fortune alg.
    2. 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
    3. See applet of Delaunay and Voronoi diagrams on APPLET
    4. Duality in : http://www.cs.unc.edu/~mantler/research/dual/