  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.
