Courses:

Geometric Combinatorics >> Content Detail



Study Materials



Readings

Amazon logo 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.
LEC #TOPICSREADINGS
1Sylvester-Gallai Theorem, Scott's Problem about the Number of Distinct Slopes in the PlaneAmazon logo 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.
2Scott's Problem about the Number of Distinct Directions in Three-spacePach, 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.
3Motzkin-Rabin Theorem on Monochromatic LinesAmazon logo Aigner, M., and G. M. Ziegler. Proofs from the BOOK. 3rd ed. Berlin, Germany: Springer-Verlag, 2004, chapter 11, pp. 59-64. ISBN: 3540404600.
4Szemerédi-Trotter Theorem (Two Equivalent Formulations), Crossing LemmaSzemerédi-Trotter Theorem (Two Equivalent Formulations)

Amazon logo 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.
5Unit Distances, Unit Area Triangles, Beck's Two Extremities Theorem, Weak Dirac ConjectureUnit Distances, Unit Area Triangles

Amazon logo 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

Amazon logo 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.
6Crossing Lemma for Multigraphs, Minimum Number of Distinct DistancesCrossing 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.

Amazon logo Brass, Peter, William Moser, and János Pach. Research Problems in Discrete Geometry. Berlin, Germany: Springer-Verlag, 2005, section 5.3. ISBN: 0387238158.
7Pach-Sharir Theorem on Incidences of Points and Combinatorial CurvesPach, János, and Micha Sharir. "On the Number of Incidences Between Points and Curves." Combinatorics, Probability and Computing 7, no. 1 (1988): 121-127.
8Various Crossing Numbers, Embedding TechniqueCombinatorics 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.

Amazon logo 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

Amazon logo 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.

Amazon logo 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.
9More 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.
10Lipton-Tarjan and Gazit-Miller Separator TheoremsLipton, Richard J., and Robert Endre Tarjan. "A separator theorem for planar graphs." SIAM Journal on Applied Mathematics 36, no. 2 (1979): 177-189.

Amazon logo 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.
11Cutting Circles into Pseudo-segments, Lenses, Transversal and Packing Numbers, d-intervalsCutting 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.
12Intersection Reverse SequencesAmazon logo 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.
13Arrangements, Levels, Lower Envelopes, Davenport-Schinzel SequencesAmazon logo Matoušek, Jirí. Lectures on Discrete Geometry. Berlin: Springer-Verlag, 2002, sections 6.1-6.2 and 7.1. ISBN: 0387953744.
14Davenport-Schinzel Sequences of Order 3Amazon logo Matoušek, Jirí. Lectures on Discrete Geometry. Berlin: Springer-Verlag, 2002, sections 7.2-7.3. ISBN: 0387953744.
15Complexity of the First k-levels, Clarkson-Shor Technique, Cutting LemmaClarkson-Shor Technique

Sharir, Micha. "The Clarkson-Shor Technique Revisited and Extended." Combinatorics Probability and Computation 12, no. 2 (2003): 191-201.
16Proof of Cutting Lemma, Simplicial PartitionsCombinatorics Seminar: On The Maximum Number Of Edges In K-Quasi-Planar Graphs (PDF ) (Courtesy of Eyal Ackerman. Used with permission.)

Proof of Cutting Lemma

Amazon logo Matoušek, Jirí. Lectures on Discrete Geometry. Berlin, Germany: Springer-Verlag, 2002, sections 4.6 and 6.5. ISBN: 0387953744.

Simplicial Partitions

Amazon logo Chazelle, Bernard. The Discrepancy Method. Cambridge, UK: Cambridge University Press, 2000, section 5.3. ISBN: 0521770939.
17Spanning Trees with Low Stabbing NumbersAmazon logo 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.
18k-levels, k-sets, Halving LinesAmazon logo Matoušek, Jirí. Lectures on Discrete Geometry. Berlin, Germany: Springer-Verlag, 2002, chapter 11. ISBN: 0387953744.
19VC-dimension and ε-netsAmazon logo Matoušek, Jirí. Lectures on Discrete Geometry. Berlin, Germany: Springer-Verlag, 2002, sections 10.2-10.3 ISBN: 0387953744.
20Optimal ε-approximations, Links to Discrepancy TheoryAmazon logo Chazelle, Bernard. The Discrepancy Method. Cambridge, UK: Cambridge University Press, 2000, section 4.3. ISBN: 0521770939.
21Binary Space PartitionsAmazon logo 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.

Amazon logo 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.
22Geometric Graphs and Forbidden SubgraphsAmazon logo Pach, János, and Pankaj K. Agarwal. Combinatorial Geometry. New York, NY: Wiley & Sons Inc., 1995, chapter 14. ISBN: 0471588903.

Amazon logo Brass, Peter, William Moser, and János Pach. Research Problems in Discrete Geometry. Berlin, Germany: Springer-Verlag, 2005, section 9.5. ISBN: 0387238158.
23Zig-zag and Alternating Paths for Disjoint SegmentsTó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.

Amazon logo 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.
24Crossing-free Hamiltonian Cycles and Long Monochromatic PathsHoffmann, 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.
25Pseudo-triangulations and Art Gallery ProblemsAmazon logo 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.



Further References


Amazon logo Goodman, E., János Pach, and E. Welzl, eds. Combinatorial and Computational Geometry. Cambridge, UK: Cambridge University Press, 2005. ISBN: 0521848628.


 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.