CS 369A Advanced Geometric Algorithms Prof. Vladlen Koltun Spring 2006

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

 

• Preliminaries from convex geometry: Theorems of Helly, Radon, Caratheodory, and Rado.
• VC-dimension and epsilon-nets. Applications to range searching, point location, nearest neighbor search, etc.
• Planar graphs: Basics, Koebe's theorem, existence and construction of planar separators.
• Well-separated pair decompositions. Applications to closest pairs, spanners, all-nearest-neighbors, and Euclidean minimum spanning trees.
• Arora's approximation algorithm for Euclidean TSP.
• Further topics presented by the students.

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	notes
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

epsilon-nets and their applications

1. Jiri Matousek: Efficient partition trees. Discrete & Computational Geometry, 8: 315-334, 1992. (1 person.)
   • Simplex range searching in linear space. No need to cover Sections 4, 6, and 7. In Section 5, just use Corollary 3.5 instead of Theorem 4.7.
2. Marco Pellegrini: Ray shooting on triangles in 3-space. Algorithmica, 9: 471-494, 1993. (1 person. Get from library.)
   • Application of the epsilon-nets machinery to the problem of ray-shooting. Only need to cover Sections 2 and 3, and Theorem 3.

planar graphs

3. 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.)
   • Linear-time planarity testing and embedding.
4. 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.)
   • The original planar separator theorem and its applications. No need to cover Sections 3,4,5 of the "applications" paper.

well-separated pair decompositions and their applications

5. 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.)
   • Proves that to reap the benefits of well-separated pair decompositions the points need not lie in a Euclidean space. All that is needed is an abstract metric with a constant doubling dimension. The paper shows how to construct compressed quadtrees for such metrics. The construction of WSPDs follows with its applications. Cover Sections 2,3,5,10; a team of 2 people should cover Section 4 as well.

geometric approximation algorithms

6. Sanjeev Arora, Prabhakar Raghavan, Satish Rao: Approximation schemes for Euclidean k-medians and related problems. STOC 1998: 106-113. (1 person.)
   • Adapts Arora's TSP techniques to a clustering problem.
7. Jan Remy, Angelika Steger: A quasi-polynomial time approximation scheme for minimum weight triangulation. STOC 2006. (1 or 2 people.)
   • A dynamic programming-based approximation scheme for a well-known problem.
8. David Eppstein: Approximating the minimum weight Steiner triangulation. Discrete & Computational Geometry, 11: 163-191 (1994). (1 or 2 people.)
   • A constant-factor approximation algorithm based on quadtrees. No need to cover Section 5.
9. Sariel Har-Peled: How to get close to the median shape. SoCG 2006. (1 or 2 people.)
   • Uses coresets for L₁-shape fitting.
10. Sariel Har-Peled: Low rank matrix approximation in linear time, manuscript, 2006. (1 or 2 people.)
    • An elegant PTAS for an important problem. Uses a lot of ideas touched on in the class.

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