I've been visiting Dublin, Ireland (my first time here) for the Fifth William Rowan Hamilton Geometry and Topology Workshop at the Hamilton Mathematics Institute of Trinity College, where I spoke about hyperconvex metric spaces, finding optimal stars, orthogonal convex hulls, and embedding into the Manhattan plane.

It was a good conference, but a bit like stepping into a parallel world where everyone's evil twin does low-dimensional topology and geometric group theory: the workshop theme had the phrase "Computational Geometry" in it, but it's an Other Computational Geometry that really mostly means low-dimensional topology and geometric group theory; there's an Other David Epstein (spelled wrong) who does etc and was here last year; and there's an Other Kevin Wortman (not spelled wrong) who does etc and wasn't here, but whose name caused some confusion when I referred to the work of my former student Kevin Wortman. Still, my interests and those of the Other Computational Geometers have enough overlap that I think we all got something useful out of the experience.

I'm not going to recount all of the talks (especially because I didn't understand them all) but here are a few that caught my attention.

( Read more... )

Here are the slides from my talks at WADS and those of my co-authors:

• On the approximability of geometric and geographic generalization and the min-max bin covering problem (slides and talk by Mike Goodrich; also with Kevin Du and George Lueker)
• Orientation-constrained rectangular layouts (slides and talk by Elena Mumford with her usual artistic flair)
• The h-index of a graph and its application to dynamic subgraph statistics (with Emma Spiro)
• Optimal embedding into star metrics (with Kevin Wortman)

I just returned from WADS, formerly the Workshop on Algorithms and Data Structures but newly renamed to be the Algorithms and Data Structures Symposium, in Banff, Canada. At the conference dinner, we learned that the organizers originally intended this to be a true workshop, with 30 or so participants, but it was never that small, and the new name recognizes that. Banff National Park is beautiful; I arrived two days early with my wife Diana so that we could do some sight-seeing, and I'll be posting some photos of that part later when I catch up on my postprocessing.

( Read more... )

I just returned from Montpellier, France, where I was invited to speak at WG 2009, the 35th International Workshop on Graph-Theoretic Concepts in Computer Science.

This was my first trip to France, and Montpellier was a very charming place to visit. It is in the south, and though not quite on the Mediterranean itself it has a very Mediterranean feeling. The conference organizers put together an interesting and educational excursion for us in which we learned some of the local history by visiting three local landmarks (the opera house, an old pharmacy, and the top of the gateway arch) and drinking a different wine in each. We learned that Montpellier is a new city for France, being only a little over 1000 years old, but it is home to one of the oldest medical schools in Europe. It's on the old pilgrim trail from Rome to Compostela, markers for which run through the town, and although the language is no longer spoken in the area there are several inscriptions for tourists written in Occitan. The nearby mountains were a refuge for the Cathars when they were persecuted by the Catholics, and there are many open squares in the city due to the monasteries and other buildings that were torn down in the French revolution. My hotel was on one side of the old quarter, now mostly a shopping district, and the conference was in an old movie theater on the other side of the quarter, so I had a very pleasant walk every day to the conference (only getting lost twice), and my bad high-school French was enough to get by with the people who didn't or wouldn't speak English (rather more of them than I've encountered in other parts of Europe).

The conference itself is about graph algorithms, both for problems on arbitrary graphs and (a larger fraction of the papers) for important special classes of graphs. There were too many interesting talks to describe them all in detail, so let me just mention a few.

( Read more... )

All in all, a good conference, and one I would attend much more regularly if only it weren't so far away.

I just returned from a pleasant post-SoCG visit to Bettina Speckmann in the Netherlands. While there, she presented me with a copy of Metroville, a puzzle based on confluent drawing. (Image below stolen from the manufacturer's web site.)



Metroville consists of a game board with nine rotating pieces on it, each containing a section of train track with turns and junctions. The pieces can be permuted to form eight different "cities", and for each city there are eight puzzles, in which one must rotate the pieces so that the resulting configuration of track can allow a train to pass through a given sequence of cities in order without reversals.

I haven't worked out the details, but I'm pretty sure that larger versions of the game would be NP-complete (that is, it should be NP-complete to test, for a fixed city, whether there exists a set of rotations that allows a given train route to work) by a reduction from 3-SAT very similar to the one in my Phutball paper in which the train zigzags horizontally across the board through tracks representing variables and then zigzags again vertically through tracks representing clauses.

Regardless, it's a fun puzzle. Thanks, Bettina!

Also, slides from Elena Mumford's talk on area-universal cartograms (my SoCG paper with Bettina, Elena, and Bettina's student Kevin Verbeek) are now online.

