Geometric Assignment and Geometric Bottleneck

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