Theory of Computing Systems Computational Theory and Mathematics

Computing Largest Minimum Color-Spanning Intervals of Imprecise Points

Ankush Acharyya, Vahideh Keikha, Maria Saumell, Rodrigo I. Silveira
Springer Nature · 2026-04-30 · DOI 10.1007/s00224-026-10270-1

Abstract

Abstract We study a geometric facility location problem under imprecision. Given n unit segments on the real line, each with one of k colors, the goal is to place a point on each segment such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given segment of each color. We prove that if the input segments are pairwise disjoint, the problem can be solved in O ( n ) time, even for segments of arbitrary length. For overlapping segments, the problem becomes much more difficult. Nevertheless, we show that it can be solved in $$O(n \log ^2 n)$$ O ( n log 2 n ) time when $$k=2$$ k = 2 , by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.

Read at publisher →