Geometric Assignment and Geometric Bottleneck
Staff - Faculty of Informatics
Date: 11 October 2023 / 15:30 - 16:30
USI East Campus, Room C1.05
Speaker: Prof. Otfried Cheong, SCALGO, Denmark
Abstract:
Let $P$ be a set of at most~$n$ points and let $R$ be a set of at most~$n$ geometric ranges, such as for example disks or rectangles, where each~$p \in P$ has an associated supply $s_{p} > 0$, and each~$r \in R$ has an associated demand~$d_{r} > 0$. An assignment is a set $A$ of ordered triples~$(p,r,a_{pr}) \in P \times R \times \Reals_{>0}$ such that~$p \in r$. We show how to compute a maximum assignment that satisfies the constraints given by the supplies and demands.
Using our techniques, we can also solve minimum bottleneck problems, such as computing a perfect matching between a set of~$n$ red points~$P$ and~$n$ blue points~$Q$ that minimizes the length of the longest edge. For the~$L_\infty$-metric, we can do this in time~$O(n^{1+\eps})$ in any fixed dimension, for the~$L_2$-metric in the plane in time~$O(n^{4/3 + \eps})$, for any~$\eps > 0$.
Biography:
Otfried Cheong received his Ph.D. at FU Berlin in 1992. After holding positions at Utrecht University, Postech, Hong Kong University of Science & Technology, TU Eindhoven, and KAIST, he is currently working with Scalgo on water flow simulations. He is on the editorial board of 'Discrete & Computational Geometry' and 'Computational Geometry: Theory & Applications', and was elected an ACM Distinguished Scientist in 2016. Since 1993, he has written and maintains the vector graphics editor 'Ipe'.
Host: Prof. Evanthia Papadopoulou
