Please note: This PhD seminar will take place online.
Anurag Murty Naredla, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Anna Lubiw
In the dispersion problem for ordered intervals, the input is an ordered list of intervals on the real line, and the task is to select one point from each interval, such that the ordering of points along the line respects the given ordering of intervals and such that the points are “far apart” from each other.
Li and Wang (Discrete Applied Math., 2018) gave a linear time algorithm for dispersion on ordered intervals that maximizes the minimum distance between any two points. We give a simpler linear time algorithm for the stronger goal of maximizing the minimum distance, then maximizing the second minimum distance, and so on. Our algorithm transforms the problem into a shortest path problem in a simple polygon. The result is based on very elementary ideas and was published at SOSA 2021.
We also apply our geometric approach to the case of ordered intervals on a closed curve and some other variants of the problem where earlier techniques do not seem to be applicable. We also sketch (without details) some results in 2D dispersion (published at ESA 2021).
Joint work with Therese Biedl, Anna Lubiw, Peter Ralbovsky, and Graeme Stroud.