| LEC # | TOPICS | READINGS |
|---|---|---|
| 1 | Sylvester-Gallai Theorem, Scott's Problem about the Number of Distinct Slopes in the Plane |  Aigner, M., and G. M. Ziegler, eds. Proofs from the BOOK. 3rd ed. Berlin, Germany: Springer-Verlag, 2004, chapter 10, pp. 59-64. ISBN: 3540404600. |
| 2 | Scott's Problem about the Number of Distinct Directions in Three-space | Pach, János, Rom Pinchasi, and Micha Sharir. "On the Number of Directions Determined by a Three-Dimensional Points Set." Journal of Combinatorial Theory, Series A 108, no. 1 (October 2004): 1-16. |
| 3 | Motzkin-Rabin Theorem on Monochromatic Lines | Aigner, M., and G. M. Ziegler. Proofs from the BOOK. 3rd ed. Berlin, Germany: Springer-Verlag, 2004, chapter 11, pp. 59-64. ISBN: 3540404600. |
| 4 | Szemerédi-Trotter Theorem (Two Equivalent Formulations), Crossing Lemma | Szemerédi-Trotter Theorem (Two Equivalent Formulations) Brass, Peter, William Moser, and János Pach. Research Problems in Discrete Geometry. Berlin, Germany: Springer-Verlag, 2005, section 1.2.2. ISBN: 0387238158. Crossing Lemma Székely, László A. "Crossing numbers and hard Erdos problems in discrete geometry." Combinatorics, Probability and Computing 6, no. 3 (1997): 353-358. |
| 5 | Unit Distances, Unit Area Triangles, Beck's Two Extremities Theorem, Weak Dirac Conjecture | Unit Distances, Unit Area Triangles Brass, Peter, William Moser, and János Pach. Research Problems in Discrete Geometry. Berlin, Germany: Springer-Verlag, 2005, sections 5.1 and 6.2. ISBN: 0387238158. Beck's Two Extremities Theorem, Weak Dirac Conjecture Elekes, György. "SUMS versus PRODUCTS in number theory, algebra and Erdos geometry." In Paul Erdos and His Mathematics, II. Edited by G. Halász, L. Lovász, M. Simonovits, and V. T. Sós. Vol 11. Bolyai Society Mathematical Studies, Berlin, Germany: Springer-Verlag, 2002, pp. 241-290. ISBN: 3540422366. |
| 6 | Crossing Lemma for Multigraphs, Minimum Number of Distinct Distances | Crossing Lemma for Multigraphs Székely, László A. "Crossing numbers and hard Erdos problems in discrete geometry." Combinatorics, Probability and Computing 6, no. 3 (1997): 353-358. Minimum Number of Distinct Distances József Solymosi and Csaba D. Tóth. "Distinct distances in the plane." Discrete and Computational Geometry 25, no. 4 (2001): 629-634. Brass, Peter, William Moser, and János Pach. Research Problems in Discrete Geometry. Berlin, Germany: Springer-Verlag, 2005, section 5.3. ISBN: 0387238158. |
| 7 | Pach-Sharir Theorem on Incidences of Points and Combinatorial Curves | Pach, János, and Micha Sharir. "On the Number of Incidences Between Points and Curves." Combinatorics, Probability and Computing 7, no. 1 (1988): 121-127. |
| 8 | Various Crossing Numbers, Embedding Technique | Combinatorics Seminar: New Results On Old Crossing Numbers (or Old Results On New Ones?) (PDF) (Courtesy of János Pach and Geza Toth. Used with permission.) Various Crossing Numbers Pach, János, and Géza Tóth. "Which crossing number is it anyway? " Journal of Combinatorial Theory Ser B 80, no. 2 (2000): 225-246. Brass, Peter, William Moser, and János Pach. Research Problems in Discrete Geometry. Berlin, Germany: Springer-Verlag, 2005, section 9.4. ISBN: 0387238158.Embedding Technique Székely, László A. "Short proof for a theorem of Pach, Spencer, and Tóth." In Towards a Theory of Geometric Graphs (Volume 342 of Contemporary Mathematics). Providence, RI: Amer. Math. Soc. 2004, pp. 281-283. ISBN: 0821834843. Valtr, Pavel. "On the pair-crossing number." In Combinatorial and Computational Geometry (Volume 52 of Mathematical Sciences Research Institute Publication). Cambridge, UK: Cambridge University Press, 2005, pp. 569-575. ISBN: 0521848628. |
| 9 | More on Crossing Numbers Sum vs. Product Sets | More on Crossing Numbers Schaefer, Marcus, and Daniel Štefankovic. "Decidability of string graphs." Journal of Computational System Sciences 68, no. 2 (2004): 319-334. Section 3. Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovic. "Odd crossing number is not crossing number." In Proceedings of the 13th International Symposium on Graph Drawing (Lecture Notes in Computer Science) Berlin, Germany: Springer-Verlag, 2005. (To appear). Sum vs. Product Sets Solymosi, József. "On the number of sums and products." Bull London Math Soc 37, no. 4 (2005): 491-494. |
| 10 | Lipton-Tarjan and Gazit-Miller Separator Theorems | Lipton, Richard J., and Robert Endre Tarjan. "A separator theorem for planar graphs." SIAM Journal on Applied Mathematics 36, no. 2 (1979): 177-189. Gazit, Hillel, and Gary L. Miller. "Planar separators and the Euclidean norm." In Algorithms (Volume 450 of Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, 1990, pp. 338-347. ISBN 3540529217. |
| 11 | Cutting Circles into Pseudo-segments, Lenses, Transversal and Packing Numbers, d-intervals | Cutting Circles into Pseudo-segments Tamaki, Hisao, and Takeshi Tokuyama. "How to cut pseudoparabolas into segments." Discrete and Computational Geometry 19, no. 2 (1998): 265-290. Transversal and Packing Numbers, d-intervals Kaiser, Tomáš. "Transversals of d-intervals." Discrete and Computational Geometry 18, no. 2 (1997): 195-203. Alon, Noga. "Piercing d-intervals." Discrete and Computational Geometry 19, no. 3 (1998): 333-334. Matoušek, Jirí. "Lower bounds on the transversal numbers of d-intervals." Discrete and Computational Geometry 26, no. 3 (2001): 283-287. |
| 12 | Intersection Reverse Sequences | Marcus, Adam, and Gábor Tardos. "Intersection reverse sequences and geometric applications." In Proceedings of the 12th International Symposium on Graph Drawing (Volume 3383 of Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, 2004, pp. 349-359. ISBN: 3540245286. |
| 13 | Arrangements, Levels, Lower Envelopes, Davenport-Schinzel Sequences | Matoušek, Jirí. Lectures on Discrete Geometry. Berlin: Springer-Verlag, 2002, sections 6.1-6.2 and 7.1. ISBN: 0387953744. |
| 14 | Davenport-Schinzel Sequences of Order 3 | Matoušek, Jirí. Lectures on Discrete Geometry. Berlin: Springer-Verlag, 2002, sections 7.2-7.3. ISBN: 0387953744. |
| 15 | Complexity of the First k-levels, Clarkson-Shor Technique, Cutting Lemma | Clarkson-Shor Technique Sharir, Micha. "The Clarkson-Shor Technique Revisited and Extended." Combinatorics Probability and Computation 12, no. 2 (2003): 191-201. |
| 16 | Proof of Cutting Lemma, Simplicial Partitions | Combinatorics Seminar: On The Maximum Number Of Edges In K-Quasi-Planar Graphs (PDF ) (Courtesy of Eyal Ackerman. Used with permission.) Proof of Cutting Lemma Matoušek, Jirí. Lectures on Discrete Geometry. Berlin, Germany: Springer-Verlag, 2002, sections 4.6 and 6.5. ISBN: 0387953744.Simplicial Partitions Chazelle, Bernard. The Discrepancy Method. Cambridge, UK: Cambridge University Press, 2000, section 5.3. ISBN: 0521770939. |
| 17 | Spanning Trees with Low Stabbing Numbers | Chazelle, Bernard. The Discrepancy Method. Cambridge, UK: Cambridge University Press, 2000, section 5.3. ISBN: 0521770939. Asano, Tetsuo, Mark de Berg, Otfried Cheong, Leonidas J. Guibas, Jack Snoeyink, and Hisao Tamaki. "Spanning trees crossing few barriers." Discrete and Computational Geometry 30, no. 4 (2003): 591-606. |
| 18 | k-levels, k-sets, Halving Lines | Matoušek, Jirí. Lectures on Discrete Geometry. Berlin, Germany: Springer-Verlag, 2002, chapter 11. ISBN: 0387953744. |
| 19 | VC-dimension and ε-nets | Matoušek, Jirí. Lectures on Discrete Geometry. Berlin, Germany: Springer-Verlag, 2002, sections 10.2-10.3 ISBN: 0387953744. |
| 20 | Optimal ε-approximations, Links to Discrepancy Theory | Chazelle, Bernard. The Discrepancy Method. Cambridge, UK: Cambridge University Press, 2000, section 4.3. ISBN: 0521770939. |
| 21 | Binary Space Partitions | de Berg, Mark, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. 2nd ed. Berlin, Germany: Springer-Verlag, 2000, section 12. ISBN: 3540656200. Tóth, Csaba D. "Binary space partitions: recent developments." In Combinatorial and Computational Geometry (Volume 52 of Mathematical Science Research Institute Publications). Cambridge, UK: Cambridge University Press, 2005, pages 529-556. ISBN 0521848628. ———. "A note on binary plane partitions." Discrete and Computational Geometry 30, no. 1 (2003): 3-16. |
| 22 | Geometric Graphs and Forbidden Subgraphs | Pach, János, and Pankaj K. Agarwal. Combinatorial Geometry. New York, NY: Wiley & Sons Inc., 1995, chapter 14. ISBN: 0471588903. Brass, Peter, William Moser, and János Pach. Research Problems in Discrete Geometry. Berlin, Germany: Springer-Verlag, 2005, section 9.5. ISBN: 0387238158. |
| 23 | Zig-zag and Alternating Paths for Disjoint Segments | Tóth, Géza, and Pavel Valtr. "Geometric graphs with few disjoint edges." Discrete and Computational Geometry 22, no. 4 (1999): 633-642. Hoffmann, Michael, and Csaba D. Tóth. "Alternating paths through disjoint line segments." Information Processing Letters 87, no. 6 (2003): 287-294. Tóth, Csaba D. "Alternating paths along orthogonal segments." In Proc. 8th Workshop on Algorithms and Data Structures (Ottawa, ON, 2003) (Volume 2748 of Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, 2003, pp. 389-400. ISBN: 3540405453. |
| 24 | Crossing-free Hamiltonian Cycles and Long Monochromatic Paths | Hoffmann, Michael, and Csaba D. Tóth. "Segment endpoint visibility graphs are Hamiltonian." Computational Geometry Theory and Applications 26, no. 1 (2003): 47-68. Károlyi, Gyula, János Pach, Géza Tóth, and Pavel Valtr. "Ramsey-type results for geometric graphs II." Discrete and Computational Geometry 20, no. 3 (1998): 375-388. |
| 25 | Pseudo-triangulations and Art Gallery Problems | Aigner, M., and G. M. Ziegler. Proofs from the BOOK. 3rd ed. Berlin, Germany: Springer-Verlag, 2004, chapter 31, pp. 59-64. ISBN: 3540404600. Tóth, Csaba D. "Art gallery problem with guards whose range of vision is 180º." Computational Geometry Theory and Applications 17, no. 3-4 (2000): 121-134. Speckmann, Bettina, and Csaba D. Tóth. "Allocating Vertex Π-Guards in Simple Polygons via Pseudo-Triangulations." Discrete and Computational Geometry 33, no. 2 (2005): 345-364. |
Table of Contents
Study Materials
Readings
| When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more. |
Further References
Goodman, E., János Pach, and E. Welzl, eds. Combinatorial and Computational Geometry. Cambridge, UK: Cambridge University Press, 2005. ISBN: 0521848628.