CIS 677: Lectures

Lecture 1: an introduction via planar convex hulls

• basic facts about convexity
• Jarvis march
• a sorting-based algorithm
• a randomized incremental algorithm and its analysis
• problems of degeneracy and robustness

Lecture 2: orthogonal range search and its relatives

Comments on Homework 1.

• coordinate-wise dominance
• orthogonal range queries
• interval trees
• priority search trees
• segment trees
• filtering search

These topics, except filtering search, are covered in Chapters 5 and 10 of the text.

See also Mulmuley, section 8.1, for a discussion using skip lists instead of balanced trees and tries.

On-line priority search tree demo
On-line 2D range tree demo
A collection of spatial data structures

Filtering search is from:

• Chazelle, B. Filtering search: a new approach to query-answering. SIAM J. Computing, pp. 703-724, Vol. 15, 1986.

Lecture 3: line segment intersections

• line segment intersection
  
• some approaches
  
• sweep algorithm
  
• planar graph facts
  
• a randomized incremental algorithm
  
  • probability facts
  • analysis

A randomized incremental program for trapezoidal diagrams

Lecture 4: Simple polygons and planar point location

Comments on Homework 2.

• analysis of randomized incremental algorithm for trapezoidal diagrams, completed
• simple polygons
  • using connectivity to speed up search
  • converting trapezoidal diagrams to triangulations
• planar point location
  • a tail estimate
  • Kirkpatrick's algorithm

Lecture 5: Planar point location, Voronoi diagrams, Delaunay triangulations

• finishing up on planar point location
  • Kirkpatrick's algorithm
  • separator trees
  • bucketing, subdivision traversal
• Voronoi diagrams and Delaunay triangulations
  • basic facts
  • edge flipping and angle optimality
  • divide and conquer algorithm
  • sweep algorithm

These topics are covered, in part, in Chapters 7 and 9 of the text. The "separator tree" data structure for planar point location is discussed in Edelsbrunner's book.

There are many Java applets that for visualizing Voronoi diagrams and Delauanay triangulations; this one or that one seem good.

Lecture 6: Delaunay triangulations, Convexity

• Voronoi diagrams and Delaunay triangulations
  • edge flipping and angle optimality
  • uses: interpolation, geometric graphs
  • divide and conquer algorithm
  • sweep algorithm
• beginning Convexity
  • convex, affine, linear, conical combinations

These topics are covered, in part, in Chapters 7, 9, and 11 of the text. Convexity is a very large topic by itself, covered well in:

Bronsted, A. An introduction to convex polytopes.

Ziegler, G. M. Lectures on Polytopes.

Lecture 7: Convexity

• Caratheodory's theorem
• polarity and duality
• the Farkas Lemma
• convex hulls and intersections of halfspaces
• faces and the face lattice
• faces and polarity

Notes for lecture 8: Convexity and Algorithms

• convex hulls and intersections of halfspaces
• faces and the face lattice
• faces and polarity
• convex hulls, Delaunay triangulations, halfspace intersections, and Voronoi diagrams
• algorithms for convex hulls
  • a randomized incremental algorithm

Notes for lecture 9: Geometric optimization

Comments on Homework 2.

• Convex hulls
  • finishing up analysis of randomized incremental algorithm
  • handling degeneracy
• geometric optimization
  • The minimum-ball problem
  • algorithms
    • recursive
    • iterative reweighting
    • incremental
  • Linear programming
    • a pivoting algorithm

Notes for lecture 10: Geometric optimization, spatial subdivisions

• geometric optimization
  • The minimum-ball problem
  • algorithms:
    • incremental
  • linear programming
    • a pivoting algorithm
  • distance to polytopes
• spatial subdivision trees
  • quadtrees, k-d trees, BSP trees
  • uses and construction

Comments on Homework 3.

Notes for lecture 11: Quadtree applications, Arrangements, and k-sets

• More quadtree applications
• Arrangements
  • and duality
  • complexity
• Levels and $k$-sets
• high order Voronoi diagrams
• Zones
  • complexity
  • zones and BSP's