MA-INF 1315 Lab Computational Geometry

offered by Herman Haverkort

In the computational geometry lab, a student can work alone or in a team on the design, analysis and implementation of efficient algorithms for a problem with geometric data. The lab is offered each semester on demand. If you are interested, please contact me to make an appointment for a Zoom meeting to discuss possible topics. Topics are typically in the same areas as those of graduations projects I tend to supervise, and they are typically related to recent research or recent research plans of myself. For a few examples, see below. Note that other members of the theory group may also be able to supervise lab projects in their respective research areas. Under circumstances, a lab project could function as a pilot study, which, if successful, can be continued in the form of a graduation project.

The planned work load of a lab project is 270 hours (9 credit points). Progress is discussed in regular (Zoom) meetings with the instructor and, if applicable, fellow students. Assessment is based on an oral presentation (via Zoom) and a written report that discusses the problem, the design decisions taken, and the results.

Example topics

Schematic maps of transportation networks are designed to show the connections between different train or metro lines clearly. However, from such maps it may be hard to get an impression which routes are costly (in terms of travel time, or otherwise) and which routes are preferable. To remedy this shortcoming, one may add a background to the map that gives an impression of travel cost. I am exploring two ways to do this. The first approach is to divide the map into zones, such that the travel cost on each route is roughly proportional to the number of times one crosses a zone boundary. The second approach is to calculate a weight function on the plane in which the map is drawn, such that the travel cost on each route corresponds to the integral of the weight function over that route. By rendering low weights as bright background and high weights as dark background, low-cost routes will stand out due to high contrast with the background. Realising such maps requires solutions to problems of computational geometry, and this leads to three possible topics for lab projects, as described below.

A fourth, unrelated topic, considers the storage and retrieval of GPS trajectories or time series data; this topic is discussed at the bottom of this page.

Topic 1: Shortest-path preserving rounding of weights in a graph

The goal of this project is to decide which edges of the transportation network should cross zone boundaries, such that map users who choose their routes so as to minimize the number of zone boundary crossings, end up choosing the routes that indeed have the lowest total cost. The problem lends itself to theoretical research (for what types of networks is it NP-hard?) and/or practical research (what heuristic solution gives satisfactory results on realistic networks?).

Topic 2: Separating groups of points by disjoint disks

Given which edges cross zone boundaries, and thus, which groups of stations must lie in the same zone, we need to draw the zones. To minimize clutter on the map, the zones should have simple shapes. Ideally, the zones look like disjoint disks. Again, this problem lends itself to theoretical research: is it NP-hard to decide whether we can draw the zones as disjoint disks, given the locations of the stations and their grouping into zones? But we can also research it from a more practical perspective: what heuristics can we apply to get well-shaped zones when disks do not fit, or when a solution with disks cannot be computed efficiently?

Topic 3: Inferring a cost map from costs of line segments

We are given a network drawn in the plane, with a cost associated with each edge. The goal is to assign a weight to each point in the plane, such that the integral of the weight function over the set of points covered by each edge matches that edge's specified cost. A technically correct solution would be nearly trivial to obtain, but to obtain a readable map, we should satisfy additional criteria that make the problem considerably more challenging. For example, the weight function should be as smooth as possible, and it should not have steep gradients where they would be obscured by the network drawing.

Topic 4: Locality-preserving encoding of trajectories

A trajectory is, technically, a continuous function from the time line to points in a one- or higher-dimensional space. This space could be the surface of the earth, as with, for example, GPS traces. More generally however, the space could have d dimensions that correspond to measurements of d different parameters. For example, the recordings of a weather station over time could be seen as a five-dimensional trajectory, where the five dimensions correspond to pressure, wind speed, temperature, humidity, and visibility. With increasing possibilities to record vast amounts of trajectory data, there is an increasing demand for data structures that allow us to store and search trajectory data. For example, from a set of trajectories recorded in the past, we want to be able to retrieve efficiently all trajectories that are somewhat similar to some given trajectory. In a lab project, we would experiment with different ways to encode and store trajectories, to see what encoding and storage schemes allow for efficient searching.

Page Tools