**Lecture 2: TRIANGULATIONS and ART GALLERY THEOREMS**
We discussed the "Art Gallery" problem. This is discussed in Chapter 1
of the textbook. Basic idea: triangulate the polygon, show that the
planar triangulation is 3 colorable (use the dual tree for this), and
finally put guards at all vertices that have color RED (least used color).

**Lecture 3: MORE ABOUT TRIANGULATIONS**
Basic stuff about triangulations. Why do triangulations exist? How many
triangles does a polygon get divided into? Check for intersection
of two line segments. Area of a triangle etc. How can we triangulate
in O(n^4) time, how can we improve theis to O(n^3) and finally O(n^2).
Chapter 1 of the book.

**Lecture 4: FASTER TRIANGULATION ALGORITHMS**
Triangulations: How to triangulate monotone polygons. How to break
a polygon into monotone polygons. Trapezoidal decompositions etc.
Chapter 2 of the book. Read Chap 6.2 from Preparata, its correct!
The text seems to have some problems. (Trapezoidalization is described
OK in the text. The problems are with the cusp lemma and the pseudo-code.)

**Lecture 5: TRAPEZOIDAL DECOMPOSITION**
We covered the sweep-line algorithm for the trapezoidalization of
(possibly intersecting) line segments in the plane. The algorithm itself
is similar to the sweep-line algorithm given in the text for trapezoidalization
of simple polygons (except for edge crossings). To handle edge-crossings we
observe that intersection points are generated by adjacent line segments in
the horizon. Each time we create a new adjacency in the horizon we check for
possible intersection of the segments, and add the intersection point to the
event queue if it has not been added already. The running time of this
algorithm is O((n+k) logn), where k is the number of intersection points.
We also covered some basic facts about randomized algorithms
(from Mulmuley's book) about Quicksort and backward analysis.
I will give a handout on this stuff in the next lecture.

**Lecture 6: RANDOMIZED (INCREMENTAL) TRAPEZOIDALIZATION**
We will study the randomized incremental construction due to Mulmuley
that runs in O(nlogn +k) expected time (recall that k is the number of
intersection points). The analysis itself is a little tricky, but
can be done using the idea of backward analysis. We will probably cover
other randomized algorithms later in the semester, which will also be
analysed using this technique. (This was taken from Mulmuley's book.)

**Lecture 7: CONVEX HULLS**
Read Chapter 3 of the text.
We covered basic definitions about convex hulls, and simple algorithms
for computing convex hulls. These include Jarvis' march, Graham's scan and
the divide and conquer algorithm. There are several other slower algorithms
that are less interesting. Graham's scan is described in gory detail in
the text, and ithe description is worth reading; especially if you
have doubts about the implementability of the algorithms discussed
in class! The divide and conquer algorithm is quite simple, the main
trick is in computing the upper and lower supporting lines. Jarvis' march
takes time O(nh) where h is the size of the hull. The others take O(n log n)
time.

**Lecture 8: CONVEX HULLS**
More on Convex Hulls. Divide and Conquer algorithms, Kirkpatrick and
Seidel's ultimate convex hull algorithm. This takes O(n log h) time.
The main idea is to do a divide and conquer scheme, where we compute
a supporting line (bridge) even before recursing on the sub-problems.
Once we have the bridge, we can eliminate many points from consideration,
in particular, the ones below the bridge. Computing the bridge is tricky,
but can be done in O(n) time using the ``prune and search'' technique.
I will make a handout for this lecture.
**Handout**

**Lecture 9: CONVEX HULLS **
We discussed convex hull algorithms for 3D briefly. Most of these are
fairly complicated to implement (at least getting below O(n^2)).
We discussed a simple randomized incremental construction that works
in expected time O(n logn). The algorithm is not complex, and can be
implemented relatively easily.
**Handout**

**Lecture 10: VORONOI DIAGRAMS - SWEEP LINE **
Start on Voronoi Diagrams, Fortune's sweep line algorithm. We studied
the key ideas behind Fortune sweep line algorithm. The original paper
appeared in Algorithmica (1987), but the description we studied is
a nicer one due to Guibas and Stolfi. Arguing the correctness is
involved and complex. The algorithm has some subtle details that
we glossed over. I will talk about some of these next time. I have placed
a **handout** in the program library for this lecture.

**Lecture 11: FORTUNE'S SWEEP LINE METHOD AND DIVIDE AND CONQUER**
More on Voronoi Diagrams (site events, circle events etc).
Divide and Conquer algorithm.
The best description of this algorithm is given in Preparata and Shamos.

**Lecture 12: VORONOI PROPERTIES/DELAUNAY TRIANGULATIONS**
Voronoi diagram properties and review for exam.

**Lecture 13: **
**REMINDER: Midterm on March 11. Skinner 0200 11:00-12:15. **

**Lecture 14: APPLICATIONS OF VORONOI DIAGRAMS**
We spent some time discussing the exam, and important uses of voronoi
diagrams. Examples included -- solving the minimum enclosing circle
problem, the maximum empty circle problem, farthest point voronoi
diagrams. We also proved that the minimum spanning tree is a subgraph
of the delaunay triangulation. Other important graphs include the
relative neighborhood graph, as well as the gabriel graph. All of this
material is discussed the the two books (O'Rourke and Preparata and Shamos).
You should read both the texts. We also studied some properties about the
floor function, using which one can obtain an O(n) algorithm for the
max-gap problem.

**Lecture 15: VORONOI DIAGRAMS AND CONVEX HULLS**
Connections between d dimensional voronoi diagrams/delaunay triangulations
with (d+1) dimensional convex hull problems. The DT has a direct
correspondence with the convex hull problem. Obtaining the VD is a little
trickier -- we have to construct the arrangement of the tangent planes for the
corresponding points on the surface of the paraboloid, and then project the
intersection of these arrangements to the plane. In particular, we need to
go above the paraboloid and view the arrangement from there -- this gives
us the VD. By going to deeper levels of the arrangement, we can obtain the
higher order voronoi diagrams. (Most of this material is from Chapter 5
of the textbook. The higher order voronoi diagram stuff comes from Chapter
6.)

**Lecture 16: ARRANGEMENTS AND DUALITY**
We study the point-line duality, some basic properties about it, and
the problem of computing the arrangement of n lines in the plane. We will
show that a simple "incremental" construction gives an optimal running time,
by proving the so called "zone theorem". In the next lecture we will study
more applications of duality.

**Lecture 17: APPLICATIONS OF DUALITY**
Applications of duality. Computing minimum area triangles from n given points
in the plane (paper by Chazelle, Guibas and Lee FOCS 1983 and BIT 25(1985))
Doing ray-shooting queries (paper by Chazelle and Guibas, Proc of ACM CG Conf
1985 and Discrete and Comp Geometry 4 (1989)).
**Handout**

**Lecture 18: DAVENPORT-SCHINZEL SEQUENCES**
Davenport-Schinzel sequences. We will study bounds on the length
of these sequences, as well as their uses in the analysis of
geometric algorithms.
**Handout**

*
The main topics that are left are geometric searching (point location,
range searching, geometric data structures, etc)
and visibility and motion planning. We will probably spend about 4 lectures
on each of these topics.*

**Lecture 19: PARAMETRIC SEARCHING** (Lecture by Mike Murphy)
We cover basics about parametric searching. Uses of parallel algorithms
in the design of faster serial algorithms. Applications of parametric
searching to distance selection.

**Lecture 20: PARAMETRIC SEARCHING** (Lecture by Samir Khuller and
Mike Murphy)
We covered the basic idea behind parametric searching as a method for
solving problems, where we have a a "ratio" objective function. The method
was then described in more detail for solving problems such as distance
selection etc.

**Lecture 21: POINT LOCATION**
We studied the O(log n) query time point location algorithm due to
Kirkpatrick. The basic idea is to repeatedly refine a triangulation
by picking a set of low degree nodes that also form an independent
set. We delete this set of nodes, and retriangulate. We prove that
this gives aus a set of O(log n) triangulations, and once we locate
a point in the coarsest triangulation, we can in O(1) time locate it
in a more refined triangulation. Repeating this gives the O(log n)
algorithm. We also studied a more paractical O(log^2 n) query time method
using monotone chains. (See Chapter 2.2 in Preparata-Shamos)

**Lecture 22: POINT LOCATION**
We studied a method to improve the space requirement of the practical
point location method to O(n) space, using the notion of a "gap". The
previous method used quadratic space. We also studied fractional cascading,
a method used to reduce the query time to O(log n). The basic idea behind the
method seems to yield a practical algorithm, but guaranteeing the
worst case bound is somewhat involved. Fractional Cascading is described in
Preparata-Shamos, the space saving method has a better description in
Samet's book on spatial data structures.

**Lecture 23: ORTHOGONAL RANGE SEARCHING**
This material is taken from Preparata and Shamos (Chapter 2.3). Range searching
is the inverse problem of point location. You are given a set of points
in d space, and wish to preprocess them to answer range queries; these are
of the form: report all points in a certain query "rectangle". Several
methods are known, some of them have high space requirements, and the
others do not give a O(log n) query time. k-d trees perform well in
practice, and are used. We will discuss a variety of approaches
finally leading to range-trees and then use "fractional cascading" to speed
up the queries.

**Lecture 24: START MOTION PLANNING/VISIBILITY STUFF**
We discussed Welzl's O(n^2) algorithm for computing visibility graphs
of n line segments. The main idea is to do a rotational sweep maintaining
the segments that are hit by the rays emanating from each point. The
processing order of the slopes needs to be chosen carefully to obtain
an O(n^2) time bound.
**Handout**

**Lecture 25: MOTION PLANNING**
This material is mostly taken from O'Rourke's book (Chapter 8).
We studied the notion of Minkowski sums, that can be used to reduce the
problem of moving a robot in the plane (translational motion) with
obstacles, to the motion of a single point in free space. We then studied
how we can extend this to the case when rotations are allowed -- motion of
a rod with translation and rotation. We then studied the idea behind
the cell decomposition method of Sharir and Schwartz to get a polynomial
algorithm for this problem. We briefly looked at the the retraction method
to plan the motion of a disc (translation only). This gives paths that
have a "high-clearance" property (avoid going close to obstacles).

**Lecture 26: MOTION PLANNING **
We studied various online navigational algorithms. The main objective
is to design an algorithm that navigates the robot between two points,
among rectangular obstacles, such that the total path length traversed
is not much longer than the true shortest path length between the start
and the goal. Two subproblems are defined and studied (1) the problem
of going from a start location to any point on a wall (2) the problem
of going from the corner of a room to an interior point. Efficient
algorithms are given for both cases, and finally combined to give
an algorithm for the general problem.
Most of the talk is taken from the paper by Blum, Schieber and Raghavan
in STOC 91. The original paper has some errors that have been fixed, the
revised version is to appear in SIAM J on Computing.

**Lecture 27: Review**

**Lecture 28: Video and Course Evaluation**

**Saturday, May 11th FINAL EXAM in AVW 1112/1152 9:30--12:00 **