Proximity and location problems on transportation networks

Abstract

This thesis considers algorithmic problems on geometric transportation network, motivated by the real-world transportation networks, in a computational point of view. In a city or anywhere on this planet, people use transportation networks like streets in a city, subway or bus networks, or a highway over a nation. Such a transportation network supports faster movement and help in economizing travel time. We define a transportation network as a (straight-line) plane graph with edges assigned by positive real numbers, called speeds. By certain rules of using a given transportation network, the travel time for each path is well defined, and thus a new metric, called a transportation metric, is induced. This thesis introduces several interesting research problems arising in this situation; some of those are shortest (or quickest) paths problem, Voronoi diagrams, farthest Voronoi diagram, transportation network design problems, and so on. These problems are roughly categorized into proximity problems and location problems. In this thesis, we define such problems that we consider, present a number of new results on those problems, and finally conclude with future work and interesting open questions.