COMP507A Computational Geometry  Fall 2006
Lecture Descriptions, Homework, and Play
Text Book: Computational
Geometry
in C by Joseph O'Rourke
"Geometry is a skill of the eyes and the
hands as well as the mind."  Jean Pedersen
Week: 1

2

3
4

5

6

7

8

9

10

11

12

13
Week 1  Sept 5 and 7
Lecture 1

Introduce course

Smallest enclosing circle

Brute force algorithm

Models of computation

The straightedgeandcompass computer

The toothpick computer

Rulers with few marks

Review projects
Problem Assignment 1 out 
"due" September
19

Constructing
a square with the Toothpick Computer

Measuring
distances
with rulers that have few marks

Circles
enclosing
polygons

Recognizing
if a (possibly crossing) polygon is convex (and simple) in linear time
Lecture 2

Review more projects

The Real RAM (ceiling and floor functions)

Define polygons (Jordan curve theorem)

Data structures for polygons (standard form)

Area of a triangle (of a polygon)

Point inclusion:

In a triangle

In a simple polygon

The plumbline algorithm

Sidedness test

Segment intersection test
Reading Assignment

Text: 1.3  Area of a polygon

Text: 1.5  Segment intersection

Web: 1.6.1  Notes on methods of proof

Web: 1.1.3  A New Look at Euclid's Second Proposition (PostScript)

Web: 2.1  Jordan curve theorem
Suggested Play

Web: 1.1.1  Applet of Francois Labelle
Week 2  Sept 12
and
14
Lecture 3

Discuss projects

Point inclusion continued

Query mode for simple polygons

Testing convexity

Of simple polygons

Of crossing polygons
Lecture 4

Twoears theorem

Via induction

Via dual trees

Chvatal's art gallery theorem

Fisk's proof
Reading Assignment

Text: Chapter 1

Web: 3.13.3  Testing the orientation and
convexity
of a polygon

Web: 4.2.1  Ian Garton's tutorial on
polygon triangulation
Suggested Play

Web: 4.2.1  Ian Garton's applets
Week 3  Sept 19
and
21
Lecture 5:

Triangulating simple polygons

Via earcutting

Via diagonal insertion

Convex partitioning of simple polygons

A hierarchy of simple polygons

Walkable polygons

Street polygons
Lecture 6:

Polygonizations of point sets

Maximal vectors

Monotonic polygonizations

Starshaped polygonizations

Onion polygonizations
Problem Assignment 2: "due"
October
10

Enclosing
a
convex polygon with a triangle

Midpoint
polygonization
of points

Visibility
in streetpolygons and walkablepolygons
Reading Assignment

Text: Chapter 2  Polygon partitioning

Web: 5.1.2  Tutorial on art gallery theorem

Web: 6.1  Polygonization tutorial
Suggested Play

Web: 5.1.2  Thierry Dagnino's applet

Web: 6.1  Polygonization applet

Web: 6.2  Polygonization counter (applet)
Week 4  Sept 26
and
Sept 28
Lecture 7

Diameter algorithms for convex polygons

SnyderTang algorithm

Twocoins algorithm

Multimodal functions
Lecture 8

Diameter via rotating calipers

Antipodal pairs

O(n) time for convex polygons

Convex hull algorithms for points in the plane

Rosenberg and Landgridge algorithm  O(n^3) time

The Jarvis march (gift wrapping)  O(hn)
Reading Assignment

Web: 7.1  Mikowski metrics

Web: 7.1.1  Distance

Web: 7.1.2  Manhattan metric

Web: 7.5.1  Diameter algorithms

Handout  Multimodality

Handout  SnyderTang algorithm
Suggested Play

Web: 7.1.2  Taxicab metric applet

Web: 7.6.1  Jaqueline Chen's tutorial on
width and
line fitting

Web: 7.7  Rotating calipers
Week 5  Oct 3
and
5
Lecture 9:

The Graham scan and starshaped polygonizations

The 3coins algorithm for polygons  O(n)

Starshaped polygons

Monotone polygons

Weakly externally visible polygons

Lower bound by reduction from sorting
Lecture 10:

Triangulation of point sets via sorting and 3coins algorithm

More convex hulls:

The ThrowAway Principle and O(n) expected time algorithms

Quickhull

Quickhull with medians

Sequential insertion (beneathbeyond)

With presorting in O(n log n) time

Without presorting and point inclusion testing in O(n log n) time
Reading Assignment

Text: Chapter 3  Convex hulls in the plane

Web: 10.3.3  A fast convex hull algorithm
(algorithm
of Akl and Toussaint)
Suggested Play

Web: 10.1  Convex hull applet

Web: 7.7.1  Rotating caliper page of
Hormoz Pirzadeh
Week 6  Oct
10
and 12
Lecture 11:
First InClass Exam  Examples ( 2000
2003)
Lecture

Movable separability of sets:

Sofa problems

