Rearranging a sequence of points onto a line (Q2144451)

Rearranging the points of a given sequence of points has many practical applications in computer graphics and image processing. So, in this paper, the problem of rearranging a sequence of weighted points in a plane is considered. These points have to be rearranged in such a way that any two consecutive points are at distance no more than their weight difference and the maximum distance between any two points is minimized. In this paper, algorithms are presented that compute optimal rearrangements for three variants of the problem either under the \(L_1\) metric or under the Euclidean metric.