Guest Post: Distinct distances, and the use of continuous mathematics in discrete geometry.

Nabil Mustafa specializes in problems of discrete geometry, and has spent time on problems related to the distinct distance problem. He offers a broader perspective on the new distinct distances result and related breakthroughts in discrete geometry. For a detailed breakdown of the Guth/Katz paper, see Terry Tao's latest opus.As usual, I take responsibility for any mistakes introduced in the editing process.

I think the days when the "Feynman method" was all that was needed to make progress on basic problems in Discrete Geometry are over. Recently there have been a slew of results which make progress on long-standing open problems in Discrete and Computational Geometry that use techniques from a variety of areas in mathematics: algebraic geometry, algebraic topology, complex analysis and so on.

This is wonderful news for the field. Though, two things to consider:

1. So far, apart from the kind of work going in "Computational Topology", this has mostly been a one-way street. There have been fewer cases of discrete and computational geometers going into topology, algebraic geometry etc. and making a similar impact there. Similarly, there are very few collaborations between mathematicians in other areas, and discrete geometers (ed: Mulmuley also argues that the GCT program will only come to fruition when this reverse direction starts happening)

2. From my experience, current graduate students, by-and-large, still seem to be stuck with the general outlook that "If I'm clever enough, and think hard enough, I can solve any problem directly". Such optimism alwayscheers me up. I used to think that too, but the more I learn about other areas, and as the recent work reveals power of techniques, it has become clear to me that it is misguided to think that. I would really advise students to take courses in algebraic topology, differential geometry and so on.

Below I list some such recent breakthroughs.

First-selection Lemma. 

 Given n points in $R^d$, can one find a point in "many" simplices spanned by these points ?

This has been studied for more than 30 years, with several partial results. The current best result was published this year by M. Gromov, which in fact proves a stronger topological  theorem, with better bounds than for restricted earlier cases. Matousek and Wagner have improved this bound slightly for 3D by improving a combinatorial part of Gromov's argument.  Gromov's argument is a complicated topological argument that I did not have the background to follow. J. Matousek gave a nice talk at the Bernoulli conference in September with the title "Also Sprach Gromov"!

2. Colored Tverberg Theorem. 

Let be disjoint subsets of , called colors, each of cardinality at least . A -subset of is said to be multicolored if for . Let be an integer, and let denote the smallest value such that for every collection of colors of size at least there exist disjoint multicolored sets such that  

The conjecture is that $T(r,d) = r$, and this was proved recently via topological arguments (for all $r$ such that $r+1$ is prime) by  Blagojevic, Matschke, and Ziegler (see Gil Kalai's blog for a detailed post on this). Matousek, Tancer and Wagner have translated this argument to a geometric proof. As they state in the abstract, "The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience."

3. Distinct Distances problem. 

The Guth-Katz dramatically improves the best known bound via techniques from algebraic geometry. Terry Tao has more details on this.

4. Joints problem. 

A joint is a point formed by the intersection of three non-coplanar lines in 3D. What is the maximum number of joints achievable by a collection of $n$ lines in 3D ? 

This was again solved by Guth and Katz via techniques from algebraic geometry. It was subsequently simplified wonderfully by Elekes, Kaplan and Sharir, and Kaplan, Sharir and Shustin.

5. Lower-bounds for eps-nets. 

It was very widely believed that for "natural"  geometric objects, eps-nets of linear-size should exist. Shockingly, Alon showed that an easy application of Hales-Jewett density version immediately gives a non-linear lower-bound for a simple geometric-system in the plane. While DHJ is a combinatorial result, it was first "proved by Furstenberg and Katznelson in 1991 by means of a significant extension of the ergodic techniques that had been pioneered by Furstenberg in his proof of Szemeredi's theorem". Like earlier proofs, it is possible to "de-ergodicize" it (the polymath project).

6. Regression-depth partitioning conjecture. 

(ed: see here for a description of regression depth - it's similar to halfspace depth)

Partial results were shown by Amenta-Bern-Eppstein-Teng in 2000. Recently almost proven by Karasev using topological techniques that I do not understand.

This is just a partial list, there are probably several others that I have missed.

What is computational topology ?

Jeff's post on his computational topology class (and the wonderful class outline), prompted me to write about something that I've tried to explain to people before.

Computational topology is arguably the hottest thing in SoCG-land right now, and has been so for a number of years (for curious folk, the "other" hot topic is high dimensional approximate geometry). But if you ask different people, you'll get different answers to the question "what is computational topology ?". I've even had to explain to local students why my computational geometry class is different from the computational topology class being offered. So here goes:

CT I: Using topological ideas to understand the 'shape' of data
This is the version of CT that has taken up the largest fraction of CT mindshare in the SoCG land. Dating back to work by Edelsbrunner and Mucke on alpha-shapes, the field now encompasses a range of ideas for extracting topological structure from data. New topological constructs that have come from this area include various notions of persistence, as well as related work on reconstruction, data smoothing, and visualization.

Afra Zomorodian's thesis (now a book) is a nice introduction to these concepts for a CS audience. Herbert Edelsbrunner is coming out with a book on this topic very soon (Jan 16, 2010! Mark your amazons!), and Valerio Pascucci teaches a class on computational topology at the U.

CT II: Asking computational questions about fundamental topological objects and concepts.
This is closest to the 'Computational X' flavor of work, where a computational perspective is brought to the study of X. There are many interesting problems here, and they have a nice discrete flavor that makes them 'friendly' for theoryCS folk. For example, computing the Betti numbers of a simplicial complex efficiently, or finding homotopy equivalent paths on a surface, or lots of work on graphs on surfaces.

I don't think there's a single book on this topic. JeffE has put together a fantastic course outline (with reading material), and there's also a great book on graphs on surfaces by Mohar and Thomasson. It's worth noting that some of the deeper tools in the Robertson-Seymour graph minor results take us into graphs-on-surfaces-of-large-genus land.

CT III: Using topological ideas in the heart of complexity theory.
Almost no one I know uses 'computational topology' in this sense, and there isn't a coherent and connected body of work to talk about as such. But there are some fascinating results at the core of complexity theory that rely on topological constructions. There's the algebraic complexity work of Yao/Steele/Ben-Or and others, showing that lower bounds for algebraic complexity of certain problems can be related to the sum of Betti numbers of associated surfaces. There's the Kahn-Saks-Sturtevant (and Chakrabarti-Khot-Shi) work on evasiveness of graph properties, and then the work (that I don't quite understand) on topology in distributed computing (that got Herlihy, Saks, Shavit and Zahoroglou the Godel Prize)

This is one of the reasons I think a course in topology (of some flavor, whether it be combinatorial, algebraic or point-set) should be required mathematical background for all theoryCS students.