date/vreme: 21/11/2023, 12:00
venue/mesto: Svečana sala FTN
Workshop/radionica: LADIS 4 - Logičko-algebarsko-diskretni susreti PMF@FTN
Speaker / Predavač
Prof. Miloš Stojaković, Departman za matematiku i informatiku, Prirodno-matematički fakultet, Univerzitet u Novom Sadu
https://people.dmi.uns.ac.rs/~milosst/ (home page)
Title / Naslov:
Crveno-plava uparivanja bez presecanja
Abstract / Sažetak:
Za datih n crvenih i n plavih tačaka u ravni želimo da dužima koje se ne presecaju uparimo crvene tačke sa plavim. Najpre ćemo razviti niz alata za lakši rad sa takvim nepresecajućim mečinzima tačaka u konveksnom položaju. Naime, ispostavlja se da se tačke prirodno klasifikuju u grupe koje nazivamo orbitama, i da one dalje imaju čitav niz korisnih osobina.
Bottleneck mečinzi su oni nepresecajući mečinzi crvenih i plavih tačaka za koje je dužina najduže duži minimalna. Primenjujući alate koje smo razvili, dizajniramo algoritme za nalaženje bottleneck mečinga koji su brži od do sada poznatih.
Navedeni rezultati su dobijeni u koautorstvu sa Markom Savićem.