# ISAAC 2009 Accepted Papers

The list of accepted papers for ISAAC 2009 in Hawaii has now been posted.
I’m happy to see that my paper “Counting in the Presence of Memory Faults” is on the list (number 136), it has been co-authored by Gerth Brodal, Allan Jørgensen and Gabriel Moruz. The paper presents counting algorithms designed in the Faulty Memory RAM proposed by Finocchi and Italiano.
A fault-tolerant resilient counting algorithm as defined in our paper is a datastructure with an increment operation and a query operation. The query algorithm returns the number of increments operations that has been performed on the data structure, within an additive error factor.

It is simple to design such a datastructure in the standard RAM using a simple integer variable, but this is not possible in faulty memory RAM where arbritrary memory cells can get corrupted at any point in time. In the paper we present tradeoff lower bounds and upper bounds and tradeoffs between the additive error factor and the time used per operation.

# Computing Nationwide Flood Maps

This video shows what parts of Denmark will flood if the ocean rises. The flood maps were computed using the TerraSTREAM software package and the finished flood maps were visualized by importing the resulting rasters into the GRASS open source GIS.

The algorithm used by TerraSTREAM takes dikes and natural features into account and works directly on the original input terrain. The terrain has been down-sampled afterwards for visualization purposes, the few seemingly disconnected flat areas are due to the fact that the computed output has been down-sampled for this video.

The size input grid dem used in this computation was around 100 gigabytes. The video was used in recent article(in Danish) which was about TerraSTREAM’s ability to compute flooding maps like the one shown in the video, on even very big terrains. This type of flood map can be used in an initial screening phase for computing flood risks.
In my opinion TerraSTREAM is a good example of I/O-efficient (external memory) algorithms put to use in efficiently solving real world problems on massive datasets.

Update: A similar, interactive, example be seen at our global flood map site.

# Live at NWERC 2008

I’m currently sitting in Utrecht in the Netherlands watching the live scoreboard of the 2008 North-Western European Programming Contest (NWERC 2008). I’m the coach for the two danish teams, and they seem to be doing somewhat better than last time.

There is a LIVE scoreboard and also live webcams.

# Live from the Nordic Collegiate Programming Competition 2008

I am currently managing the Aarhus University (and only Danish!) site for the Nordic Collegiate Programming Competition (NCPC 2008).

We have 5 teams here – which is a 250% increase from last year (which was also an increase from the year before that). We are currently two hours into the competition and all the teams here are doing well and have solved at least two problems.  Right now, “MADALGO Men” is in the lead in the “student” class, and only one team in the open class have solved more problems! There is a total of about 140 teams competing.

Take a look at the Live Scoreboard.

# Participate in the ACM Collegiate Programming Contest

This is probably most interesting for students at Aarhus University. I’m coaching the teams from Aarhus that’ll go to the North-West European Regional Finals (NWERC 2008) in Utrecht. If you are interested in trying out for the teams you can read more here.

We have some talented people participating this yeah, I think they’ll do well at NWERC :) This will be my fifth NWERC event.  I participated in 2003, 2004 and 2005 and coached in 2006. I was at Duke during NWERC 2007 so I couldn’t go to that year.

Remember. programming is fun!

# No Plans for August? Come to Denmark and Learn About Cache-Oblivious Algorithms

MADALGO is hosting a summer school on cache-oblivious algorithms in August this year. Here is the announcement: (Note that registration is free (!) and that the registration deadline is approaching)

OVERVIEW AND GOAL

Cache-oblivious algorithms are algorithms that are efficient on any
level of any memory hierarchy; they are basically algorithms developed
for a two-level memory model (I/O-model) but without using any
parameters describing the memory levels. Although it might seem hard to
design algorithms for a memory hierarchy without using any
hierarchy-specific parameters, many efficient cache-oblivious algorithms
and data structures have nevertheless been developed since the
cache-oblivious model was defined in the late 1990s. The goal of the
summer school is to provide an in-depth introduction to some of the key
issues in cache-oblivious algorithms and data structures.

