Differences

This shows you the differences between two versions of the page.

--- graduation_projects [2021/06/06 14:29] – [Hierarchical schematic map drawing (BM)] administrator
+++ graduation_projects [2021/06/06 14:30] (current) – [Exploration of building designs (M)] administrator
@@ Line 7: / Line 7: @@
 =====Suggestions for future projects=====
+====Cost cues for maps of transportation networks (BM)====
+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, 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. This line of research leads to three possible topics for graduation projects:
+==Shortest-path preserving rounding of weights in a graph (M)==
+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 (is it NP-hard or not?) and/or practical research (what heuristic solution gives satisfactory results on realistic networks?).
+==Separating groups of points by disjoint disks (M)==
+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, they are 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?
+==Inferring a cost map from costs of line segments (BM)==
+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. In a Master project, we could also try to investigate how the computed background affects users' perception of the network and how it affects what routes they would choose to travel.
 ====Exploration of building designs (M)====

Herman Haverkort

User Tools

Site Tools

Differences

Page Tools