On Minimum Generalized Manhattan Connections

Antonios Antoniadis, Margarita Capretto, Parinya Chalermsook, Christoph Damerius, Peter Kling, Lukas Nölke, Nidia Obscura, Joachim Spoerhase

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 $\ell_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(\log n)$-approximation is trivial. We show that the problem is NP-hard and present an $O(\sqrt{\log n})$-approximation algorithm. Moreover, we provide an $O(\log\log n)$-approximation algorithm for complete bipartite 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.

Introduction

The Minimum Generalized Manhattan Connection (MinGMConn) problem is a node-cost variant of the classical Manhattan network problem. Given a set of points $P$ and a set of "demands" (pairs of points in $P$), the goal is to find a minimum-cardinality superset of $P$ such that every demand pair is connected by a rectilinear path of minimum length (the $\ell_1$-distance).

Illustration of Manhattan rectangles and connections between point pairs.

This problem is deeply connected to the geometric view of Binary Search Trees (BSTs). In this view, searching for elements in a BST corresponds to adding points to a 2D plane to satisfy certain connectivity properties. While the "Dynamic Optimality Conjecture" suggests an $O(1)$-competitive BST exists, it is currently unknown if finding the optimal offline BST is NP-hard. By generalizing the BST problem to arbitrary demand pairs, MinGMConn provides a framework to study these fundamental structural properties.

Complexity and NP-Hardness

The authors prove that MinGMConn is NP-hard through a reduction from 3-SAT. The reduction uses a grid-based arrangement of variable, clause, and connection gadgets. This result establishes that the problem is computationally difficult even under strict constraints, such as limiting the number of points per row or column.

Gadget construction for the NP-hardness reduction from 3-SAT, showing variable (GX) and clause (GC) components.

The VS Lower Bound and Approximation Algorithms

A central contribution of the paper is the introduction of the Vertically Separable (VS) demands lower bound. A set of demands is vertically separable if their bounding rectangles can be partitioned by vertical lines in a specific sequence without interference. This bound is stronger than the traditional "Independent Rectangle" (IR) bound used in BST literature.

The subadditivity of the VS bound enables a divide-and-conquer approach. For $s$-thin instances (where points occupy only $s$ distinct x-coordinates), the authors achieve an $O(\log s)$ approximation. For general instances, they combine this with a vertical strip decomposition to achieve an $O(\sqrt{\log n})$ approximation ratio, improving upon the trivial $O(\log n)$ bound.

Key Results and Special Cases

The paper provides several improved results for specific demand structures:

  • $O(\log \log n)$ approximation for complete $k$-partite demands.
  • $O(1)$ (constant factor) for unit-disk demands, where points are demands if they are within a fixed distance $r$.
  • $O(\log \Delta)$ for general disk demands with radius ratio $\Delta$.

Conclusion

By bridging computational geometry and data structures, this work offers a potential path toward proving the NP-hardness of the BST problem. The techniques developed, particularly the VS bound, provide new tools for analyzing rectilinear connectivity problems. Future work may involve applying these sub-logarithmic approximation techniques to the traditional edge-cost Manhattan network problem.

Summary updated

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 $\ell_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(\log n)$-approximation is trivial. We show that the problem is NP-hard and present an $O(\sqrt{\log n})$-approximation algorithm. Moreover, we provide an $O(\log\log n)$-approximation algorithm for complete bipartite 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.
BibTeX
@inproceedings{antoniadis2021minimum,
  author = {Antonios Antoniadis and Margarita Capretto and Parinya Chalermsook and Christoph Damerius and Peter Kling and Lukas Nölke and Nidia Obscura and Joachim Spoerhase},
  title = {{On Minimum Generalized Manhattan Connections}},
  booktitle = {WADS},
  year = {2021},
  doi = {10.1007/978-3-030-83508-8\_7},
}
Figure