The 25th ACM Symposium on Computational Geometry just finished yesterday. Suresh has already reported on the pre-conference historical review of computational geometry, but I thought I'd mention a few highlights of the conference itself.

( Read more... )

All in all, a good conference.

Why has it taken me so long to figure out that Richard Lipton has a blog? Anyway he has a great recent post, starting out as a reminiscence about how theory talks used to be given and segueing into the still open and still very interesting question of how to compare the lengths of two polygonal chains exactly and efficiently. For some more geometric computing flavor, he also has another recent post on Rabin's randomized linear time algorithm for finding closest pairs.

I've now put my photos from Volker Strassen's Knuth Prize lecture at SODA online. I've also uploaded two of them to Wikimedia and used them to illustrate the Wikipedia articles for Strassen and the Knuth Prize; if anyone has a need for a freely-licensed version of any of the other photos, I'd be happy to upload them there as well.

I already have something of a tradition of recording limericks that people have included in their technical talks, so, for the record, Strassen's was:

An E.T. residing on Vega
determined the size of ω.
  In Praha, at night,
  he told me that quite
positively ω was nega....

In the following slide, he encoded a conjecture that ω (the exponent in the time bound for matrix multiplication) is strictly greater than two into another poem. Fortunately, the quality of the poetry provided a lower bound, rather than an upper bound, on the quality of the rest of his talk.

The slides from Elena Mumford's talk at SODA on our paper, “Self-overlapping curves revisited” (arXiv:0806.1724) are now online, including a few she skipped in the presentation.

Several people asked us the same two questions afterwards. First: how did you make such beautiful drawings? I can phrase it like that without fear of immodesty because Elena made the drawings, by hand with colored pencils, and then scanned them. Her colleagues at Eindhoven told me she also had some nice large 3d models made out of semitransparent plastic that would have made an interesting addition to the talk, but unfortunately she didn't bring them.

The second question we were asked is what applications we had in mind. The short answer is that this is a theory paper that isn't trying to be applied, but after the talk Yusu Wang discussed with Elena an application involving finding similarities between pairs of curves (one of Yusu's two SODA papers involved using Fréchet distance for this sort of comparison). Unfortunately I'm not sure of the details of the application. More generally, beyond the specific results in the paper itself, we think that one of its important contributions is the definition of a generalized terrain as a surface such that every point has a neighborhood within which the surface is a terrain. There should be many more problems in which these surfaces can be applied, and we tried to convey that in the talk slides by the images of real-world spiral ramps forming surfaces of this type that we found on Flickr. Sadly, we didn't end up using another photo we found, of the generalized terrain formed by a giant helicoid potato chip (or as Elena would call it a crisp), perhaps because it didn't have the proper salt-and-vinegar flavoring.

• Bernard Chazelle's talk “Natural Algorithms” (describing a convergence time for a simple model of bird flocking that is both upper and lower bounded by a logarithmically tall tower of powers of two, if I remember correctly) was quite entertaining and played to a standing-room-only crowd, and I heard that some latecomers weren't able to get in at all. The system we've had at some SODAs of having meeting rooms of varying sizes and guessing which talks would be better attended had some drawbacks, but the present Harrison Bergeron system of making everybody equal does too.

• I'm sorry to have missed the first data structures talk, on pairing heaps, due to said Chazelle talk. But the rest of the data structures session (including the one with Chazelle's name in the title, in a different session from Chazelle's own talk) was good. The triple threat of John Iacono, Erik Demaine, and Mihai Pătraşcu presenting their equivalence between a geometric problem (augmenting a point set so there is no rectangle with only two opposite corners present) and dynamic optimality for online binary search tree data structures was again particularly entertaining and standing-room-only.

