## Abstract

We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in (Formula presented.), 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 pair’s Manhattan (that is, L_{1}-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless (Formula presented.)). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension d and any ε>0, an O(n^{ε})-approximation algorithm. For 3D, we also give a 4(k−1)-approximation algorithm for the case that the terminals are contained in the union of k≥2 parallel planes.

Original language | English (US) |
---|---|

Pages (from-to) | 36-52 |

Number of pages | 17 |

Journal | Algorithmica |

Volume | 71 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2013 |

## Keywords

- Approximation algorithms
- Computational geometry
- Minimum Manhattan network

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics