COT5520, CIS4930: COMPUTATIONAL GEOMETRY

Term: Fall 2009
Time: Tuesday 10:40am-11:30am, Thursday 10:40am-12:35pm
Location: CSE 222
Professor: Alper Üngör
Office hours: Tue 11:30am-1:30pm

syllabus announcements schedule projects references

Announcements

Schedule (Tentative)

Date Lecture Topic Assignments Speaker
Aug 25 Tu Introduction, syllabus, course structure, etc.    
  CONVEX HULLS ALGORITHMS [BKOS00, Chapter 1]    
Aug 27 Th Convex hulls
Orientation test; Degenaracy; Jarvis' march [J73]

A
Sep 1 Tu Convex hulls
Divide & conquer; Graham's scan [G72, A79] Chan's alg.[C96]
  A
  PLANE-SWEEP ALGORITHMS [BKOS00, Chapters 2 and 3 ]    
Sep 3 Th Line segment intersections
Plane-sweep [BO79];
  A
Sep 8 Tu Doubly linked edge list, Overlay subdivisions
HW1 out A
Sep 10 Th Polygon Triangulation
Triangulating monotone polygons [GJPT78]
  A
Sep 15 Tu Polygon Triangulation
Partitioning simple polygons
  A
Sep 17 Th Convex Partitioning
Lower and upper bounds, A factor 4 approximation algorithm
HW1 due A
  LINEAR PROGRAMMING [BKOS00, Chapter 4 ]    
Sep 22 Tu Manufacturing with Molds
Necessary and Sufficient condition, Half-Plane Intersections
  A
Sep 24 Th Linear Programming
Fesaible Region, Optimal solution;
Incremental and randomized algorithms
  A
  ORTHOGONAL SEARCH [BKOS00, Chapters 5 and 10]    
Sep 29 Tu Geometric data structures
Range Queries, kd-trees [B75];
  A
Oct 1 Th Range Search (more)
Range tree; fractional cascading [CG86]
  A
Oct 6 Tu Inverse Range Search
Segment tree [B77]; interval tree [E83]; priority search tree [M85]
  A
Oct 8 Th Mid-term Exam (in class, closed book)    
  VORONOI DIAGRAMS & DELAUNAY TRIANGULATIONS
[BKOS00, Chapters 7, 9, and 14]
   
Oct 13 Tu Voronoi diagrams
Voronoi diagrams [AK00]; furthest point Voronoi diagram, Other distance metrics
  A
Oct 15 Th Voronoi diagrams
Fortune's plane sweep algorithm
  A
Oct 20 Tu Delaunay triangulation
Empty circles, local Delaunayhood [D34],
edge-flip [L77], lifting, analysis, maxmin angles
  A
Oct 22 Th Randomized incremental algorithm
backward analysis [S93]
  A
Oct 27 Tu Randomized incremental algorithm
backward analysis [S93]
  A
Oct 29 Th Point Location
DAG structure for point location in triangulations
[BKOS00, Chapters 6 and 9]
Steiner triangulations
Steiner triangulation [BE95]; quality measure; quad-trees [BE95];
  A
Nov 3 Tu Project proposal discussions    
Nov 5 Th Delaunay refinement
Circumcenter insertion [R95]; Sphere packing argument
  A
  ARRANGEMENTS [BKOS00, Chapter 8]    
Nov 10 Tu Zones
Duality; line arrangements; complexity;
incremental algorithm; zone theorem [ESS93]
  A
Nov 12 Th Levels and discrepancy
Super-sampling for rendering; Half-plane discrepancy[EG89]
  A
  GEOMETRIC APPROXIMATION PROBLEMS    
Nov 17 Tu TSP
Approximation Algorithms, TSP, Hardness of Approximation
  A
Nov 19 Th Metric and Euclidean TSP
2-approximation, 3/2-approximation, tightness of analysis
Polynomial Time Approximation Scheme (PTAS)
  A
Nov 26 Th THANKSGIVING BREAK
Dec 1 Tu Project Presentations
Ferhat, John, Alex
 
Dec 3 Th Final Exam (in-class, closed book)    
Dec 8 Tu Project Presentations
Morning 10:40am: Young-Woong, Justin, Yan, Anubhav, Hechen
Evening 5pm (CSE 520A): Robert, Paul, Mallory, Karra, Yifan, Junjie, Qi, Christopher
   

References

Books
[BKOS00] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. [course textbook]
Lecture Slides by Marc van Kreveld (one of the authors of the textbook)
Lecture on Subdivision Overlays
Lecture on Polygon Triangulations
Lecture on Casting Polyhedra
Lecture on KD Trees
Lecture on Range Trees
Lecture on Window Queries
Lecture II on Window Queries
Lecture on Voronoi
Lecture II on Voronoi
Lecture on Delaunay
Lecture on Mesh Generation Lecture on TSP slides
Surveys
[E02] Lecture Notes on ConvexHulls by J. Erickson.
[E07] Lecture Notes on Polygon Triangulations by J. Erickson.
[BE95] M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Computing in Euclidean Geometry (2nd ed.), D.-Z. Du and F. Hwang (eds.), World Scientific, 1995, 47-123.
[E00] H. Edelsbrunner. Triangulations and meshes in computational geometry. Acta Numerica (2000), 133-213.

Other Papers
[A79] A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9:216-219, 1979. [A left-to-right variant of Graham's scan]
[AK00] F. Aurenhammer and R. Klein. Voronoi Diagrams. Handbook of Computational Geometry, Ed. J. Sack, J. Urrutia (eds.), 2000, 201-290.
[BDH96] B. Barber, D. Dobkin, and H. Huhdanpaa. The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software Vol. 22, No. 4, December 1996, Pages 469¿483.
[B75] J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18:509-517, 1975.
[B77] J. L. Bentley. Solution to Klee's rectangle problems. Tech. Rep., Carnegie-Mellon Univ., Pittsburgh, 1975.
[BO79] J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28:643-647, 1979.
[C96] T. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete and Computational Geometry, 16:361-368, 1996.
[CE92] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM 39:1-54, 1992.
[CG86] B. Chazelle and L. J. Guibas. Fractional cascading. Algorithmica 1:133-162 and 163-191, 1986.
[D34] B. N. Delaunay. Sur la Sphere vide. Izvestia Akademia Nauk SSSR, VII Seria, Otdelenie Matematicheskii i Estestvennyka Nauk 7:793-800, 1934.
[E83] H. Edelsbrunner. A new approach to rectangle intersections. International Journal Computational Mathematics 13:209-219 and 221-229, 1983.
[GJPT78] M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a simple polygon. Information Processing Letters, 7:175-179, 1978.
[G72] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132-133, 1972.
[GKS92] L. J. Guibas, D. E. Knuth, M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7:381-413, 1992.
[J73] R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2:18-21, 1973.
[KS86] D. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM J. Computing, 12:1:287-299, 1986.
[L77] C. L. Lawson. Software for C1 surface interpolation. Mathematical Software III, J. Rice ed., Academic Press, New York, 1977, 161-194.
[M85] E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14:257-276, 1985.

Links
[TOPP] The Open Problems Project by Erik D. Demaine - Joseph S. B. Mitchell - Joseph O'Rourke
[OP] Open Problems by Jeff Erickson
[OPDCG] Open Problems on Discrete and Computational Geometry by Jorge Urrutia
[SP] Sample Computational Geometry Projects from McGill University

Animations

syllabus announcements schedule projects references


Alper Üngör (ungor@cise.ufl.edu) Sep 2009