Presentation
The minimum Manhattan network problem approximations and exact solutions
Author  Benkert, Marc
Shirabe, Takeshi Wolff, Alexander 
Date  2004 
Published in 

Abstract  A Manhattan p–q path is a geodesic in the Manhattan (or L1) metric that connects p and q, i.e. a staircase path between p and q. Given a set of
points P in the plane, a Manhattan network is a set of axisparallel line ... A Manhattan p–q path is a geodesic in the Manhattan (or L1) metric that connects p and q, i.e. a staircase path between p and q. Given a set of points P in the plane, a Manhattan network is a set of axisparallel line segments that contains a Manhattan p–q path for each pair {p, q} of points in P. In this paper we consider the minimum Manhattan network problem which consists of finding a Manhattan network of minimum total length, an MMN in short, i.e. a 1spanner for the Manhattan metric. The problem is likely to have applications in VLSI layout. Its complexity status is unknown. The problem has been considered before. Gudmundsson et al. have proposed a factor8 O(n log n)time and a factor4 O(n3)time approximation algorithm, where n is the number of input points. Later Kato et al. have given a factor2 O(n3)time approximation algorithm. However, their correctness proof is incomplete. In this paper we give a geometric factor3 approximation algorithm that runs in O(n log n) time and the first mixedinteger programming (MIP) formulation for the MMN problem. We have implemented and evaluated both approaches. 
Citation  Benkert, M., Shirabe, T. y Wolff, A. (2004). The minimum Manhattan network problem approximations and exact solutions. En 20th European Workshop on Computational Geometry, Sevilla. 
Files  Size  Format  View  Description 

The minimum Manhattan network ...  132.3Kb  [PDF]  View/  