Despite having half of one day cancelled because of the worst typhoon in ten years, this year's Japan Conference on Discrete and Computational Geometry was a rousing success. There were four ddays of talks and over 150 attendees, putting this conference on par with some years of SoCG.

Probably the most fun talk was given by Godfried Toussaint, who spoke about “The Geometry of Musical Rhythm”. Godfried described several interesting combinatorial and algorithmic problems involving rhythms, viewed as (possibly circular) bit vectors. For example, the *swap distance* between two binary necklaces of length *n* both with the same number of 1s, is the number of swaps of adjacent bits required to transform one necklace into the other. How quickly can this distance be computed? Godfried liberally illustrated his talk with classical Latin, African, and Eastern European rhythms. (I think he might have inadvertently played a rain dance or two.)

JCDCG was actually held in honor of János Pach's 50th birthday. (On the last day of the conference, he worse a T-shirt that read “Wham-O: 50 years of fun!”) At the reception, after describing his movie career and refusing to demonstrate his Transylvanian folk dancing skills, he thanked his hosts, friends, and colleagues with the following priceless comment.

There is something in common between Hungarian, and Japanese, and Hispanic mathematics. We can start a paper by saying “Let *P* be a set of *n* points in the plane...” and no one will ask us, “Why? *Why?*”

János gave a great invited talk on unit distances, directed graphs with forbidden subgraphs, and 0-1 matrices with forbidden patterns of 1s. He ended his talk with the following result, which he proved with Gábor Tardos: If *M* is an *n×n* 0-1 matrix that contains no orthogonal cycle with positive winding number everywhere, then *M* has at most O(*n*^{4/3}) 1s. One consequence of this theorem is that any set of *n* points in the plane contains at most O(*n*^{4/3}) unit-distance pairs. (This was already known, but by very different proofs.)

Jonathan Shewchuk described his new method for repairing near-Delaunay triangulations, which he calls “star splaying”. The obvious method for doing this involves performing bistellar flips at locally non-Delaunay simplices. Unfortunately, this simple method is not proven to work in three and higher dimensions, and is proven not to work in five and higher dimensions. Jonathan's brilliant idea is to allow the triangulation to be temporarily inconsistent—every vertex stores a description of its local neighborhood, but those neighborhoods may not all describe the same triangulation. He then describes a sequence of moves similar to bistellar flips, and shows that they always terminate in the Delanuay triangulation, in O(*n*) time under some “realistic” assumptions about the starting triangulation.

Unfortunately, one of the most interesting papers that was accepted to the conference won't be presented, because the authors decided to stay ~~dry~~ home. Franz Aurenhammer and Hannes Krasser have *finally* defined a useful and consistent generalization of pseudo-triangulations to three and higher dimensions, building on their earlier work wiith Oswin Aichholzer and Peter Braß. I'll try to get a copy of their paper and say something about it here later.

The next JCDCG will be held in mid-June 2007 in honor of Jin Akiyama's ~~60th~~ third 40th birthday.

## Recent Comments