Computational Geometry

Fall, 2010-2011

Prof. Klara kedem


Office hours: by e-mail


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.


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.



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.




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.


Chapter 2.

Detecting/reporting all the intersections among n line segments.

The doubly connected edge list - a data structure for planar graphs.



[CLR] pp. 886-891

Chapters 2.1, 2.2

Planar subdivisions. Proof of complexity of a planar graph.

Computing the overlay of two subdivisions.


Chapter 2.3

Half-plane intersections and linear programming in small dimensions. Backward analysis



Chapters 4.2-4.5

Orthogonal range searching, range trees,

kd trees. Quad trees
Fractional cascading.



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



Voronoi diagrams, practical examples definitions, properties, the empty circle of L1, L2, L

Fortune's algorithm.




Chapters 7.1-7.3


The minimum Hausdorff distance.  Rasterized HD following the theoretical algorithm, GPU application, and partial HD including outlier



Sections 1+2 of the attached paper1 and paper2

Delaunay triangulation


Chapter 9.1-9.2

Arrangements and duality,
the zone thm


Chapter 8.2-8.3

end of proof, examples, levels


The geometry of axis parallel rectangles
 Segment trees, Klee's measure


[Me] pp. 212-218.

interval trees



Minkowski sums and Robot motion planning



Chapter 13.1-13.4

Convex hull of points in 3D


Chapter 11

Suggested a class training exam


Suggested a class moed alef exam





    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 :