### Two Talks Today

02Aug07

I got to see a couple of good talks today by other students at Waterloo.

First, my roommate Igor gave his Master’s thesis presentation. His talk was centered around finding dominating sets in Kneser graphs, and generalizations. Many of his results were summarized in a table regarding upper and lower bounds. A single entry of the table required a complicated case analysis (namely, that a dominating set of the 9:3 Kneser graph has at least 7 vertices)… it reminds me of the search for Ramsey numbers, and I was glad to hear during the talk that most of the other hundred-or-so entries didn’t each require so much attention; otherwise I doubt that I would ever have seen him leave his room…

The second talk was by Mustaq Ahmed of the computer science department. The basic problem he considered is pretty natural: given a terrain, what is the shortest path from point A to point B that never goes uphill? For example, what is the shortest path to ski down a mountain, or the minimum length of aqueduct needed for irrigation from the a glacier to the fields below. To analyze the problem one models the terrain by a polyhedron (e.g., planar faces joined at straight lines); the talk had lots of interesting snippets dealing with convex optimization, approximation algorithms, and Steiner points. There’s a related problem that appears to be very popular:

You are “the amazing mr. sticky-fingers,” and you are sitting in one corner of a 10x10x10 metre room. What’s the shortest path (including climbing walls and/or ceilings) to get to the opposite corner (the one where the far two walls meet the ceiling)?

Anyway, the answer to this problem is pretty nice, but it is apparently unknown yet whether exact solutions for similar “downhill-only” problems have a closed form.