Two of my papers have been accepted to this year's Algorithms and Data Structures Symposium, known for short as WADS and held every two years in Canada (this year's Canadian location: Brooklyn). The proceedings are due very soon, and (as usual) not everything we wanted to write about fit into the conference's 12-page LNCS proceedings format. So today my coauthors uploaded to the arXiv longer versions of both papers, so that instead of writing "see the appendix" (as one does when submitting a paper) we could write "see the arXiv".

One of the two is on a subject that's gone a bit out of fashion since its peak in the early 1990s, and something that I didn't really work on myself when it was fashionable: competitive analysis of online algorithms. The actual motivation of my paper "Tracking Moving Objects with Few Handovers" (arXiv:1105.0392, with Mike Goodrich and Maarten Löffler) comes from a different fashionable topic, sensor networks, but it's easier to describe using something familiar to many of us, cell phones. Depending on your carrier, you are likely either painfully aware or blissfully unaware of the fact that your cell phone gets its service from towers distributed throughout the regions you live in, work in, and drive through, and that each tower can only cover a limited area. If you phone while you drive (as you should probably not be doing), your phone may have to change from one tower to another mid-call, and it may have a choice among several towers to switch to. The best tower to switch to is the one that you will remain reachable from as long as possible, but without knowing the future your phone can't determine which one that is. What we show is that, if the regions of coverage have small ply (your phone can reach only a small number of towers from any one point) then it can make these decisions in such a way that the number of handovers is almost as small as in the ideal solution. In some sense, then, this is a successor to a couple of my earlier papers, "A Deterministic Linear Time Algorithm for Geometric Separators and its Applications" (SoCG 1993 and Fund. Inf. 1995, with Miller and Teng), and "Studying (Non-Planar) Road Networks through an Algorithmic Lens" (ACM GIS 2008, with Goodrich), which both show that the same property of small ply leads to efficient algorithms in completely different application areas.

My other WADS paper is "Adjacency-Preserving Spatial Treemaps" (arXiv:1105.0398, with Kevin Buchin, Maarten Löffler, Martin Nöllenburg, and Rodrigo Silveira). A treemap is a hierarchical partition of rectangles into smaller rectangles; what we mean by a "spatial treemap" is one in which the rectangles at different levels of the hierarchy have some geographic or at least geometric meaning. For instance, once could imagine forming a treemap in which the outer level represents the US, it is divided into 50 smaller rectangles representing states, and each of those is further subdivided into even smaller rectangles representing counties. Of course, it would probably be a good idea to make the relative positions of the rectangles at each level of the subdivision approximate the relative positions of the spatial regions they represent. My paper "Orientation-Constrained Rectangular Layouts" at WADS two years ago with Elena Mumford was motivated by the same problem of making rectangular subdivisions have relative positions that match those of the corresponding regions, but with only a single level of subdivision. As I wrote at the time, it did so by reducing the input to a partially ordered set that encodes all possible rectangular subdivisions and by translating the problem into a search for a constrained subset of the partial order. Here we use the same partial order, but instead translate our problem into one of finding a minimum weight closure in it, giving us some freedom to minimize the number of points where the subdivision doesn't look the way we want instead of just giving up when perfection is unattainable.