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 |
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 |
BooksLecture Slides by Marc van Kreveld (one of the authors of the textbook)
[BKOS00] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. [course textbook]
[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.
[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.
[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
- Voronoi Game and the Applet
- Sweepline Algorithm Animation for Voronoi Diagrams
- Convex Hulls by Alejo Hausner [Graham's scan, Jarvis march, and quickhull]
- Convex Hull Algorithms by Tim Lambert [incremental, gift-wrapping, divide and conquer, and quickhull]
- Sweepline algorithm for Line Segment Intersection by Wei Qian
- An Applet on the Art gallery problem
- Voronoi Diagram Illustrations
- Duality Demo
- PTAS_TSP slides
- Visibility Applet
syllabus | announcements | schedule | projects | references |