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