Efficient algorithms for computing one or two discrete centers hitting a set of line segments

Given the scheduling model of bike-sharing, we consider the problem of hitting a set of n axis-parallel line segments in \(\mathbb {R}^2\) by a square or an \(\ell _\infty \)-circle (and two squares, or two \(\ell _\infty \)-circles) whose center(s) must lie on some line segment(s) such that the (maximum) edge length of the square(s) is minimized. Under a different tree model, we consider (virtual) hitting circles whose centers must lie on some tree edges with similar minmax-objectives (with the distance between a center to a target segment being the shortest path length between them). To be more specific, we consider the cases when one needs to compute one (and two) centers on some edge(s) of a tree with m edges, where n target segments must be hit, and the objective is to minimize the maximum path length from the target segments to the nearer center(s). We give three linear-time algorithms and an \(O(n^2\log n)\) algorithm for the four problems in consideration.