G²OAT seminar: Computing largest minimum color-spanning intervals of imprecise points

Abstract

We study a geometric facility location problem under imprecision.

Given $n$ unit intervals in the real line, each with one of $k$ colors, the goal is to place one point in each interval 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 interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in $O(n)$ time, even for intervals of arbitrary length. For overlapping intervals, we show that the problem can be solved in $O(n^{2}logn)$ time when $k=2$. Interestingly, this shows a sharp contrast with the $2$-dimensional version of the problem, recently shown to be NP-hard.

More events