Bounds for \(k\)-centers of point sets under \(L_{\infty}\)-bottleneck distance

Abstract

We consider the \(k\)-center problem on the space of fixed-size point sets in the plane under the \(L_{\infty}\)-bottleneck distance. While this problem is motivated by persistence diagrams in topological data analysis, we illustrate it as a Restaurant Supply Problem: given \(n\) restaurant chains of \(m\) stores each, we want to place supermarket chains, also of \(m\) stores each, such that each restaurant chain can select one supermarket chain to supply all its stores, ensuring that each store is matched to a nearby supermarket. How many supermarket chains are required to supply all restaurants? We address this questions under the constraint that any two restaurant chains are so close under the $L_{\infty}$-distance that they can be supplied by a single supermarket chain. We provide both upper and lower bounds for this problem and investigate its computational complexity.