A fixed-parameter algorithm for the minimum Manhattan network problem
Christian Knauer, Andreas Spillner · Journal of Computational Geometry (Carleton University) · 2010
A Manhattan network for a finite set P of points in the plane is a geometric graph such that its vertex set contains P, its edges are axis-parallel and non-crossing and, for any two points p andq in P, there exists a path in the network connecting p and q whose length equals the l1-distance between p and q. The problem of computing a Manhattan network of minimum total edge length for a given point set P has recently been shown to be NP-hard. In this note, using as the parameter the minimum number h of horizontal straight lines that contain the points in P, we present a fixed-parameter algorithm for this problem running in O*(214h) time and note that, under the exponential time hypothesis for 3-SAT, a run time that is subexponential in h is impossible.