Optimal road placement in a square
Luís Fernando Schultz Xavier da Silveira
Carleton University

Consider the following simple yet interesting problem. One has been assigned the task of laying down roads in the plane. The goal is to facilitate trips from two given opposing sides of a unit square: trips off the roads require one unit of time per unit of distance, while trips on the roads are faster, requiring only α units of time per unit of distance, where $0\leq\alpha<1$. The metric by which we judge road networks is the maximum travel time between two points, one on each of the opposing sides. Furthermore, there is a budget constraint: the total length of the roads may not exceed a parameter $\beta>0$.

In this seminar, we show road networks that make this maximum travel time the least possible. That is for any choice of α, but limitations in our methodology demand the assumption that $\beta\leq \sqrt{2}$.

We also consider two variants of the problem, one where the roads are directed and the other regarding the unit circle rather than the unit square.