LECTURES
The school will be taught by experts in the area of cache-oblivious
algorithms and data structures. The lecturers will include (more
lectures to be announced):

* Erik Demaine (MIT)
* Norbert Zeh (Dalhousie University)

PARTICIPATION
The summer school will take place on August 18-21, 2008 at Center for
Massive Data Algorithmics (MADALGO) in the Department of Computer
Science, University of Aarhus, Denmark.

The school is targeted at graduate students, as well as researchers
interested in an in-depth introduction to cache-oblivious algorithms.

The capacity of the summer school is limited. Prospective participants
should register using the online registration form available at
www.madalgo.au.dk/cacheschool08/ as soon as possible. Registering
graduate students must also have their supervisor send a
letter confirming their graduate student status directly to
‘student_last_name/SS_2007/confirming’. Registration is on a
first-come-first-serve basis and will close on June 15, 2008.

Registration is free; handouts, coffee breaks, lunches and a dinner will
be provided by MADALGO and the University of Aarhus.

ORGANIZING COMMITTEE
* Gerth S. Brodal (MADALGO, Aarhus)

Center for MAssive Data ALGOrithmics is a major basic research center
funded by the Danish National Research Foundation. The center is located
at the Department of Computer Science, University of Aarhus, Denmark,
but also includes researchers at CSAIL, Massachusetts Institute of
Technology in the US, and at the Max Planck Institute for Informatics
and at Frankfurt University in Germany. The center covers all areas of
the design, analysis and implementation of algorithms and data
structures for processing massive data (interpreted broadly to cover
computations where data is large compared to the computational
resources), but with a main focus on I/O-efficient, cache-oblivious and
data stream algorithms.

# SoCG 2008 Accepted Papers

The list of accepted papers for The 24th Annual ACM Symposium on Computational Geometry (SoCG) 2008 is out: (Hint, paper 40 looks good)

