Seminář G²OAT: Computing largest minimum color-spanning intervals of imprecise points

Kdy

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

Kde

Místnost TH:A-1247

Thákurova 7, Praha 6

V rámci pravidelného pondělního semináře skupiny G²OAT vystoupí Maria Saumell Mendiola z Katedry teoretické informatiky FIT ČVUT. Během své odborné přednášky se bude zabývat geometrickým problémem umístění bodů v intervalech různých barev na reálné přímce s cílem maximalizovat velikost minimálního barevného intervalu.

Web akce

Abstrakt

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.