EuroCG 2013 part 1

This post is about  the European Workshop on Computational Geometry, number 29. This year's workshop takes place in Braunschweig Brunswick, Germany. In case you are interested, there is a  book of abstracts ready for download.

Day 1

The first day had already some very interesting talks. For those of you who don't know, the EuroCG has parallel tracks, so unfortunately, I missed some of the talks. Here is a small selection of talks I found especially interesting (form my very personal perspective):

Adrian Dumitrescu, Joseph Mitchell and Paweł Żyliński. The Minimum Guarding Tree Problem. For a given  line arrangement in the plane Paweł presented an approximation algorithm for computing the minimum guarding tree. This tree is a subset of the lines, such that every line in the arrangement is visible by some point in the tree. The key idea, roughly speaking,  is to locate a triangle (brute force), for which an optimal guarding path is computed. Then peripheral edges are added to the path, which gives a guarding tree. Interestingly the guarding path problem can be computed in polynomial time, whereas the guarding tree problem that also allows line segments is NP-hard. Although the algorithm seems very neat, approximation ratio and running time are not very good. So the canonical open question is here to improve either one.

Mimi Tsuruga and Frank H. Lutz. Constructing Complicated Spheres. In this talk I learned about the Akbulut-Kirby sphere. This is a rather involved method for defining a family of 4-spheres. It is based on the group G=\langle x,y \mid xyx=yxy, x^r =y^{r-1}\rangle, for some r. Notice that this group is trivial. Now start with a 5-ball and add two handles, one for the generator x and one for the generator y. Then add 2-handles representing the paths given be the generators of G. The boundary of the result is a 4-sphere. In the presentation it was sketched how to construct  triangulations of such spheres. Actually the f-vectors of these complexes were not too big. The motivation for the work was the construction of complicated instances for homology algorithms.

Peter Brass. Selecting a Small Covering from a Double Covering. Given a double covering of the plane by unit disks. Can we always select a small subset of the disks that still forms a cover? It was shown that one needs to keep at least 1/2 of the disks and furthermore an algorithm for computing a cover with at most 3/4 of the disks was presented. The idea is to construct a Delaunay triangulation of the center points and then apply the 4-color theorem to find a large color class to remove.

The first invited talk was given by Konrad Polthier, from the FU Berlin. The talk was about some topics in geometric processing and discrete differential geometry. I liked the talk very much -  cool stuff. I am always fascinated by discrete differential geometry and there are many connections to computational geometry.  In particular, in both fields weighted geometric graphs (or more generally, geometric complexes) play a central role.

Business meeting

The business meeting started with a presentation of the usual statistics, followed by an advertisement for the next EuroCG, which will take at the Dead Sea in Israel. There were two bids for the 2015 EuroCG: Prague and Ljubljana. I must say that I liked both. Both locations promised to have a reasonable workshop fee. Prague was offering different options, so the first vote was on where to go in Prague. The vote actually didn't mattered since Ljubljana won the final vote. So 2015 EuroCG is in Slovenia.

Leave a Reply