• Gary Miller roped me into taking photos for Volker Strassen's Knuth Prize lecture, in which he described some of his major past results. (Someone who understands it better than I should add his law of the iterated logarithm to his Wikipedia article, which is in other respects as well quite bare-bones.) So photos will be appearing here shortly, and I'll likely add them to the Wikipedia articles as well. But they won't be appearing until I get access to a compact-flash card reader (as I left mine at home) and in any case will probably have to wait until after the conference when I have time to sort through them and postprocess them. I ended up using both my own Canon 40D and 50mm prime lens (I didn't bother to bring a zoom this time) and Erik Demaine's brand-new 5D mk II and 24-105 zoom; the 5D is a sweet camera. Thanks, Erik!

• Jeff has posted the annual drinking game rules. Sadly I did not partake so I have no details to report.

So last week I attended the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), which was held here in Irvine. It's a little problematic attending a conference in one's own town — too easy to schedule other conflicting activities — but I still went to much of it, as well as getting some research done with attendee and renaissance man extraordinaire Matt Dickerson (about which more some other time).

( Read more... )

I'm back from Graph Drawing 2008 in Crete, and too jet-lagged to blog coherently about it, other than to say that on the whole it went well -- interesting talks, too much tasty seafood and raki (though the lack of beverages at the lunches, similarly to WADS 07, was a minor annoyance), a spectacular location (which I somehow failed to take any photos of, but there should eventually be plenty of others on the conference site), good company, and even some progress on the research problems I was thinking about during the conference.

My own talk slides are now online: The topology of bendless three-dimensional orthogonal graph drawing and Isometric diamond subgraphs.

This week, I'm in Karlsruhe (again), where I've been attending the European Symposium on Algorithms and the associated workshops of ALGO 2008.

( Read more... )

ETA: The Lund story.

A mouse just told me that all the talks from the International Conference on Topological and Geometric Graph Theory, just held in Paris, are available online. Nearly a full day of video, when you put it all together.

Sadly, you'll need a Windows PC to view it all. It's in Windows Media format, and a more recent version of Windows Media than will run with the last version of the browser plugin available for OS X. And it's a streaming video so it's not obvious to me how to download the files and run them through VLC instead. Let alone somehow get them onto my new big iPod...

The rigamarole needed to get this working on a Mac:

( Read more... )

I spoke today about graph drawing at a seminar in our School of Social Sciences. They're very mathematically sophisticated over there (and more interested in combinatorics than our mathematicians are) but it was still mostly not a very technical talk — I just showed lots of pretty pictures and used them to motivate some thoughts about how I think graph drawing should be done. Slides here.

Early in the talk, I included a bit of an ad for the annual graph drawing conference, so let me do that here too. Graph drawing! Crete! September! The submission deadline is May 31, and the call for papers may be found at http://www.gd2008.org/.

I just returned from a very pleasant several-day visit to Tucson, at the invitation of Stephen Kobourov, to visit him and Alon Efrat. I spoke Wednesday morning about xyz graphs; my talk slides are here.

Wednesday afternoon, we visited the Sonora Desert Museum, and then took a short (one hour) hike into Saguaro National Park, where Stephen showed me some petroglyphs at a site he knew of. We had been planning to do this Sunday, but it rained that day, after which the weather was beautiful. Photos here and here.

I realize it's not exactly day 3 anymore, and it's all a bit of a blur by now, but I thought I'd finish my reporting of the conference regardless. Besides, my flight is delayed so I have plenty of time to write, I'm procrastinating on making slides for my next talk, and it's a good excuse to plug my SODA talk slides and my book, especially since Springer mysteriously failed to do the latter at their exhibit table.

( Read more... )

For more on ALENEX/ANALCO and SODA, see my previous entries (I, II, III), Suresh's (I, II, III), Michael Mitzenmacher (I, II), and Hal Daume.

Let me explain... no, there is too much. Let me sum up.

( Read more... )

My iPod's randomizer this morning decided to treat me to some Metasciences and Casiotone for the Painfully Alone. All it needed, I thought, was some Say Hi To Your Mom (of which I have plenty) for the nerdy music trifecta to be completed. So I was looking forward to tonight's concert by Lady X and the Positive Eigenvalues, Christos Papadimitriou's band, for another hit of nerdy music. My (excellent) dinner ran long, though, sadly, so I had to miss it. I hope those who attended had a good nerdy time.

( Some of the talks )

My usual pattern here is to start with high hopes of several long complicated blog posts, and then get more terse and less frequent as the conferences go on and I get more sleep-deprived. So don't count on this continuing...

( Read more... )