18.325 Topics in Applied Mathematics: Discrete Geometry
Instructor: Csaba D. Tóth
2007 Spring,
TR 12:30-2 Room 26-314

Office hours: W 1-2pm and by appointment on any afternoon at 2-336.
Grades will be based on problem sets or research projects.

Feb 7, W Conflict-free colorings (definitions, CF-colorings for halfspaces and disks) [HS05]
Fec 13, T
 The complexity of the union of disks and pseudo-disks  [KLP86], [AEH01]
Feb 15, R
 Regular and irregular vertices on the boundary of the union of convex sets [PS99]
Feb 22, R
 Read Section 1.3 "Radon's Lemma and Helly's Theorem" in [M02]
Feb 27, T
 Read Chapter 8 "Intersection Patterns of Convex Sets"  in [M02]
Mar 1, R
 Solve problems at the end of Chapter 8 "Intersection Patterns of Convex Sets"  in [M02]
Mar 6, T
 Distinct triangle areas in the plane, Ungar's theorem
Mar 8, R
 Koebe's theorem [PA95]
Mar 13, T
 Separator theorems [PA95], Turán-type results for the intersection graphs of convex sets [PS06]
Mar 15, R
 Ramsey-type results for the intersection graphs of segments [LMP94]
Mar 20, T
 Erdős-Hajnal properties and the intersection graphs of segments [APP05][PS01]
Mar 22, R
 The intersection pattern of convex sets
Apr 3, T
 Read Chapter 9 from [PA95]
Apr 5, R
 Solve Excercises at the end of Chapter 9 in [PA95]
Apr 10, T
 Sweep-line heuristics for Euclidean minimum spanning trees [NS07]; the first selection theorem [M02]
Apr 12, R
 The ε-net theorem [M02]
Apr 19, R
 No class today.
Apr 24, T
 Weak ε-nets [CEG95][MW04][MR07][AKN07][K07]
Apr 26, R
 The Hadwiger-Debrunner (p,q)-problem [AK92][AK97][M02]
May 1, T
 Unit area triangles in the plane [PS92]
May 3, R
 Maximum and minimum area triangles in the plane [BRS01]
May 8, T
 Networks with small geometric dilation for a planar point set [E00][KK06][EGK06]
May 10, R
 Geometric spanner networks with constant degree and weight [DEG07][FM00]
May 15, T
 Traversing a point set with min-max turns [AHH07], Convex subdivisions with low stabbing numbers [CEG89]
May 17, R Encompassing graphs [HT03][HST04]


Topics:
Conflict-free colorings, ✔
Combinatorial bounds on the complexity of the union of geometric objects. ✔
Helly and Carathéodory-type results. ✔
Intersection patterns of segments, pseudo-segments, and convex sets in the plane. ✔
Selection theorems, transversals, ε-nets, and weak ε-nets. ✔
Extremal bounds on the number of triangles of unit area, unit perimeter. ✔
Constructing spanner networks with constant  geometric dilation for a point set. ✔
Traversing a point set with few sharp turns. ✔
Subdivisions with low stabbing numbers. ✔
Encompassing graphs. ✔

