Fall 2015

Prerequisite:
Algorithms

Announcements:

Assignment no. 2 (see below) is
due December 29, 2015.

Assignment no. 1 (see below) is
due December 1, 2015.

**Instructor**:

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

Office hours: Sunday 12:00-14:00, Alon
building (37), room 212, Tel: (08) 6461628

**Teaching Assistant:**

???

Office hours:

**Class Time:**

Monday 16-18 (building 90, room 125)

Tuesday 16-18 (building 90, room 239)

**Course Description: **

This
is an introductory course to computational geometry and its applications. We
will present data structures, algorithms and general techniques for solving
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 applications of geometric
(optimization) algorithms to problems in robotics, computer graphics, GIS
(geographic information systems), communication networks, facility location,
manufacturing, 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.

Many of the exercises in the HW assignments are taken
from [dBCvKO].

Assignment no. 1 (due December
1, 2015)

Assignment no. 2 (due December
29, 2015)

Assignment no. 3 (due January
19, 2016)

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

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 formed by 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*.

Casting; transforming the problem
of determining whether a polyhedron P with n faces is castable
into n instances of the problem of finding a point in the intersection of
n half-planes. 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.

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

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.

**26.10.15**

Introduction

**27.10.15**

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

**2.11.15**

The diameter and width of a set of points; rotating calipers

**3.11.15**

Sweeping; an output sensitive algorithm for line segment
intersection

**9.11.15**

Sweeping with a ray

Implementing the decision problem “do two line segments
intersect?” and a more general discussion on implementation issues and general
position

** **

**16.11.11**

The doubly-connected edge list representation for planar maps

**21.11.11**

Map overlay; Boolean operations

**10.11.15**

The art gallery theorem, introduction to guarding
problems

**16.11.15**

Introduction to polygon triangulation

**17.11.15**

Partitioning a polygon into y-monotone pieces

**23.11.15**

triangulating a
y-monotone polygon

**24.11.15**

Orthogonal range searching