Friday, September 28, 2007

Kinetic spanners

Today and tomorow I'm in Eindhoven. I spent most of the day working together with Mark de Berg and Mohammad Abam on the problem of constructing kinetic spanners. That is, given a set of moving points in the plane can we maintain a t-spanner with a small number of topological changes, for a given constant t>1.

Previous work on this problem includes a paper by Karavelas and Guibas (SODA'01) and a paper by Agarwal, Wang and Yu (SoCG'04). Agarwal et al. show that a triangulation (the Delauany triangulation is known to have small dilation) can be maintained with n^2 * 2^{\sqrt{\log n \loglog n}} topological updates, if the trajectories of the input points are algebraic curves of fixed degree. We hope to be able to prove similar results for t-spanners.

We looked at this problem before but this time we were lucky to obtain some initial results so I'm looking forward to continue the discussion tomorrow.

Congratulations Mattias

Two days ago Mattias succesfully defended his thesis on "Approximation algorithms for geometric networks" in Lund. The faculty opponent, Marc van Kreveld, gave a very nice overview of the thesis. This was followed by lots of questions from Marc and the review committee consisiting of Rolf Klein (Bonn), Pavel Winter (Copenhagen) and Bengt Nilsson (Malmo). After the decision to accept the thesis there was a big dinner for family, friends and colleageus.

Monday, September 24, 2007

A Swedish PhD defence

I'm in Sweden for a few days to attend Mattias' PhD defence. In Sweden it works as follows. The thesis is published as a book a few weeks before the actual defence. It is then sent out to the committee and the opponent (more on that later) at least three weeks before the defence.

The actual defence is completely open, anyone can attend. Your colleagues are there together with friends and family. There is one opponent, in this case Marc van Kreveld. He will present the thesis which usually takes between half an hour and an hour. After that there's a short break which is followed by a long questioning session where the opponent starts, followed by the review committee. The committee has three members which usually ask a few questions each; however, I've been to defences where this part has been very long. When this is done, usually between one and two hours, anyone is allowed to ask questions. This is the part where some entertaining questions sometimes can be heard. This concludes the defence and now the committee, the opponent and the supervisors have a meeting to discuss if the candidate deserves to pass or not (although the supervisors are only there to observe and to give additional information to the group). In the Swedish system there is only pass or fail, however, the latter decision only happens at very rare occasions. The best part is the party afterwards where everyone gets drunk.

In Australia the system is very different. When you finish the thesis you send it off to a committee consisting of three reviewers. The reviewers will (hopefully) read it and return their report within six weeks (although I heard stories that it could take several months). The decision can be accept, accept with minor revision, accept with major revision or fail.

Even though the Swedish tradition might be slightly outdated I very much enjoy it. I like it since your PhD reaches a climax at the defence. I thought it was great to have friends, family and colleagues listening to what I spent all those years on. For some reason you don't get the same feeling in the Australian system when you send off the pdf file to the university administration.

Wednesday, September 19, 2007


In a previous post Tasos was complaining about the CATS registration fee (900 AUD), and claimed that the registration fee for IWOCA would be much cheaper. However, I just saw on the IWOCA website that the registration fee is 800AUD (650AUD for students)! I'll probably stay at home....

How can it be so expensive? Is it the transition from AWOCA to IWOCA?

Monday, September 17, 2007

Thesis types

At the moment three out of my four PhD students are about to finish their thesis. The thesis are all very different. Mohammad Farshi's thesis is quite technical and very foucussed on geometric spanners. Damian Merrick's is foucussed on metro map layout and maybe not as technical as Mohammad's, instead he uses several different approaches. Finally, Mattias Andersson's is much more dispersed and considers many different problems and techniques. Is any of the thesis more preferable than the others?

When I was a PhD student I remember that I was a strong advocate of Mattias' type of thesis (which was also my type of thesis). A new day, a new problem. But nowadays I would probably prefer Mohammad's type of thesis. I believe that there is an added research experience in closely focussing on one type of problems. It takes a long time to really understand a hard group of problems and the satisfaction of solving a problem that you've been working on for a looong time is hard to describe if you haven't done it yourself.

Are there many other types of thesis in CS theory? Do different countries require different types?

Tuesday, September 11, 2007

Dagstuhl - a meeting place

Dagstuhl is a great institution. I recently spent another week there and as usual it was pure pleasure. It is is an old castle that has been converted into a research conference centre. Almost every week for the whole year it hosts one or two workshops in various areas of computer science. The castle is quite secluded and there are no cities close by (it takes two hours to Frankfurt), thus nothing to distract you from your research. Generally the workshops includes between 15-50 researchers and the Dagstuhl personnel takes care of almost all the administration. On top of that the prize is heavily subsidised.

I know there is a similar place in Italy, although I never been there. McGill has a place in Barbados that is used for a similar purpose, but I don't think the administration is as well developed as at Dagstuhl. Are there any other places around? Is there anything like this in Australia? If not, why not?

Monday, September 10, 2007

SODA 2008 accepted papers

the list of accepted papers for SODA 2008 is out it seems.

lists of accepted papers for theory conferences

A useful webpage that keeps an updated list of accepted papers for theory conferences.
the webpage is maintained by Iftah Gazmu at tel-aviv university. There is also a list of events with upcoming deadlines and conference dates.