CS 369A Advanced Geometric Algorithms Spring 2006 |
Time and location |
Mondays and Wednesdays, 11:00--12:15, Gates 498
Syllabus |
Lecture notes |
Vladlen's lecture notes are here.
Timetable |
Date | Topics Covered | Sources and Further Readings |
April 5 | Definitions. Theorems of Helly, Radon, and Caratheodory. | [Mat1, Chap 1] |
April 10 | Defining epsilon-nets and VC-dimension. The example of halfspaces. Beginning the proof of the epsilon-net theorem. | [Mat1, Chap 10], [AS, Chap 13] |
April 12 | Finishing the proof of the epsilon-net theorem. epsilon-samples. Bounds on the VC-dimension of various geometric range spaces. | [Mat1, Chap 10], [AS, Chap 13] |
April 17 | Some more VC-dimension bounds. Applying epsilon-nets to construct an efficient point location data structure. | [SA, App 7.2 and Sec 8.3.3], [CF'94], [CS'90] |
April 19 | Data structures for segment intersection searching and simplex range searching. | [CSW'92], [K'03] |
April 24 | A data structure for exact nearest-neighbor searching. Rado's theorem and the computation of approximate centerpoints. | [SA, Sec 7.2.3], [Cla'88], [CEMST'96] |
April 26 | Basic properties of planar graphs. | [MN, Chap 5] |
May 1 | Koebe's theorem (first part of proof). | [PA, Chap 8] |
May 3 | Koebe's theorem (second part of proof) + Planar separators 1. | [ST'96], [MTTV'97] |
May 8 | Planar separators 2 + WSPDs 1. | [CK'95], [HP, Chap 5] |
May 10 | WSPDs 2. | [CK'95], [HP, Chap 5] |
May 14 (Sun, 3:00-6:30pm) |
Long lecture to make up
for Memorial Day and the two June sessions. WSPDs 3 + Euclidean TSP. |
[Aro'98], [Aro'03] |
May 15 | Nikola: Eppstein's approximation of the MWST | |
May 17 | Sid: Lipton & Tarjan | slides |
May 22 | Ying: Boyer & Myrvold | slides |
May 24 | Anthony: Har-Peled & Mendel | slides and notes |
May 29 | Memorial Day | |
May 31 | Emilio: Remy & Steger David: Har-Peled's low rank matrix approximation |
Emilio's slides, David's slides |
Papers for final project |
epsilon-nets and their applications
planar graphs
well-separated pair decompositions and their applications
geometric approximation algorithms
Sources and further readings |
books and lecture notes
[AS] Noga Alon, Joel H. Spencer, The Probabilistic Method
[HP] Sariel Har-Peled: Approximation Algorithms in Geometry
[Mat] Jiri Matousek: Lectures on Discrete Geometry
[MN] Jiri Matousek, Jaroslav Nesetril: Invitation to Discrete Mathematics
[PA] Janos Pach, Pankaj K. Agarwal: Combinatorial Geometry
[SA] Micha Sharir, Pankaj K. Agarwal: Davenport-Schinzel Sequences and their Geometric Applications
papers
[AHV'04] Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan: Approximating extent measures of points. J. ACM 51: 606-635 (2004)[Aro'98] Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J. ACM 45: 753-782 (1998)
[Aro'03] Sanjeev Arora: Approximation Schemes for Geometric NP-Hard Problems: A Survey, Math. Programming, 2003
[BH'01] Gill Barequet, Sariel Har-Peled: Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions. J. Algorithms 38: 91-109 (2001)
[Cha'02] Timothy M. Chan: Approximating the Diameter, Width, Smallest Enclosing Cylinder, and Minimum-Width Annulus. Int. J. Comput. Geometry Appl. 12: 67-85 (2002)
[CK'95] Paul B. Callahan, S. Rao Kosaraju: A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields. J. ACM 42: 67-90 (1995)
[CF'94] Bernard Chazelle, Joel Friedman: Point Location Among Hyperplanes and Unidirectional Ray-shooting. Comput. Geom. 4: 53-62 (1994)
[CS'90] Bernard Chazelle, Micha Sharir: An Algorithm for Generalized Point Location and its Applications. J. Symb. Comput. 10: 281-310 (1990)
[CSW'92] Bernard Chazelle, Micha Sharir, Emo Welzl: Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems. Algorithmica 8: 407-429 (1992)
[Cla'88] Kenneth L. Clarkson: A Randomized Algorithm for Closest-Point Queries. SIAM J. Comput. 17(4): 830-847 (1988)
[CEMST'96] Kenneth L. Clarkson, David Eppstein, Gary L. Miller, Carl Sturtivant, Shang-Hua Teng: Approximating center points with iterative Radon points. Int. J. Comput. Geometry Appl. 6: 357-377 (1996)
[K'03] Vladlen Koltun: Segment Intersection Searching Problems in General Settings. Discrete & Computational Geometry 30: 25-44 (2003)
[MTTV'97] Gary L. Miller, Shang-Hua Teng, William P. Thurston, Stephen A. Vavasis: Separators for sphere-packings and nearest neighbor graphs. J. ACM 44: 1-29 (1997)
[ST'96] Daniel A. Spielman, Shang-Hua Teng: Disk Packings and Planar Separators. Symposium on Computational Geometry 1996: 349-358