Planes, Trains and Automobiles: Problems in Computational Navigation
Wednesday, July 21, 2-3 p.m.
Dr. Darryl Hill
In this talk we will focus on a few computational problems related to navigation. We will consider the optimal placement of a road network to minimize cost (driving off-road being more “expensive”). We will examine a network of intersecting orthogonal train lines and look at scheduling solutions that avoid collisions. Finally we will examine geometric graphs (i.e., graphs embedded in the “plane”) and consider which classes of graphs provide reasonably short paths between two locations, both in the case where we have global knowledge of the graph, and also the online setting where only local knowledge of the graph is available.
Presented by Department of Computer Science