I realize that everyone else in the theoretical CS blogosphere is excited over something to do with P and NP, but I'm in Winnipeg for CCCG this week, surrounded by geometers and geometry.

David Avis gave a very entertaining invited talk on cut metrics and cut polytopes, the Paul Erdős Memorial Lecture — apparently, the first invited talk at the first CCCG was by Erdős, and since then one of the qualifying characteristics of the first invited speakers at subsequent CCCGs is that they have to have Erdős number one. For this CCCG, they seem to have added a new requirement, that the invited speakers all have to be named David, and even the introduction to Avis' talk was by another David (Rappaport). However despite the official name for the talk, Avis dedicated his talk to the memory of Hazel Everett, who recently lost her struggle with cancer.

Avis mentioned an open problem in metric graph theory that was new to me, but quite interesting: Kusner's conjecture, that embedding the complete graph \( K_n \) isometrically into an \( L_1 \) space requires \( \lceil n/2 \rceil \) dimensions. For instance, \( K_6 \) can be embedded into three-dimensional \( L_1 \) space as the vertices of a regular octahedron, but \( K_7 \) already requires one more dimension. The proof that \( K_5 \) requires three dimensions is trivial (at least, it is if you know about tight spans), the proof that \( K_7 \) requires four dimensions is due to Bandelt, Chepoi, and Laurent [DCG 1998], the proof that \( K_9 \) requires five dimensions is due to Koolen, Laurent, and Schrijver [Designs, Codes, and Cryptography 2000], and beyond that only weaker bounds are known.

Among the contributed talks, I especially enjoyed the ones by Vogtenhuber et al on blocking Delaunay triangulations (given \( n \) red points, how many blue points do you need to add to ensure that the Delaunay triangulation of the augmented point set has no red-red edges?) and Charlton et al on "ghost chimneys" (a famous phenomenon in Japan according to which the four smokestacks of the Senju Thermal Power Station are seen from some angles as three, two, or one smokestack; in general, for which intervals of integers does there exist a planar point set that can be viewed from different angles in such a way that the number of visible points is any number in the interval?).

I was hoping to enjoy a talk by Rahmati and Zarei (or, actually, since there were problems for several Iranians attempting to get into the country, by a non-author of their paper) on the number of combinatorial changes that the Euclidean minimum spanning tree can undergo, if the points that form the vertices of the tree are moving along paths of the form \( (X(t),Y(t),Z(t)) \) at time \( t \), where \( X \), \( Y \), and \( Z \) are all bounded-degree polynomials of \( t \). They claim a near-cubic bound on the number of changes (improving an easy \( O(n^4) \) bound: each pair of possible EMST edges can swap into and out of the EMST a constant number of times) but I think their proof is just wrong. It is based on a "theorem" that, if you have \( n \) functions, each of which is a polynomial that is defined only over some subset of the real line, and if you take the pointwise minimum of the functions that are defined at any point, and if the boundary points of the sets within which each function is defined are all points where it is not the minimum, then you get a Davenport-Schinzel sequence with near-linear complexity: you can fill in the missing gaps of the functions by sufficiently large function values to get totally defined functions without changing the pointwise minimum and then use standard Davenport-Schinzel bounds. Unfortunately what you do change when you fill in the missing gaps in the functions is the property that each pair of functions crosses each other \( O(1) \) times, so it's not true that the pointwise minimum is a Davenport-Schinzel sequence. In fact it's easy to find counterexamples, sets of \( n \) partially-defined linear functions whose lower envelope has complexity that is a superlinear power of \( n \). I don't know whether their bound on the EMST itself is true or false, though.

More tomorrow, if I have the energy after my own talk...