Approximating Minimum Manhattan Networks in Higher Dimensions
We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in\({\mathbb {R}}^{d}\), find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pairs Manhattan (that is, L 1-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless \({\mathcal{P}} = \mathcal{NP}\)). Approximation algorithms are known for 2D, but not for 3D.
approximation algorithms computational geometry minimummanhattannetwork