Optimal Insertion of a Segment Highway in a City Metric

摘要

Given two sets of points in the plane, we are interested in locating a highway h such that an objective function on the city distance between points of the two sets is minimized (where the city distance is measured with speed v > 1 on a highway and 1 in the underlying metric elsewhere). Extending