# Fall, 2010-2011

Office hours: by e-mail   klara@cs.bgu.ac.il

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.

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 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