Geometry and Combinatorics

Computational geometry deals with algorithms on geometric objects.
This is a statement that most computational geometry folks can agree on. It is also a statement that encapsulates the primary source of tension and profundity in this field, namely the interplay between the discrete (algorithms) and the continuous (geometry).

Algorithms take as input (and generate as output) discrete entities; at the most basic level strings of 0s and 1s. A geometric entity such as a line or point cannot always be represented so concisely. It would not be an exaggeration to say that it is this conflict that has inspired many of the techniques, theories, and areas of computational geometry.

The most immediate effect has been practical. As anyone who has tried to implement a geometric algorithm quickly realizes, issues of precision and robustness are not dry academic concerns when your convex hull starts looking like spaghetti ! Some wonderful work has come out of the problems in implementing geometric algorithms; robust computing, exact polynomial evaluation, how to determine the precision needed for a computation... In fact computational geometry has stood out among all algorithmic disciplines in its attention to issues of implementation.

There is a deeper level of interplay between the discrete and the continuous in geometric algorithms though. In a sense, some of the best theory in computational and combinatorial geometry has come from trying to abstract out a combinatorial structure that describes a geometric setting, and then using that combinatorial structure to prove a desired result. The trick has always been to take what is needed from the underlying geometry to construct an appropriate combinatorial space to work with.

Examples of this abound. Simple results on arrangements of lines can be proved merely by observing that the lines and their intersections can be represented as a planar graph. The Koebe-Andreev-Thurston theorem characterizes planar graphs in terms of contacts between circles.
Many theorems on arrangements use only incidence axioms, and thus are true in the projective plane, which in turn can be represented combinatorially.

What is so fascinating about this is that you can get deeper and deeper into the geometric structure, and new combinatorial structures keep emerging. If projective spaces give you a lower bound (and they often do), then it tells you that you need more than just incidence relationships. If you need to use convexity, then Helly's theorem (and Radon's theorem and others) gives you a nice way of handling convexity combinatorially. If combinatorial set systems defined on geometric objects are giving weak bounds, then VC-dimension arguments give you a way of capturing geometry in a combinatorial way.

The relationship goes both ways; planar graphs and interval graphs are but two examples of rich graph classes that are defined geometrically. Results in coding theory come from arguments about sphere packing. One of the great breakthroughs in complexity theory, Mulmuley's proof separating P and a slightly restricted variant of NC, uses geometric and topological methods.

Ultimately, this is what I enjoy about computational geometry; it provides a playground for rich algorithms, and the means to utilize tools from some of the deepest areas in mathematics. Truly, sitting in this mean is no mean pleasure.....