ESA (along with ICALP) is one of the top two European conferences for Theory A. And probably since the ICALP deadline is typically between the SoCG submission and notification, ESA is the home of many of the best computational geometry talks. This year was no exception, with two "geometry" sessions, as well as many other geometry talks mixed in other sessions.
Another interesting pattern at ESA which makes it different to other algorithms conferences is the juxtaposition of theoretical and experimental work. The two tracks (A: Design and Analysis, B: Engineering and Applications) have separate submissions, but are not treated separately in the program. This leads to the fun game of trying to determine whether a talk was from track A or track B. Sometimes you are surprised when a talk starts with a nice theoretical results, and then the speaker presents several experiments to show the algorithm works well in practice, or mentions that it has already been added to CGAL.
I think this a great practice and should be considered by other conferences such as SODA or SoCG. For instance ALENEX talks could be mixed in with SODA talks. This would encourage more algorithms people to actually implement their algorithms, because it would allow them to apply to a separate track that would give more value to practical algorithms. How would this not be a positive for our community and its perception from other parts of computer science!
A couple of related data points: There were 56 track A papers and 10 track B papers, and both were accepted at a rate of about 25%.
The invited talks followed the theme of theory and practice as well. Michael Mitzenmacher began with a very clear talk explaining many open problems in Cuckoo hashing. He has been working on small variations in the algorithm that lead to large differences in performance, and then has been going to great lengths to explain why these variations make such a large difference.
Erik Demaine gave a very entertaining talk describing how a certain line of his work has alternated between art and the theory behind the art. He also performed a couple magic tricks, reminding us that most of the best magic requires lots of research, and sometimes algorithms!
On the third day, Noam Nisan presented a great high level view of how Google's TV ad auctions work. Much of his talk served to point out all of the important details often ignored in theoretical analysis, but critical in implementing such a system effectively.
I'd like to note a few papers I found interesting. This is not by any means an exclusive list, but just enough to give a taste of the (geometric) results.
Manuel Caroli and Monique Teillaud. Computing 3D Periodic Triangulations.
They presented a set of rules and an algorithm for computing triangulations in 3D which are periodic, that is they tesselate to fill an infinite space, but can be defined as a complex within a unit cube. These triangulations are needed for many simulations where it is difficult to deal with boundary conditions, so these can be avoided, but effectively having no boundary. Despite, the usefulness of these triangulations, they had not really been properly formally defined until this paper. Furthermore, their algorithm has been implemented and will soon me in CGAL, if not already.
Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson and Michiel Smid. Geometric Spanners for Weighted Point Sets.
They study Euclidean a size n point sets with weights so that a weighted distance between two points p and q is described
d_w(p,q) = w(p) + d(p,q) + w(q)
where d(.,.) is the Euclidean distance and w(.) is the weight of a point. This may, for instance, represent a potential road network where it takes w(p) time to get to the center of a city from its outskirts. This paper shows that typical spanner-type results can be found for a weighted point set using this weighted distance. I.e. in R^d a (5+eps)-spanner can be found with O(n) edges, and (2+eps)-spanner can be found with O(n log n) edges.
Sumit Ganguly and Christian Sohler. d-dimensional Knapsack in the Streaming Model.
This paper studies the d-dimensional knapsack problem, that is given a set of n items with a value v_i and a size in d-dimensions s_{i,1}...s_{i,d} find a set of items I with maximum total value such that for all j \in [1,d] that sum_{i in I} s_{i,j} <= 1. This problem is studied in the streaming model, which I found interesting, because they were unable to store the actual solution, because it might have linear size. Instead, they approximate the optimal cost and present a "template" solution where they give an approximate size of each element in their approximate solution I'.
Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan. Rank-Pairing Heaps.
A data structure paper, but for one very useful in geometry, among other places. This paper does not present any new results from a classical theoretical perspective. They describe a heap data structure which has the same running time for all operations as Fibonacci heaps. The contribution is that their data structure is considerably simpler than any variant of Fibonacci heaps, in particular, the structure of the heap never needs to be restructured. As an added benefit, their data structure easily outperforms Fibonacci heaps.Other notes (mainly from business meeting): See also Michael Mitzenmacher's post.
- There were 37 computational geometry submissions, 10 were accepted.
- Mark deBerg (next years track A chair), declared that next year the page size will be STRICTLY ENFORCED and he is not opposed to automatically rejecting papers if they play too many games to squeeze more text in the alloted number of pages. Be warned.
- next year, ESA 2010 (and ALGO) will be in Liverpool, England, and it was voted for ESA 2011 to be in Saarbrucken. Which won over a bid from Greece. (ed: HOW ON EARTH ? !!!!!!)
- Proceedings were not included in registration, but could be bought. On the second day, after politely asking Springer, participants were able to download a single pdf of the proceedings from a couple USB keys. This was very useful!, but it would have been better earlier in the conference.
Things I missed (I had to leave partway through the third day).
- - best student paper: Heidi Gebauer. Disproof of the Neighborhood Conjecture with Implications to SAT.
- - best paper: Christoph Dürr, Flavio Guiñez and Martín Matamala. Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard.
Attached workshops which are part of ALGO on Thursday and Friday:
