Related sites: Algorithms Group               Possible graduation projects with Herman Haverkort     OWInfo    Contact Herman Haverkort

		Elevation models    Space-filling curves    Route maps    Your choice    More info

Below are some general topics for CSE graduation projects which could be done under my supervision. Computations on large elevation models Current remote-sensing technology provides detailed elevation models of the surface of the earth. These are usually made available in the form of a grid: a matrix with elevation values for points in a regular grid on the surface of the earth. Two important applications of such models are hydrological studies and visibility computations. Hydrological computations In hydrological studies we analyse the flow of water on a terrain, for example to study the effects of possible human intervention or to estimate risks of erosion. Assuming that water always flows downhill, we can predict the flow of water on a terrain from its elevation model. This involves several computations: terrain correction: removing small "depressions" and "dams" where water would get stuck (because such depressions and dams are quite unnatural and are probably the result of sampling errors); flow routing: there will be patches of terrain that seem to be flat (possibly lakes), nevertheless water will probably flow out of these flat areas somewhere. The flow routing problem is to compute, for every point in a flat patch of terrain, in what direction water would find a way out. flow accumulation: computing for every point of the terrain the size of the region from which water flows to that point. hierarchical watershed labelling: giving each point of the terrain a label that indicates its position in the watershed hierarchy (the hierarchy of river, tributary, and subtributary basins). It is not very difficult to come up with algorithms for these problems. However, the grid models may be as large as several dozen gigabytes so that they do not fit in the main memory of a computer at once. Therefore hydrological analysis requires I/O-efficient algorithms: algorithms that are especially designed to minimise the swapping of data between main memory and disk. And this is where the challenge comes in. In a previous graduation project we designed and implemented new I/O-efficient algorithms for terrain correction (removing all depressions) and for flow accumulation (assuming that from every grid point, water flows down in one direction). With these algorithm we managed to process large terrains (13 GB) more than ten times faster than the state-of-the-art software that is currently available. That is really nice, but it does not immediately provide a solution for the remaining hydrological computations. Some of the remaining questions are: Can we also speed up flow routing? Can we also speed up watershed labelling? Can we also do terrain correction where we only remove small depressions? Can we also do flow accumulation if water flows in multiple (downhill) directions from each point? Can we adapt the algorithms to work with adaptive grids (grids with cells of different sizes, typically with large cells in flat terrain, more refined in rough terrain)? Some of these questions could be addressed in a graduation project, which could be a combination of theoretical work and experiments. Visibility computations Another important application of elevation models is the computation of visibility maps: which parts of the terrain can be seen from a given viewpoint? Such maps are useful, for example, when planning the construction of buildings that should have a good view over the terrain (such as watch towers) or rather the opposite (they should not spoil the view). Whether a point p is visible or not, depends on the elevation profile of the terrain on the line from the viewpoint to p. The elevation profile along that line has to be estimated by interpolating between the elevation values of nearby grid points. However, we cannot afford to do this too precisely: because of the huge size of the data sets we have to find a balance between accuracy and efficiency. The goal of a graduation project could be to analyse and improve the state-of-the-art in the accuracy/efficiency balance of visibility map algorithms. The project could be a combination of theoretical work and experiments. Space-filling curves Space-filling curves are curves that are so crinkly that they really fill the space: when you zoom in, you will see that the curve is so crinkly that there is really no empty space left: Although such curves may look complicated, they are typically defined by a easy recursive definition. For example, here is the rule defining the curve published by David Hilbert in 1891: The figure shows how the square is divided into four smaller squares, numbered 0 to 3. This means that all points in square 0 come before points in square 1 in the order; these are followed by the points in square 2 etc. This is illustrated by a curve drawn through the centres of the squares. For points that lie inside the same smaller square, the order is defined by applying the rule recursively, albeit sometimes rotated or mirrored---this is indicated by the letters R inside the squares. When you expand the recursion, the curve becomes ever more dense and crinkly. In the limit the curve fills the full square. The recursive rule cannot only be used to make pretty pictures, but it can also be used to quickly sort points along the curve. Space-filling curves can thus be used to sort points into groups of, say, B points: sort them along the curve, put the first B points in a group, then the next B points in a group, etc. Here is an example with 16 points in four groups of size B = 4: This way of dividing points into groups is very useful for the construction of certain data structures, provided the bounding boxes of the resulting groups are small. To what extent this will be the case, depends on the curve that is used. Above we gave the definition of one space-filling curve, but there are infinitely many more. In particular, all ideas sketched above are also applied to points in three dimensions, and currently we have no idea what would be the best three-dimensional curve. In a graduation project you could contribute to our quest for better three-dimensional space-filling curves. The project would require a combination of theoretical analysis and automated search, exploring the limits of what a computer can do. Route map drawings A route network consists of a graph with vertices and edges, together with a set of paths (routes) through the graph. In many situations one needs a drawing of such a network: not just any drawing, but a drawing in which the routes can easily be seen. Maps of public transport systems are a well-known example. In recent graduation projects, we worked on the design of road networks: given a set of villages, where should one build roads and roundabouts to optimise the travel time between the villages while staying within a given budget? We needed many figures of different route networks (such as the one shown below, drawn by Marco Verstege); unfortunately we had to draw them all by hand. Fortunately this work also led to new ideas about how such networks could be drawn nicely. These ideas need to be turned into mathematically precise optimisation criteria for route network drawings, and then an automated approach needs to be developed to draw such networks automatically. This could be the topic of a graduation project with a combination of theoretical work, implementation work, and experiments to determine what optimisation criteria lead to drawings that are easy to read. An algorithmic topic of your choice If you have an idea for an algorithmic graduation project yourself, let me know! More information? If you are potentially interested in doing a graduation project with me, I would be happy to tell you more about the topics mentioned above.

OWInfo    Contact Herman Haverkort