Matya Katz ( firstname.lastname@example.org )
Office hours: Wednesday 14:15-16:00, Alon building (37), room 212, Tel: (08) 6461628
Monday 10-12 (building 34, room 7)
Wednesday 12-14 (building 34, room 5)
is an introductory course to computational geometry and its applications. We
will present data structures, algorithms and general techniques for solving
fundamental geometric problems, such as convex hull computation, line segment
intersection, orthogonal range searching, construction of Voronoi
diagram and Delaunay triangulation, polygon triangulation, and linear
programming. We will also present several geometric (optimization) algorithms
(both exact and approximate) for problems in robotics, computer graphics, GIS
(geographic information systems), communication networks, facility location,
and VLSI systems design.
The main textbook of the course is
[dBCvKO] Computational Geometry: Algorithms and Applications (3rd edition),
M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Springer-Verlag, 2008.
[DO] Discrete and Computational Geometry, S. Devadoss and J. O’Rourke, Princeton University Press, 2011.
[E] Algorithms in Combinatorial Geometry, H. Edelsbrunner, Springer-Verlag, 1987.
[M] Computational Geometry: An Introduction Through Randomized Algorithms, K. Mulmuley, Prentice Hall, 1994.
[O] Computational Geometry in C (2nd edition), J. O'Rourke, Cambridge University Press, 1998.
[PS] Computational Geometry: An Introduction (2nd edition), F. Preparata and M. Shamos, Springer-Verlag, 1988.
The final grade will be determined by 3-5 homework assignments (4% each) and a final exam.
Some of the exercises in the HW assignments are taken from [dBCvKO].
Assignment no. 1 – due Nov. 25
Assignment no. 2 – due Dec. 16
Assignment no. 3 – due Jan. 6
Assignment no. 4 – due Jan.
The following list of topics is tentative.
The convex hull of a set of points in the plane (applications: computing the diameter and width of a point set).
An output sensitive algorithm for computing the intersection points of a set of line segments; the plane sweep technique.
A representation for planar maps (based on doubly-connected edge lists).
Computing the overlay of two planar maps; Boolean operations on two polygons (union, intersection, and difference).
The art gallery theorem; introduction to polygon triangulation.
An O(n log n) polygon triangulation algorithm (partitioning a polygon into y-monotone pieces; triangulating a y-monotone polygon).
Orthogonal range searching.
Computing the intersection of n half planes in O(n log n) time.
Linear programming - introduction; A randomized incremental algorithm for linear programming in the plane.
Planar point location, vertical decomposition / trapezoidal map, a randomized incremental algorithm.
Nearest site queries, nearest site Voronoi diagram.
Triangulation of a set of points in the plane; the Delaunay triangulation.
Arrangement of lines; duality; computing the discrepancy of a set of points in the unit square.
Segment trees; computing the area of a set of n axis-parallel rectangles in O(n log n) time.
Simplex range searching.
Hidden surface removal: problem definition, image space / object space, the z-buffer algorithm, depth order, the painter's algorithm. Output sensitive hidden surface removal algorithm for horizontal fat triangles.
Introduction to geometric optimization through facility location optimization and wireless networks.
Measures of similarity between curves.
Below you will
find, after each class, a brief summary of the topics covered in class.
This should not be taken as a complete description of the course's content.
The convex hull of a set of points in the plane (gift wrapping, quickhull, an O(n log n)-time incremental algorithm).
An Ω(n log n) lower bound for CH computation, remarks on the CH in higher dimensions. The diameter and width of a set of points in the plane; rotating calipers.
Sweeping; an output-sensitive algorithm for line segment intersection.
Sweeping with a ray; Implementing the decision problem “do two line segments intersect?” and a more general discussion on implementation issues and general position
The doubly-connected edge list representation for planar maps
Map overlay; Boolean operations
The art gallery theorem, introduction to guarding problems, introduction to polygon triangulation
Partitioning a polygon into y-monotone pieces
Triangulating a y-monotone polygon
Orthogonal range searching, kd-trees, orthogonal range trees and extensions
Segment trees and extensions, computing the area of (axis-parallel) rectangles in the plane.
Computing the intersection of half planes; Linear programming in general and a randomized incremental LP algorithm in the plane.
Planar point location, trapezoidal map, a randomized incremental algorithm.
Triangulation of a set of points in the plane; The Delaunay triangulation.
Using the VD and DT, EMST, and more
Arrangement of lines and duality
A 3/2-approx. algorithm for Euclidean TSP
Realistic input models
Last update: January 22, 2020