COT5520: COMPUTATIONAL GEOMETRY | |
Term: Fall 2006
| |
Time: Tuesday 3:00pm-4:55pm, Thursday 4:05pm-4:55pm | |
Location: MCCA2196 | |
Professor: Alper Üngör | |
Office hours: Wed 10am-noon | |
TA: Tianyun Ni | |
TA Office hours: Thu 10am-noon |
syllabus | announcements | schedule | projects | references |
Date | Lecture Topic | Assignments | Speaker |
Aug 24 Th | Introduction, syllabus, course structure, etc. | HW#0 out [ps, pdf] | A |
CONVEX HULLS ALGORITHMS [BKOS00, Chapter 1] | |||
Aug 29 Tu | Convex hulls Orientation test; Degenaracy; Jarvis' march [J73] | A | |
Aug 31 Th | Convex hulls Divide & conquer; Graham's scan [G72, A79] Chan's alg.[C96] | A | |
PLANE-SWEEP ALGORITHMS [BKOS00, Chapters 2 and 3 ] | |||
Sep 5 Tu | Line segment intersections Plane-sweep [BO79]; |   | A |
Sep 7 Th | Doubly linked edge list, Overlay subdivisions | HW#1 out [ps, pdf] | A |
Sep 12 Tu | Polygon Triangulation Triangulating monotone polygons [GJPT78] |   | A |
Sep 14 Th | Polygon Triangulation Partitioning simple polygons |   | A |
Sep 19 Tu | Convex Partitioning Lower and upper bounds, A factor 4 approximation algorithm | HW#1 due | A |
LINEAR PROGRAMMING [BKOS00, Chapter 4 ] | |||
Sep 21 Th | Manufacturing with Molds Necessary and Sufficient condition, Half-Plane Intersections |   | A |
Sep 26 Tu | Linear Programming Fesaible Region, Optimal solution; Incremental and randomized algorithms |   | A |
  | ORTHOGONAL SEARCH [BKOS00, Chapters 5 and 10] |   |   |
Sep 28 Th | Geometric data structures; Range search Quad-tree; kd-tree [B75]; |   | A |
Oct 3 Tu | Improvements on range searching Range tree; fractional cascading [CG86] | HW#2 is out [ps, pdf] | A |
Oct 5 Th | Inverse Range Search Segment tree [B77]; interval tree [E83]; priority search tree [M85] |   | A |
  | VORONOI DIAGRAMS & DELAUNAY TRIANGULATIONS [BKOS00, Chapters 7, 9, and 14] |   |   |
Oct 10 Tu | Voronoi diagrams
Voronoi diagrams [AK00]; furthest point Voronoi diagram, Other distance metrics |   | A |
Oct 12 Tu | Voronoi diagrams
Fortune's plane sweep algorithm |   | A |
Oct 17 Th | Delaunay triangulation Empty circles, local Delaunayhood [D34], edge-flip [L77], lifting, analysis, maxmin angles | HW#2 due | A |
Oct 19 Th | Randomized incremental algorithm Incremental construction [GKS92]; backward analysis [S93] |   | A |
Oct 24 Th | Project proposal presentations and discussions | HW#3 is out [ps, pdf] | |
Oct 26 Th | Project proposal presentations and discussions | HW#2 Graded | |
Oct 31 Tu | 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 2 Th | Delaunay refinement Circumcenter insertion [R95]; Sphere packing argument | A | |
  | ARRANGEMENTS [BKOS00, Chapter 8] |   |   |
Nov 7 Tu | Zones Duality; line arrangements; complexity; incremental algorithm; zone theorem [ESS93] | HW#3 due | A |
Nov 9 Th | Levels and discrepancy Super-sampling for rendering; Half-plane discrepancy[EG89] |   | A |
  | OTHER GEOMETRY APPLICATIONS [BKOS00, Chapters 13 and 15] |   |   |
Nov 14 Tu | Geometric Approximation Algorithms TSP, Metric TSP, Euclidean TSP Polynomial Time Approximation Scheme (PTAS) | HW#4 is out [ps, pdf] | A |
Nov 16 Th | Motion Planning Trapezoidel Maps; Robotics; Configuration Space; Connectedness; Visibility Graphs |   | A |
Nov 21 Tu | Various Applications of Computational Geometry Video Proceedings of SoCG 2003-2006 |   | A |
Nov 23 Th | THANSGIVING BREAK | ||
Nov 28 Tu | Project Presentations |   |   |
Nov 30 Th | Project Presentations | Reports due |   |
Dec 5 Tu | Final Exam (in-class, closed book) |   |   |
BooksSurveys
[BKOS00] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000. [course textbook]
[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
- 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 |