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. We also apply our geometric approach to the case of ordered intervals on a closed curve.
(Based on a SOSA 2021 paper by Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud.)