Fall 2019

Prerequisite:
Algorithms

Announcements:

**Instructor**:

Matya Katz (
matya@cs.bgu.ac.il )

Office hours: Wednesday 14:15-16:00, Alon
building (37), room 212, Tel: (08) 6461628

**Teaching Assistant:**

Stav
Ashur

**Class Time:**

Monday 10-12 (building 34, room 7)

Wednesday 12-14 (building 34, room 5)

**Course Description: **

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

**Additional** textbooks

[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. ~~20~~
23

Some old exams: exam 2005 A;
exam 2005 B;
exam 2007 A;
exam 2007 B;
exam 2009 A;
exam 2009 B;
exam 2016 A

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.

**28.10.19**

Introduction

**30.10.19**

The *convex hull* of a set of points in the plane (gift
wrapping, quickhull, an *O(**n log n)*-time incremental algorithm).

**4.11.19**

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.

**6.11.19**

Sweeping; an output-sensitive
algorithm for line segment intersection.

**11.11.19**

Sweeping with a ray

** **

**13.11.19**

The doubly-connected edge list
representation for planar maps

**18.11.19**

Map overlay; Boolean operations

**20.11.19**

The art gallery theorem,
introduction to guarding problems, introduction to polygon triangulation

**25.11.19**

Partitioning a polygon into
y-monotone pieces

**27.11.19**

Triangulating a y-monotone polygon

**2.12.19, 4.12.19**

Orthogonal range searching, kd-trees, orthogonal range trees and extensions

**9.12.19, 11.12.19**

Segment trees and extensions,
computing the area of (axis-parallel) rectangles in the plane.

**16.12.19, 18.12.19**

Computing the intersection
of half planes; Linear programming in general and a randomized incremental LP
algorithm in the plane.

**23.12.19,
25.12.19**

Planar point
location, trapezoidal map, a randomized
incremental algorithm.

**30.12.19**

Voronoi diagrams

**1.1.20**

Triangulation of a set of points in
the plane; The Delaunay
triangulation.

**6.1.20**

Using the VD and DT, EMST, and more

**8.1.20**

Arrangement of lines and duality

**13.1.20**

A 3/2-approx. algorithm for
Euclidean TSP

**20.1.20**

Realistic
input models

**22.1.20**

Summary

**Last
update: January 22, 2020**