Dates: September 30  October 4, 2002
Location: DIMACS Center, CoRE Building, Rutgers University
Organizer: Janos Pach, City College and Courant Institute, New York
Email: pach@cims.nyu.edu

The rapid development of computational geometry
in the past two decades presented a powerful new source of inspiration
for combinatorial geometry, the theory of geometric arrangements. Many
curious extremal problems in recreational mathematics turned out to be
crucially important for the analysis of a wide range of geometric algorithms.
Perhaps the best example of this is the socalled kset problem
of Erdős, Lovász, Simmons, and Straus, which is more than
thirty years old. Given n points in general position in the plane,
what is the maximum number of ktuples that can be separated from
the remaining nk points by a straight line? After almost twenty
years of stagnation and ten years of slow progress, in the past two years
Dey and Tóth achieved two breakthroughs by substantially improving
the best known upper and lower bounds, respectively.
The kset problem belongs to a newly emerging discipline, geometric graph theory. A geometric graph is a graph drawn in the plane such that its vertices are points in general position and its edges are straighline segments. The first result on geometric graphs was proved almost seventy years ago by Hopf and Pannwitz: if a geometric graph has no two disjoint edges, then its number of edges cannot exceed its number of vertices. According to Conway's famous Thrackle Conjecture, the same assertion remains true for graphs drawn by (not necessarily straight) continuous arcs with the property that any two of them have at most one point in common. Many recent results in this area are relevant to proximity questions, bounding the number of incidences between points and curves, designing various graph drawing algorithms, etc. The aim of this workshop is to explore the consequences of the new results, and to discuss their extensions and some related questions. We plan to bring together many of the researchers who contributed to the development of this area. 

For further information please visit the websites: http://dimacs.rutgers.edu/Workshops/indexcompgeom.html http://dimacs.rutgers.edu/SpecialYears/2002_CompGeom/ or contact János Pach at pach@cims.nyu.edu 