Advanced Geometric Algorithms

Prof. Vladlen Koltun

Spring 2006

Time and location

Mondays and Wednesdays, 11:00--12:15, Gates 498




Lecture notes

Vladlen's lecture notes are here.



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

  1. Jiri Matousek: Efficient partition trees. Discrete & Computational Geometry, 8: 315-334, 1992. (1 person.)
  2. Marco Pellegrini: Ray shooting on triangles in 3-space. Algorithmica, 9: 471-494, 1993. (1 person. Get from library.)

planar graphs

  1. John M. Boyer, Wendy J. Myrvold: On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, 8(3): 241-273, 2004. (1 or 2 people.)
  2. Richard J. Lipton, Robert E. Tarjan: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979  and  Richard J. Lipton, Robert E. Tarjan: Applications of a planar separator theorem. SIAM Journal on Computing, 9(3): 615-627, 1980. (1 or 2 people.)

well-separated pair decompositions and their applications

  1. Sariel Har-Peled, Manor Mendel: Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing 35(5): 1148-1184, 2006. (1 or 2 people.)

geometric approximation algorithms

  1. Sanjeev Arora, Prabhakar Raghavan, Satish Rao: Approximation schemes for Euclidean k-medians and related problems. STOC 1998: 106-113. (1 person.)
  2. Jan Remy, Angelika Steger: A quasi-polynomial time approximation scheme for minimum weight triangulation. STOC 2006. (1 or 2 people.)
  3. David Eppstein: Approximating the minimum weight Steiner triangulation. Discrete & Computational Geometry, 11: 163-191 (1994). (1 or 2 people.)
  4. Sariel Har-Peled: How to get close to the median shape. SoCG 2006. (1 or 2 people.)
  5. Sariel Har-Peled: Low rank matrix approximation in linear time, manuscript, 2006. (1 or 2 people.)


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


[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


CS369A Spring 2006
Vladlen Koltun