From number crunching to crunching shapes

So, when I present our work on certain old, fundamental geometric problems, such as those discussed below, some colleagues exclaim that these must already be solved! The difference is that our group at University of Athens focuses on exact computation - unlike most existing methods - and this makes a huge difference in certain applications.

One such problem is as follows: given a set of shapes, partition a plane into regions, each corresponding to that part of the plane which is closer to one shape than to any other. This problem has been studied for at least a century now, starting with very simple shapes, such as points and line segments. Next, complex shapes were considered, but with one crucial assumption: that we allow some kind of approximation. This implies that computations need not be 100% exact, just as an ordinary calculator will "round off" if there are too many decimal digits. A second simplification is to approximate the given shapes by simpler ones. For these simplified problems, algorithms do exist for computing the desired partition. But we have not solved the original problem exactly.

You may object that in "real life" a small approximation will not hurt. Not if "real life" is truly real! Nobody can guarantee that a future application may not require a precision higher than that available from an approximate solution. Upgrading to a higher - but still fixed - precision will not necessarily do, because a yet harder instance may come up, requiring even better precision. The issue becomes of paramount importance when dealing with critical applications, be it on the surgeon's table or in the cockpit. Hence, our decision to attack geometric problems in an absolutely exact manner.

But how to go about it? My students and I gambled on an approach even older than the geometric problems we were solving: to use algebra to represent the geometry, in a way reminiscent of Cartesian coordinates. Linking geometry and algebra goes back to ancient Greece and offers an exact representation of complex shapes, thus transforming geometric manipulations to algebraic and numeric operations. We all know that computers are great at number crunching, right? So now, let them crunch some shapes!

Yet, a new challenge came up: the resulting equations were huge. Take the problem of plane partition above. When the given shapes are ellipses, we end up with an equation that contains all powers of the unknown variable up to 184. Our high school teachers taught us how to compute the solutions to equations of degree 2. But in University, math majors can prove that there exists no solution formula when the degree reaches 5 and beyond. So how could we handle 184? Computational algebra came to the rescue. By adapting powerful algebraic techniques, we are now able to solve the plane partition problem; an illustration is given above with 16 ellipses. The time required is proportional to the number of ellipses, requiring about one second per ellipse on an ordinary computer. More impressively, our software is faster than if we had approximated the ellipses by polygons or by a sequence of points! In short, we achieve exactness without sacrificing speed.

What is the impact of this success story? First, it is personally very fulfilling to witness the effectiveness of a long series of theoretical work - in which Europe is a world leader - concerning geometric and algebraic algorithms. Second, in a more practical vein, such algorithms, and their extensions to higher dimensions, are critical for shedding light into important problems like the study of how molecules bind to each other, a central question in the emerging field of structural bioinformatics. This is intimately related to the major challenge in computational molecular biology of understanding three-dimensional structures and their interactions in forming compounds. The so-called docking of small enzymes to larger molecules in the blood is the way that many drugs act. A dangerous virus becomes neutralized when an appropriate molecule docks itself on it. Unfortunately, finding the proper combination may take from several months to a few years, and the contemporary lab-based procedure is very expensive. Computer-aided drug design is our effort to accelerate and simplify this process. This involves exact geometric computations, such as partition diagrams in 3 dimensions generalizing the problem described above where, for instance, atoms may be represented by spheres and sets of atoms or small molecules may be represented by ellipsoids.

So, let me disagree with Pablo Picasso after all. Computation, besides providing answers to (hard) problems, has shaped today's scientific thought. Without computers, research would take a different tack on several problems. Computers are the modern lab, where mathematicians and biologists, in conjunction with physicists, doctors and engineers, meet to experiment and shape a new way of doing science.

For information on our group see: http://erga.di.uoa.gr/ For information on our software for plane partitions see: http://www.ima.umn.edu/nuggets/voronoi.html