CONSTRUCTING OPTIMAL HIGHWAYS
- 1 February 2009
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 20 (01) , 3-23
Abstract
For two points p and q in the plane, a straight line h, called a highway, and a real v > 1, we define the travel time (also known as the city distance) from p and q to be the time needed to traverse a quickest path from p to q, where the distance is measured with speed v on h and with speed 1 in the underlying metric elsewhere. Given a set S of n points in the plane and a highway speed v, we consider the problem of finding a highway that minimizes the maximum travel time over all pairs of points in S. If the orientation of the highway is fixed, the optimal highway can be computed in linear time, both for the L1- and the Euclidean metric as the underlying metric. If arbitrary orientations are allowed, then the optimal highway can be computed in O(n2 log n) time. We also consider the problem of computing an optimal pair of highways, one being horizontal, one vertical.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANEInternational Journal of Computational Geometry & Applications, 2006
- Quickest Paths, Straight Skeletons, and the City Voronoi DiagramDiscrete & Computational Geometry, 2003
- Voronoi Diagram for services neighboring a highwayInformation Processing Letters, 2003
- Fast approximations for sums of distances, clustering and the Fermat–Weber problemComputational Geometry, 2003
- Geometric Applications of a Randomized Optimization TechniqueDiscrete & Computational Geometry, 1999
- The upper envelope of piecewise linear functions: Algorithms and applicationsDiscrete & Computational Geometry, 1989
- Generalized Selection and Ranking: Sorted MatricesSIAM Journal on Computing, 1984
- Euclidean Constructibility in Graph-Minimization ProblemsMathematics Magazine, 1969