Tuesday, July 30, 2019

Tribute to Godfried by Joe Mitchell

I can honestly say that if not for the influence of Godfried, I may never have discovered the beauty of computational geometry. As a graduate student at Stanford, in the very early 1980's, I was often standing in the faculty hallway in Terman Engineering, and, there on the orange carpet would be a stack of technical reports from McGill University, just outside George Dantzig's office. Almost all of them were recent papers of David Avis and Godfried Toussaint. I wondered what this topic "computational geometry" was all about, and one evening I carried off a stack of reports to borrow and peruse. I made an immediate connection to the problems Godfried and his collaborators were discussing, as they were very closely related to problems I was discovering in the robotics lab at HRL, where I was working on coding algorithms for route planning. How exciting that there were others blazing a trail in this new area!  I immediately wrote to Godfried at McGill and asked to be put on the mailing list (yes, physical mail) for his technical reports, and I started collecting those red-jacketed reports (all of which I still keep on my shelf). I felt very encouraged by finding this common bond to the "father of computational geometry". 

I met Godfried in person not long afterwards and was immediately taken in by his friendly and enthusiastic encouragement. He invited me to a Bellairs workshop and I came to know him as a colleague, a host, and a friend. Godfried and I had another, less publicly known, connection too, as we both had lived in Oklahoma: he did his BS at the University of Tulsa, and I went to high school in Oklahoma, just north of Tulsa. Surely, though, neither of us would ever claim to be an "Okie"!

Godfried is immortalized in all of the CG classes I teach, as I tell stories about his clever contributions and conjectures, his influence on the establishment of the field, and the ever famous "Godfried's Favorite Polygon"  -- the nonconvex hexagon (pseudotriangle) that all of my students respect for its role in formulating counterexamples.

Each year on this very date I would be writing to Godfried to exchange our annual birthday wishes, both of us sharing the bond of a late July birthday, just one week apart. I surely did not imagine that last year's birthday wishes would be our last such exchanges.

Let me share Godfried's historical reflections he sent me recently when I was researching the early days of the teaching of computational geometry, for the workshop (Educational Forum) we had at SoCG'18.
Godfried wrote of the "early days" of the field:

"I got started doing research on computational geometry in 1974. The CS department (School) was started at McGill in 1971. It was only a graduate school. George Marsaglia was that Head. He was a (the?) world expert on random number generation. Donald Knuth would come and visit us frequently to discuss random number generation with George for inclusion into his next volume.

I was teaching pattern recognition using Duda and Hart’s text which contained many geometric problems without algorithms. Having switched from Electrical Engineering (all my 3 degrees) to CS I thought I should include algorithms in my course. The convex hull seemed like a beautiful place to start. Knuth had the reputation of being an encyclopedia for algorithms. So in 1974 on one of his visits to McGill I asked him if he knew of any convex hull algorithms. He instantly replied that there was one algorithm published in 1972 by Ron Graham. I looked it up, loved it, saw how it could be improved to run faster on the average, and included it in my pattern recognition lectures. So I first started teaching computational geometry in my pattern recognition course in 1974. The amount of CG in the PR course increased rapidly. In the late 70’s David and Vasek Chvatal joined McGill and I learned about the art gallery theorem. I thought of making the guards move, and this started collaborations with David on CG research (visibility) that led to the introduction of the CG courses at around 1980. The exact dates can probably be retrieved from McGill records, as David points out."

I will miss you, dear Godfried. We all miss you.