On Minimum Generalized Manhattan Connections

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

TL;DR

This paper introduces the Minimum Generalized Manhattan Connection (MinGMConn) problem, proving it is NP-hard and providing the first sub-logarithmic approximation algorithm ($O(\sqrt{\log n})$). By bridging computational geometry and data structures, the authors develop a new lower-bound technique—Vertically Separable (VS) demands—that offers a potential path toward solving the long-standing mystery of whether computing an optimal Binary Search Tree (BST) is NP-hard.

What Problem Does This Paper Address?

In computational geometry, a "Manhattan Network" typically connects a set of points using the shortest possible horizontal and vertical segments. Most research focuses on minimizing the total length of these segments (edge-cost). This paper shifts the focus to node-cost: minimizing the number of auxiliary points added to satisfy specific "demands" (pairs of points that must be connected by a shortest rectilinear path).

This isn't just a geometry puzzle; it’s 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, we don't even know if finding the best offline BST is NP-hard. By generalizing the BST problem to arbitrary demand pairs, this paper provides a framework to study these structural properties.

Methods

The authors employ a mix of combinatorial proofs and algorithmic design:

  • NP-Hardness Reduction: They reduce 3-SAT to MinGMConn using intricate "gadgets" (variable, clause, and connection gadgets) arranged in a grid. This proves the problem is difficult even under strict constraints (e.g., at most one point per row/column).
  • The VS Lower Bound: They introduce "Vertically Separable" (VS) demands. A set of demands is vertically separable if their rectangles can be "cut" by vertical lines in a specific order without interference. This bound is stronger than the traditional "Independent Rectangle" (IR) bound used in BST literature.
  • Divide-and-Conquer Algorithms:
    • For $s$-thin instances (where points occupy only $s$ distinct x-coordinates), they use a horizontal divide-and-conquer approach to achieve an $O(\log s)$ approximation.
  • For general instances, they combine this with a vertical strip decomposition, balancing the two to achieve the $O(\sqrt{\log n})$ result.

Datasets

As a theoretical paper in computer science, it does not use empirical datasets. Instead, it defines and analyzes mathematical models and problem instances.

Key Insights and Ideas

  • The Power of VS: The authors show that the VS bound is "subadditive." This property is the "secret sauce" that allows divide-and-conquer algorithms to work effectively, as the cost of solving sub-problems can be neatly bounded against the total optimal cost.
  • BST Roadmap: The paper suggests that the techniques used to prove MinGMConn is NP-hard—specifically the use of the VS bound to argue about "soundness"—could be adapted to finally prove the NP-hardness of the BST problem itself.
  • Sparsification: For specific demand structures (like $k$-partite graphs), the authors show you can "sparsify" the input—removing redundant points without losing feasibility—to get even better $O(\log \log n)$ approximations.

Key Results

  • Complexity: Proved that MinGMConn is NP-hard.
  • General Approximation: Developed an efficient $O(\sqrt{\log n})$-approximation algorithm, improving upon the trivial $O(\log n)$ bound inherited from BSTs.
  • Special Cases:
    • $O(\log \log n)$ 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$.

Limitations and Future Work

  • The BST Gap: While MinGMConn is NP-hard, the hardness of the original BST problem (where demands are "evolving") remains open.
  • Tightness of VS: It is currently unknown if the VS bound is within a constant factor of the true optimal cost for BSTs.
  • Edge-Cost Variants: The authors suggest their $O(\sqrt{\log n})$ approach might be adaptable to the more traditional edge-cost Manhattan network problem, which currently lacks such a sub-logarithmic result for arbitrary demands.

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 Acosta and Joachim Spoerhase},
  title = {{On Minimum Generalized Manhattan Connections}},
  booktitle = {WADS},
  year = {2021},
  doi = {10.1007/978-3-030-83508-8\_7},
}

Loading related content...

Figure