EuroCG 2010 in Dortmund

Posted on

Last Wednesday evening I re­turned from Eu­roCG 2010 held in Dort­mund, Ger­many. The weather was nice throughout the con­fer­ence, and so were the food and drinks. (Although some people did not seem to care for the coffee in the lobby, but I’m not a coffee drinker.) Jan Vahren­hold and his team made this into a very smoothly run event, even in the pres­ence of some un­fore­seen can­cel­la­tions of talks.

A lot of in­ter­esting topics were pre­sented in talks ranging in quality from mod­erate to ex­cel­lent. I have to give spe­cial men­tion to Amit Chat­topad­hyay. When the speakers for the talk 2-Factor Ap­prox­i­ma­tion Al­go­rithm for Com­puting Max­imum In­de­pen­dent Set of a Unit Disk Graph" could not at­tend the con­fer­ence, he of­fered to give the talk in­stead of let­ting it get can­celled. Not being one of the au­thors, nor being af­fil­i­ated with them, he just read their ar­ticle and their slides a day in ad­vance and gave a talk on-the-fly. Ku­dos!

Fast-for­ward ses­sions

As de­cided by vote at the busi­ness meeting of Eu­roCG 2009, this year’s Eu­roCG was the first to have fast-for­ward ses­sions. In these short ses­sions, all con­fer­ence at­ten­dees are to­gether in one room. The speakers of the next two par­allel ses­sions get 60 sec­onds each (with slides sub­mitted in ad­vance) to pro­mote their talks. There is a coffee or lunch break be­fore the ac­tual par­allel ses­sions start, and then the process re­peats. This way, at­ten­dees are sup­posed to be able to make a more in­formed choice about which talks they want to at­tend.

This no­tion stolen from in­spired by SIG­GRAPH was still a bit un­fa­miliar to both or­ga­nizers and speak­ers. During the first few fast-for­ward ses­sions the speakers were asked to go in “column order”, that is, first all the speakers of ses­sion A, then all speakers of ses­sion B. At the sug­ges­tion of sev­eral at­ten­dees, this was changed to “row order” so that “com­peting” speakers went one after an­other. This order was then kept for the rest of the con­fer­ence.

In both or­ders, the speaker of ses­sion A al­ways came be­fore the par­allel speaker of ses­sion B. This seemed un­fair to me, but no one present seems to have used this to their ben­e­fit. More gen­er­ally, I think most speakers (my­self in­cluded) did not think the fast-for­ward through from a strategic point of view. My par­allel speaker even had a slide with the title of our paper on it, saying some­thing to the ef­fect of “this guy is speaking in par­allel to me, and his talk will surely also be nice”. Cer­tainly a nice ges­ture, but I’m not en­tirely sure why someone would do this ex­cept to get a smaller au­di­ence.

All in all, I quite like the con­cept. Skim­ming the pro­ceed­ings in ad­vance says some­thing of the top­ics, but not of the speak­ers. The ad­di­tion of fast-for­ward ses­sions thus gives one this extra vari­able by which to de­cide which talks to at­tend. At the busi­ness meet­ing, the vote was n-3 against 3 in favor of keeping the fast-for­ward ses­sions, so they will be used again at Eu­roCG 2011 held in Morschach, Switzer­land.

Keynote speaker

Al­though all the in­vited speakers gave ex­cel­lent talks, the one by Tim­othy Chan was the most mem­o­rable to me. With his inim­itable en­thu­siasm he gave a one-hour talk on In­stance-Op­timal Geo­metric Al­go­rithms.

He ex­plained the con­cept using the ex­ample of com­puting 2D convex hulls. For some, “easy” sets S of n points there are al­go­rithms to com­pute its h-point convex hull in O(n) time, while for other, “hard” point sets dif­ferent al­go­rithms with a run­ning time of O(n log h) are known to be op­ti­mal.

An easy (left) and a hard (right) point set for com­puting the convex hull
An “easy” (left) and a “hard” (right) point set for com­puting the convex hull

Tim­othy de­fined a func­tion H (some­what sim­ilar to en­tropy) so that H(S) is a number that mea­sures how “hard” it is to com­pute the convex hull for point set S. More pre­cisely, he proved that there is a Ω(H(S)) lower bound for com­puting the 2D convex hull in the mul­ti­linear de­ci­sion-tree model, by a simple and el­e­gant ad­ver­sary ar­gu­ment. He also showed that a slight mod­i­fi­ca­tion of the Kirk­patrick­-Seidel con­vex-hull al­go­rithm yields a run­ning time of O(H(S)). Thus its run­ning time (up to con­stant fac­tors) is as good or better than any other 2D convex hull al­go­rithm that does not de­pend on the order of the points.

Tim­othy ended the talk with ap­pli­ca­tions of the same tech­nique to other prob­lems, which in some cases did re­quire new al­go­rithms, such as for 3D convex hull. All in all a very im­pres­sive talk on some very im­pres­sive re­search, the paper for which can be found on Tim­o­thy’s web­site.