Balls in space (Dawson's theorem)

Orthogonal boxes (GuibasYao theorem)

Convex polygons in 2 dimensions
Problem Assignment 3: "due"
October
24

Computing
the
diameter of a polygon

Computing
the
diameter of a set of points

Triangulations,
sorting and lower bounds

Convex
hulls
of polygons
Reading Assignment

Text: Chapter 4

Web: 7.5.1  Diameter algorithms

Web: 10.4.1  3coins algorithm

Handout: the GrahamYao algorithm

Handout: Melkman's algorithm
Suggested Play

Web: 17.2  Movable separability of objects

Web: 17.1  Applet for the matchstick game

Web: 17.2.1  Applet for separating
starshaped polygons

Web: 7.7.1  Rotating caliper page of
Hormoz Pirzadeh

Web: 7.5.1  Diameter algorithm applet

Web: 10.4.1  3coins algorithm applet
Week 7Oct 17 and
19
Lecture 13:

Convex hulls continued:

Randomized sequential insertion

Divide and conquer:

With presorting

Without presorting and rotatingcaliper merge

Sequential insertion (beneathbeyond)

In 3dimensions in O(n^2) time
Lecture 14:

Convex hulls continued:

Outputsensitive convex hull algorithms:

KirkpatrickSeidel's ultimate algorithm

Timothy Chan's algorithm

Convex hulls of simple polygons:

O(n) time convex hulls of simple polygons

The GrahamYao algorithm

Melkman's online algorithm
Reading Assignment

Web: 10.1.1.1.1  Randomized incremental
convex hull
algorithm

Web: 10.1.1.7  KirkpatrickSeidel ultimate
algorithm

Web: 10.1.6  Timothy Chan's algorithm
Suggested Play: none this week
Week 8  Oct 24
and
26
Lecture 15

Movable separability problems:

Convex polyhedra 3 dimensions

The width of a set (definition)

Passing a chair through a door (Strang's theorem)

O(n) algorithm for computing the width of a convex polygon

Separating starshaped polygons and
polyhedra

Dawson's theorem
Lecture 16

Movable separability problems:

Separating monotone polygons

Separating two simple polygons

Dualtree of a triangulated polygon

Shortest paths inside polygons

Relative (geodesic) convex hulls
Week 9  Oct 31
and
Nov 2
Lecture 17

Intersectig convex polygons:

Slab method of Shamos & Hoey

Via rotating caliper method and
sailpolygons

Divide & Conquer algorithm for
intersecting halfplanes
Lecture 18

Introduction to Voronoi diagrams

Proximity graphs(properties)

Nearest neighbor graphs

Minimum spanning trees

Relative neighborhood graphs

Gabriel graphs

Delaunay triangulations

NNGMSTRNGGGDT relationships

Computing proximity graphs

Proximity graphs via local search of the
Delaunay
triangulation

Relative neighborhood graph algorithms
and counter
examples

Bucketing methods
Reading Assignment

Text: 5  Voronoi diagrams and applications

Web: 14.3  The relative neighborhood graph

Web: 14.9  Proximity graphs (including a
survey
paper)
Suggested Play

Web: 14.1  Minimal spanning tree applet

Web: 14.6.1  Fantastic applet for Voronoi
diagrams
and Delaunay triangulations
Week 10  Nov 7
and
9
Lecture 19

Alphahulls and alphashapes

Sphereofinfluence graph

Nearest and furthestpoint Voronoi diagrams

Flipping algorithm for the Delaunay
triangulation

Voronoi diagram algorithms

Via halfplane intersections in O(n^2
log n) time

Proof that the nearest neighbor is a
Voronoi neighbor

Voronoi diagram algorithms  cont.

Rhynsberger's algorithm  O(n^2)

Voronoi diagrams in 2D via convex hulls
in 3D by
lifting points to paraboloid

Voronoi diagram algorithm via divide and
conquer
 O(n log n)

Properties of furthestpoint Voronoi
diagrams

The smallest enclosing circle in O(n log
n) time
via furthestpoint Voronoi diagrams
Lecture 20

Linear programming in linear time in the
plane (Meggido's
algorithm)

Efficient polygon triangulation.

Sleeve searching algorithm in O(n(1+t))
time where
t is the number of vertices of degree 3 in the dual tree of the
triangulation
delivered.
Handling degeneracies

Computing nice viewpoints of objects in space

Regular projections in knot theory

Wirtinger projections in computer vision

Visualization in computer graphics

Handling degeneracies in computational geometry

No two points on a vertical line (2 and 3 dimensions)

Decision problem

Computation problem

Optimization problem

Largest gap problem

Gonzales' algorithm with floor functions and pigeonhole principle
Reading Assignment

Handout: Meggido's algorithm

Handout: Sleeve searching polygon
triangulation algorithm

Web: 18.7  Removing extrinsic degeneracies
in computational
geometry

Web: 18.8  Computing nice viewpoints of
objects
in space

Web: 14.9  Proximity graphs (including a
survey
paper)

Text: Chapter 4  Convex hulls in 3
dimensions

Web: 14.3  Relative neighborhood graph

Web: 14.8  Sphereofinfluence graph
tutorial (Richard
Unger)
Suggested Play

Web: 14.8  Sphereofinfluence graph applet
Week 11  Nov 14
and
16
Lecture 21: Second
Midterm Exam (Examples of previous exams:)
Lecture 22: Student
Presentations
Week 12  Nov 21 and 23
Lecture 23:
Student
Presentations
Lecture 24: Student
Presentations and
Course
Evaluations
Week 13  Nov 28 and 30
Lecture 25: Student Presentations
Week 14  Dec 5
Lecture 25: Student
Presentations