2020/10/27 by Antonios Antoniadis, Antoniadis, Antonios, Margarita Capretto +13
Computer Science · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.2010.14338
arxiv created 2020/10/27 · arxiv updated 2020/10/28
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(log n)-approximation is trivial. We show that the problem is NP-hard and present an O(√(log n))-approximation algorithm. Moreover, we provide an O(loglog 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.