ISAAC - Day 3

Today I gave my two presentations. Both papers are about trajectories, or what is sometime called geospatial lifelines, which is the the research topic of our project in Sydney. In the first paper we consider the problem of compressing, or simplifying, trajectories such that both the spatial and temporal information is preserved. The problem has been studied earlier in the database community, however, we gave a first method that guarantees that approximate versions of standard operations such as where_at, when_at and nearest neighbour are "sound". We also showed how the simplification can be done in O(n log^3 n) time (in practice the standard Douglas-Peucker algorithm in 3D works like a charm).

The second paper considered the problem of computing a "popular place" in a set of trajectories. A popular place is just a region, in our case a square of given side length, that is "visited" by at least k different trajectories. Our main result is a quadratic time algorithm with a "matching" 3-SUM hardness proof.

Both presentations went okay and hopefully some of the participants now have an idea of the existing problems in the area.

Finally I had sushi!

Tomorrow I'm going back to Sydney and my new office which is on the top floor of the School of IT building at University of Sydney.

ISAAC - Day 2

I overslept and missed the invited talk by Robin Thomas. The rest of the day I again mostly listened to geometry papers, except a presentation on game theory by Stefan Schmid (Eidenbenz, Oswald and Wattenhofer). They considered an extended version of the prisoners'dilemma. I'm far from an expert in the area but it seems to have some relation to the concept of putting taxes on edges in a network as proposed by Cole, Dodis and Roughgarden.

Another talk that I found interesting was by Tetsuo Asano who gave a talk on triangulations with Steiner points. That is, the aim is to triangulate a polygon while optimising some criterion. However, you're allowed to add, say k, Steiner points in the interior. How will you add the Steiner points such that the criterion is optimised? They showed polynomial time algorithms for adding a constant number of Steiner points while optimising the maximum interior angle.

Today was also the day of the conference banquet. We were served a French/Italian dinner. I still haven't had any sushi since I arrived!!!

ISAAC - Day 1

After a week of diving in Thailand (Similan Islands) together with my fellow blogger Tasos, I'm now attending ISAAC in Sendai. Yesterday there was a workshop in the honour of Prof. Nishizeki's 60th birthday. Prof. Nishizeki founded ISAAC in 1990 in order to expand the research community to Asia and the Pacific. Unfortunately I missed most of the talks but during the afternoon I attended a talk by Dorothea Wagner. She talked about her favourite topic, routing in transportation networks. This is a topic that I find very appealing. Dorothea and her group use more "algorithmic engineering" than what I'm used to but I still find both the problem and the techniques used to obtain a practical solution very interesting. She covered the algorithmic engineering approaches which proves that a good theoretical understanding of a problem can give very fast and effective solutions.


The first talk at ISAAC was an invited talk by Pankaj Agarwal. He talked about I/O-efficient algorithms for analysing terrain data. As usual Pankaj gave an excellent talk that was easy to follow and still gave some insight into the problems in the area. The rest of the day I mainly attended the computational geometry sessions. It's surprising how many of the papers that are in the computational geometry field. I went through the program and concluded that almost half the papers are geometry related.