The aim of this project is to design a map scheme analogous to a road atlas. The purpose of the map is to allow a person to identify the best route from any point on the map to any other. For us, the best route will be defined as the one that takes the shortest time, which is not necessarily the shortest in terms of distance. Some links in the map may have different speed ratings than others, for example:
There has been some work on related problems in the past. For example see http://planner.t.u-tokyo.ac.jp/member/inoue/pdf_files/JSPS2003_Time-distance.pdf for a discussion of time-distance maps, and the UPS website http://www.ups.com/maps for showing how many days it takes to get to a variety of points. Many trip planning web sites solve the problem of identifying the shortest route between pairs of points.
Our problem is different from these because (a) we're interested in knowing the actual route to take, not just the time, and (b) our map should help navigate between any pair of points, not just from a single specified source.
In general, there may be too much information to display on a single map, and so part of the problem is to focus on displaying just the most informative and/or useful items. You should feel free to distort the geometry if that helps, but bear in mind that preserving some of the natural geometry can leverage a user's prior knowledge.
There will be two categories of map, depending on whether the speed on the various links can change due to changes in traffic conditions. If speeds don't change, then a single map can be printed without the need for the user to have a computer. If speeds change, then a new map could be generated each time there's a change. Nevertheless, there are opportunities to share work since most speeds will not change. Further, one would hope that there is some degree of continuity between frames in the dynamic case.
You will be given a number of (x,y) points in a Cartesian coordinate system with one unit equal to one kilometer. Each point will have a label, such as a city name, which you may assume to be unique. No two data points will share the same (x,y) coordinate pair. You will also be given a set of links between labels, together with a distance (in km) and a speed rating (in km/hr). For this project, we shall assume that links are bidirectional, and that the speed of travel is the same in each direction. Distances may be greater than the straight-line Euclidean distance due to winding roads, roads that circumnavigate mountains or lakes, etc.
The output of your program should be an image (or sequence of images) that fit on a standard single-screen computer display, and can be printed on a standard letter-sized piece of paper.
We will provide some initial test data, but each group is expected to generate two additional data sets for use by the class. At least one of these data sets should be based on some real-world map (e.g., a highway map of New York State with some airline routes included) with at least 50 points and 100 links. The other data set may be smaller, focusing on a particular ``interesting'' configuration.
The dynamic data sets will be generated by perturbing a small number of randomly chosen links from the static data set, making some links slow down over time.
At the end of the project period, your programs will be run against one data set you've already seen, and one data set you haven't seen. Your maps will be judged by the instructor, the TA, and by ``experts'' chosen by the instructor according to the discussion in class. (For example, in a past class where we drew representations of an airline's route system, the class chose a travel-agent, a child, an artist/designer, etc.) As always, this competition will not affect your grades, which depend on the quality of the ideas used to address the problem.