+

I just added a new article to Wikipedia on indifference graphs (also known as unit interval graphs or proper interval graphs): the graphs formed from sets of points on the real line by connecting every two points whose distance is less than one.There are many papers on algorithms for going from the graph to a geometric representation in linear time. The following method for the reverse problem, going from the set of points (or equivalently unit intervals) to its graph must be known, possibly in
[…]

+

As I promised earlier, here is the video for my talk on "structures in solution spaces" at the Conference on Meaningfulness and Learning Spaces last February.It was a wide-ranging talk, about learning spaces, distributive lattices and Birkhoff's representation theorem for them, rectangular cartograms, antimatroids, the 1/3-2/3 conjecture for partial orders and antimatroids, partial cubes, and flip distance in binary trees and point sets. It was also about an hour long, so don't watch unless you
[…]

+

Every year about this time, my campus holds a spring celebration, with all the student organizations setting up pavilions in the park to sell food and advertise for new members, with the creative anachronists bashing each other with padded swords, and with a car show. Why a car show? I don't know, but I always enjoy seeing the variety of shapes and colors compared to today's mostly-the-same boxes. My favorite this year was a 1950 Chevy Fleetline, found rusting in a swamp in Tenessee; after a […]

+

When I last saw Tetsuo Asano, he was giving a research talk at WADS, and openly worrying that it might be his last one. We all thought it was because of mandatory retirement (still legal in Japan). But, it turns out, no. Instead, he's the new president of JAIST. Congratulations, Tetsuo!I'll probably miss SoCG, in Kyoto this year, but for those who will be going, there will be an associated workshop in honor of Asano's 65th birthday.

+

The power of two choices in load balancing is well known: If one throws n balls independently at a similar number of bins (as in hash chaining), some bin will typically have Θ(log n/log log n) balls in it, but if one draws two random bins for each ball, and places the ball greedily into the less-full of these two bins, the maximum load will be much smaller, Θ(log log n). And if one clairvoyantly chooses which of the two bins to place each ball into (or uses […]