An Improved Algorithm for Inserting a Highway in a City Metric Based on Qua-siconvex Optimization

摘要

We introduce an improved algorithm to locate a segment highway such that the maximum city distance between a given set of n points is minimized (where the city distance is measured with speed v > 1 on a highway and 1 in the underlying metric elsewhere avoiding obstacles). We consider that such highway is built in a complex transportation system with H other highways and obstacles. The algorithm runs in 0(n~3H~3(log^2 n + log H)) time using O(nH) space improving the previous O(n~4H~4) time and space bound.