I recently completed a round-the-world journey from New York to Israel, Hong Kong, various parts of Australia, New Zealand, Los Angeles and back to New York. The ticket for this journey had the following conditions:
You can fly as many legs as you like, as long as you are always moving (at least slightly) east, or always moving (at least slightly) west. You must end where you started, and you cannot circle the globe more than once. All flights must be operated by (or have codeshare numbers for) either Qantas or El-Al.For example, since we chose to move east, it was ok to fly from Hong Kong to Perth, because Perth's longitude is slightly east of that of Hong Kong. Similarly, we would not have been allowed to fly from Darwin to Uluru because that would have been slightly west; instead, we flew to Alice Springs and drove to Uluru.
As a traveler, it is tricky trying to figure out which itineraries are possible, and which are not. Some cities simply cannot be part of a round-the-world ticket of this type. (How would you identify such cities algorithmically?) Choosing to visit city A can mean that another city B cannot be visited.
You have been hired by the airlines to market this round-the-world ticket. Your job is to write a program to take the set of city-pairs connected by the airline(s) as input, and to derive a one-page hardcopy output (suitable for a magazine page, say) that explains the travel options to a potential traveler. (The program's output may not be subsequently hand-edited; it must be used verbatim.)
A set of city/latitude/longitude triples can also be used as input; you will need to verify that your proposed itineraries satisfy the monotonicity property of longitude mentioned above.
The output can be textual, graphical, diagrammatic, or something else. The aim is to convey as much information about what can/can't be done as possible. Relevant information, such as the distance of each flight leg, can be derived from global latitude/longitude data. This kind of information can be included if you think it is important. But remember that too much information might clutter the output.
The Qantas/El-Al information provides a realistic data set. You can get their flight schedules from the web. We'll also evaluate your programs on some other data sets, either fictional or based on hypothetical combinations of real airlines.
For the competition at the end of the project, at least one of the data sets will be one you haven't seen before.
Your output will be judged by a panel of judges. Membership of the panel will be discussed in class.