1. Manor Mendel and Assaf Naor. Markov convexity and local rigidity of distorted metrics
2. Noga Alon, Robert Berke, Maike Buchin, Kevin Buchin, Peter Csorba, Saswata Shannigrahi, Bettina Speckmann and Philipp Zumstein. Polychromatic Colorings of Plane Graphs
3. Jinhee Chun, Matias Korman, Martin NÃ¶llenburg and Takeshi Tokuyama. Consistent Digital Rays
4. Eitan Yaffe and Dan Halperin. Approximating the Pathway Axis and the Persistence Diagram of a Collection of Balls in 3-Space
5. Naoki Katoh and Shin-ichi Tanigawa. Fast Enumeration Algorithms for Non-crossing Geometric Graphs
6. Ken Been, Martin N??llenburg, Sheung-Hung Poon and Alexander Wolff. Optimizing Active Ranges for Consistent Dynamic Map Labeling
7. Hans Raj Tiwary and Khaled Elbassioni. On the Complexity of Checking Self-duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism
8. Victor Chepoi, Feodor Dragan, Bertrand Estellon, Michel Habib and Yann Vaxes. Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs
9. Esther Arkin, Joseph Mitchell and Valentin Polishchuk. Maximum Thick Paths in Static and Dynamic Environments
10. Julien Demouth, Olivier Devillers, Marc Glisse and Xavier Goaoc. Helly-type theorems for approximate covering
11. Sarit Buzaglo, Ron Holzman and Rom Pinchasi. On $k$-intersecting curves and related problems
12. Mohammad Ali Abam, Mark de Berg and Joachim Gudmundsson. A Simple and Efficient Kinetic Spanner
13. Frederic Chazal and Steve Oudot. Towards Persistence-Based Reconstruction in Euclidean Spaces
14. Ken Clarkson. Tighter Bounds for Random Projections of Manifolds
15. Krzysztof Onak and Anastasios Sidiropoulos. Circular Partitions with Applications to Visualization and Embeddings
16. Bernard Chazelle and Wolfgang Mulzer. Markov Incremental Constructions
17. Kenneth L. Clarkson and C. Seshadhri. Self-Improving Algorithms for Delaunay Triangulations
18. Frederic Cazals, Aditya Parameswaran and Sylvain Pion. Robust construction of the three-dimensional flow complex
19. Herbert Edelsbrunner, John Harer and Amit Patel. Reeb Spaces of Piecewise Linear Mappings
20. Evangelia Pyrga and Saurabh Ray. New Existence Proofs for $\epsilon$-Nets
21. Lars Arge, Gerth StÃ¸lting Brodal and S. Srinivasa Rao. External memory planar point location with logarithmic updates
22. Eric Berberich, Michael Kerber and Michael Sagraloff. Exact Geometric-Topological Analysis of Algebraic Surfaces
23. Misha Belkin, Jian Sun and Yusu Wang. Discrete Laplace Operator on Meshed Surfaces
24. Olivier Devillers, Marc Glisse and Sylvain Lazard. Predicates for 3D visibility
25. Luca Castelli Aleardi, Eric Fusy and Thomas Lewiner. Schnyder woods for higher genus triangulated surfaces
26. Erin Chambers, Jeff Erickson and Pratik Worah. Testing Contractibility in Planar Rips Complexes
27. Rado Fulek, Andreas Holmsen and J??nos Pach. Intersecting convex sets by rays
28. Noga Alon, Dan Halperin, Oren Nechushtan and Micha Sharir. The Complexity of the Outer Face in Arrangements of Random Segments
29. Maarten L??ffler and Jack Snoeyink. Delaunay triangulations of imprecise points in linear time after preprocessing
30. Erin Chambers, Ã‰ric Colin de VerdiÃ¨re, Jeff Erickson, Sylvain Lazard, Francis Lazarus and Shripad Thite. Walking Your Dog in the Woods in Polynomial Time
31. Jean-Daniel Boissonnat, Camille Wormser and Mariette Yvinec. Locally Uniform Anisotropic Meshing
32. Adrian Dumitrescu, Micha Sharir and Csaba Toth. Extremal problems on triangle areas in two and three dimensions
33. Timothy M. Chan. A (Slightly) Faster Algorithm for Klee's Measure Problem
34. Timothy M. Chan. Dynamic Coresets
35. Timothy M. Chan. On Levels in Arrangements of Curves, III: Further Improvements
36. Minkyoung Cho and David Mount. Embedding and Similarity Search for Point Sets under Translation
37. Jacob Fox and Janos Pach. Coloring K_k-free intersection graphs of geometric objects in the plane
38. Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine and Scott D. Kominers. Hinged Dissections Exist
39. Vida Dujmovic, Ken-ichi Kawarabayashi, Bojan Mohar and David R. Wood. Improved upper bounds on the crossing number
40. Pankaj Agarwal, Lars Arge, Thomas MÃ¸lhave and Bardia Sadri. I/O Efficient Algorithms for Computing Contour Lines on a Terrain
41. Pankaj Agarwal, Bardia Sadri and Hai Yu. Untangling triangulations through local explorations
42. Ileana Streinu and Louis Theran. Combinatorial Genericity and Minimal Rigidity

# Election Day

I never made it to the consulate in Seattle in time to vote, unfortunately. I hope the right ones win. Anyways, DR decided to open their online live-tv to non-danish computers for today only, so I am currently sitting in my office at Duke watching the online coverage of the election, yay :)

We ordered some new machines the other day, four Dell XPS 720, two of those are in Denmark and the other two are currently in my office – look at these babies:

# Talk Tomorrow

Tomorrow I am giving a talk at the Duke CS tri-seminar which is a seminar arranged by the duke algorithms grad students. If you happen to be in the area, feel free to stop by :).

# Back on TV

Yesterday TV2-Ã˜stjylland aired the second part of their visit. You can see their interview with Lars and some background shots with Lars and me here.