Lecture Summaries for Polyhedral Computation      

Prof. David Avis                          Friday  8:45 - 10:15        

      also check:  announcements        return to:  course home page

Basic reference:    Komei Fukuda's Polyhedral Computation FAQ


Oct 7: Course outline. Several geometric problems in two dimensions: convex hull, line arrangements, triangulations.    notes
Exercise: We are given a set P of n points in the plane with no 4 points lying on a circle. We define a graph G as follows. The vertices of G are P. For each vertex v in P, join v to all other points in P which are at minimum distance from v. Here the distance means the normal Euclidean distance between points.
(a)  Prove that G is a subgraph of the Dealaunay triangulation.
(b) Give as good an upper bound as you can on the number of edges of G.
(c) Give a construction for the best lower bound you can get on the number of edges of G.

Oct 14:  Basic definitions: polyhedron, vertex, face, facet, etc. The vertex enumeration problem. Solution by dictionaries and graph search. If you are not familiar with LP dictionaries, please read this excerpt from Chvatal's Linear Programming.  English or Japanese          notes     Please review these slides.
Exercise: Use the brute force method of Section 2 of the notes to classify all cobases of the following system:
1+x1 ≥ 0,  1-x1+x2-x3 ≥ 0,  1 -x1-x2-x3 ≥ 0,  1+x1+x3 ≥ 0,  1+2x1+x2-x3 ≥ 0,  1+2x1-x2-x3≥0
Your solution should include (1) a complete classification of all 20 subsets chosen in step 1 (2) a graph like Figure 7 (3) a sketch like Figure 2
Oct 21: The graph search method for vertex enumeration. See notes for Oct. 14. Details of the adjacency oracle is in part 2 of these  notes

Exercise: Solve the problem for Oct 14 one more time using the graph search method and DFS. You may start from any of the feasible cobases you discovered doing the Oct 14 exercise.
In your report, you do not need to show every dictionary. However you should show the Adjacency oracle results for each dictionary as described in part 2 of the   notes
 
Exercises for Oct 7,14,21  are due in class on Nov 4 or give to Yuichi Yoshida.   Note new deadline!
Oct 28: The b-rule for finding a starting feasible solution . Read AMS paper .
Exercise: Solve the following two problems by the b-rule. Either give a feasible solution or a certificate of infeasibility via Farkas' lemma.
(a) x1 + x3 ≤ 1,      -3 x1+x2+x3 ≤ -1,    -x2 -3 x3 ≤ -1,   4 x1+2 x3 ≤ 1,    x1, x2, x3 ≥ 0
(b) -x1 -x2 -x3 ≤ -6,  -x1  -2x3 ≤ -2,  -x2 ≤ -3, -x3 ≤ 2,     x1, x2, x3 ≥ 0
Nov 4: The reverse search technique. Review slides and tutorial. See this page for more information and history.

Exercise: Do exercise 2.2 on page 3 of the tutorial. Write out in detail the new Adjacency oracle and Local Search function.
 Illustrate your method for n=5 where D contains edges 12, 23, 14 and 15. Draw out the reverse search tree. (You do not need to show all details of the calculations).
Nov 11: Guest lecture by Shinichi Tanigawa on enumeration of geometric objects by reverse search.   notes 

Exercise. Contained at the end of today's class notes. Do part (i) for regular credit. For extra credit towards 'S' grade do parts (ii) and (iii) also.

Nov 18:  Guest lecture by Marco Cuturi on Support Vector Machines and hyperplane separation of point sets.  notes

    Exercises for Oct 28, Nov 4, Nov11 due Nov 25 in class or give to Yuichi Yoshida.
Nov 25: Point hyperplane duality. We interpret a non-zero d-vector w as either wpoint in d-space, or as the hyperplane w.x=1. We say how to do facet enumeration using a vertex enumeration algorithm. Implications for degeneracy. Volume computation. notes

Exercise: Do an example similar to that shown on pages 6-2 and 6-3 of the notes, starting with an initial set of 5 vertices that contain the origin in the interior of their convex hull.
Show how to find the facets of the convex hull by vertex enumeration by using point-line duality. All students should do a different example!
Dec 2:   The cut polytope.  slides    Open pit mining problem. Directed max cut.  slides
Exercise: You will need to download the lrs software package from here (Dec 9 lecture discusses use of lrs)
(a) Construct the V-representation of the cut polytope with n=5. This has 10 dimensions and 16 vertices.
(b) Give a general description of each class of facets. (There are 5 different classes)
(c) Show the following vectors are not in the Cut polytope by giving a violated facet inequality:  
1/3*(2,2,2,2,2,2,2,2,2,2)     1/3*(2,2,2,1,2,2,1,2,1,1)        1/3*(2,2,1,1,2,1,1,1,1,2)
Dec 9:  Two person games, Nash equilibria: an application of vertex enumeration.  notes     paper
Exercise: Read the notes carefully, especially the example at the end. Choose your own 3 X 2 matrices A and B and compute all Nash equilibria by the same method.
Ie. first compute all vertices of the two related polyhedron using lrs and make a table like that in the middle of page 3. Now choose one of the two vertex lists (shorter one is better) and for each vertex in that list compute the Nash equilibria (if any) using the other vertex list.
Dec 16:  Stefan Langerman guest lecture on Ham sandwich cuts. slides   Exercises for Nov 25, Dec 2, Dec 9, due Dec 22 5pm in drop off box or give to Yuichi Yoshida.
Dec 23-Jan 3  Winter break.
Jan 6:    Voronoi diagrams and Delaunay triangulations.  notes    Jean Gallier's notes.

The double description method.      slides  
Jan 13:    No class.
Jan 20: Guest Lecture    Francois Le Gall    
Jan 27: No class.