Bibliography;
  1. [M02] Jiří Matoušek, Lectures on Discrete Geometry, Springer-Verlag, Berlin, 2002. ISBN 0387953744
  2. [C00] Bernard Chazelle, The Discrepancy Method, Cambridge University Press, Cambridge, 2000, ISBN 0521770939
  3. [PA95] János Pach and Pankaj K. Agarwal, Combinatorial Geometry, Wiley, 1995, ISBN 0471588903
  4. [BKO00] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf,  Computational Geometry: Algorithms and Applications, 2nd edition, Springer-Verlag, Berlin, 2000. ISBN 3-540-65620-0
  5. [HS05] Sariel Har-Peled and Shakhar Smorodinsky, Conflict-free coloring of points and simple regions in the plane, Discrete & Computational Geometry 34 (2005), 47-70.
  6. [KLP86]  Klara Kedem, Ron Livne, János Pach, and Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,  Discrete & Computational Geometry 1 (1986), 59-71.
  7. [AEH01] Boris Aronov, Alon Efrat, Dan Halperin, Micha Sharir, On the number of regular vertices of the union of Jordan regions, Discrete & Computational Geometry 25 (2001), 203-220.
  8. [PS99] János Pach and Micha Sharir, On the boundary of the union of planar convex sets, Discrete & Computational Geometry 21 (1999), 321-328.
  9. [LLS03] Ching-Chi Lin, Hsueh-I. Lu, and I.-Fan Sun, Visibility representation of planar graphs via Schnyder's realizer, in Proc. 20th Sympos. on Theoretical Aspects of Comp. Sci.,
    vol. 2607 of LNCS, Springer, Berlin, 2003, pp. 14-25.
  10. [PS06] János Pach and Micha Sharir, On planar intersection graphs with forbidden subgraphs, manuscript, 2006.
  11. [APP05] Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić and Micha Sharir,  Crossing patterns of semi-algebraic sets, J. Combinatorial Theory, Series A 111 (2) (2005),  310-326.
  12. [PS01] János Pach and József Solymosi, Crossing patterns of segments, J. Comb. Theory, Ser. A 96 (2001), 316-325.
  13. [LMP94] David Larman, Jiří Matoušk, János Pach, Jenő Törőcsik,  A Ramsey-type result for convex sets, Bull. London Math. Soc.  26  (2) (1994), 132-136.
  14. [NS07] Giri Narasimhan and Michiel Smid, Geometric Spanner Networks, Cambridge Univ. Press, 2007.
  15. [CEG95] Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl, Improved bounds on weak ε-nets for convex sets, Discrete & Computational Geometry 13 (1) (1995), 1-15.
  16. [MW04] Jiří Matoušk and Uli Wagner, New constructions of weak ε-nets,  Discrete & Computational Geometry 32 (2) (2004), 195-206.
  17. [MR07] Nabil H. Mustafa and Saurabh Ray, Weak ε-nets have a basis of size O(1/ε log 1/ε) in any dimension, in Proc 23rd ACM Sympos. on Computational Geometry (Gyeongju, 2007), to appear.
  18. [AKN07] Noga Alon, Haim Kaplan, Gabrial Nivasch, Micha Sharir, and Shakhar Smorodinsky, Weak ε-nets in convex position, in preparation, 2007.
  19. [AK92] Noga Alon and Daniel J. Kleitman,  Piercing convex sets and the Hadwiger-Debrunner (p,q)-problem, Adv. Math.  96  (1) (1992), 103--112.
  20. [AK97] Noga Alon and Daniel J. Kleitman, A purely combinatorial proof of the Hadwiger Debrunner (p,q) conjecture, The Wilf Festschrift (Philadelphia, PA, 1996),  Electron. J. Combin. 4  (2) (1997).
  21. [PS92] János Pach and Micha Sharir, Repeated angles in the plane and related problems, J. Comb. Theory, Ser. A 59 (1) (1992), 12-22.
  22. [BRS01] Peter Braß, Günter Rote, Konrad J. Swanepoel, Triangles of extremal area or perimeter in a finite planar point set, Discrete & Computational Geometry 26 (1) (2001), 51-58.
  23. [KK06] Rolf Klein and Martin Kutz, The density of iterated crossing points and a gap result for triangulations of finite point sets, in Proc. 22nd ACM Sympos. on Comput. Geom. (Sedona, 2006), pp. 264-272.
  24. [E00] David Eppstein, Spanning trees and spanners, in Handbook of Computational Geometry (eds., J.-R. Sack and J. Urrutia), Elsevier, 2000, pp. 425-461.
  25. [EGK06] Annette Ebbers-Baumann, Ansgar Grüne, and Rolf Klein, The geometric dilation of finite point dets, Algorithmica 44 (2) (2006), 137-149.
  26. [DEG07] Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, and Günter Rote, On the geometric dilation of closed curves, graphs, and point sets, Comput. Geom. Theory Appl. 36 (1) (2007), 16-38.
  27. [FM00] Sándor P. Fekete and Henk Meijer, On minimum stars and maximum matchings, Discrete & Computational Geometry 23 (3) (2000), 389-407.
  28. [AHH07] Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber, Maximizing maximal angles for plane straight-line graphs, in Proc. 10th Workshop on Algorithms and Data Structures, LNCS, Springer, 2007, to appear.
  29. [CEG89] Bernard Chazelle, Herbert Edelsbrunner, and Leonidas J. Guibas, The complexity of cutting complexes, Discrete & Computational Geometry 4 (1989), 139-181.
  30. [HT03a] Michael Hoffmann and Csaba D. Tóth, Segment endpoint visibility graphs are Hamiltonian, Comput. Geom. Theory Appl. 26 (2003), pp. 47-68.
  31. [HT03b] Michael Hoffmann and Csaba D. Tóth, Alternating paths through disjoint line segments, Inform. Proc. Letts. 87 (2003), 287-294.
  32. [HST04] Michael Hoffmann, Bettina Speckmann, and Csaba D. Tóth, Pointed binary encompassing trees: simple and optimal, in Abstracts of 14th Annual Fall Workshop on Computational Geometry (Cambridge, MA, 2004), pp. 28-29.