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


11. 12. 2023
13:00 – 14:00


Room TH:A-1247

Thákurova 7, Prague 6

Maria Saumell Mendiola from the Department of Theoretical Computer Science, FIT CTU, will speak at the regular Monday seminar of the G²OAT group. During his talk, he will discuss a geometric facility location problem involving placing points in intervals of different colors on the real line to maximize the size of a minimum color-spanning interval.

Event website


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 l o g n ) time when k = 2 . Interestingly, this shows a sharp contrast with the 2 -dimensional version of the problem, recently shown to be NP-hard.