## Abstract

We consider minimum-cardinality Manhattan connected sets with arbitrary demands: Given a collection of points P in the plane, together with a subset of pairs of points in P (which we call demands), find a minimum-cardinality superset of P such that every demand pair is connected by a path whose length is the ℓ_{1} -distance of the pair. This problem is a variant of three well-studied problems that have arisen in computational geometry, data structures, and network design: (i) It is a node-cost variant of the classical Manhattan network problem, (ii) it is an extension of the binary search tree problem to arbitrary demands, and (iii) it is a special case of the directed Steiner forest problem. Since the problem inherits basic structural properties from the context of binary search trees, an O(logn) -approximation is trivial. We show that the problem is NP-hard and present an O(logn) -approximation algorithm. Moreover, we provide an O(loglogn) -approximation algorithm for complete k-partite demands as well as improved results for unit-disk demands and several generalizations. Our results crucially rely on a new lower bound on the optimal cost that could potentially be useful in the context of BSTs.

Original language | English |
---|---|

Title of host publication | Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings |

Editors | Anna Lubiw, Mohammad Salavatipour |

Pages | 85-100 |

Number of pages | 16 |

DOIs | |

Publication status | Published - 2021 |

MoE publication type | A4 Article in a conference publication |

Event | International Symposium on Algorithms and Data Structures - Virtual, Online Duration: 9 Aug 2021 → 11 Aug 2021 Conference number: 17 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 12808 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | International Symposium on Algorithms and Data Structures |
---|---|

Abbreviated title | WADS 2021 |

City | Virtual, Online |

Period | 09/08/2021 → 11/08/2021 |

## Keywords

- Binary search tree
- Manhattan networks
- NP-hardness