A Labeling Problem for Symbol Maps of Archaeological Sites

摘要

Given a set of n rectangles embedded in the Euclidian plane, we consider the problem of modifying the layout to avoid intersections of the rectangles. The objective is to minimize the total displacement under the additional constraint that the orthogonal order of the rectangles must be preserved. We call this problem MINIMUM-DISPLACEMENT OVERLAP REMOVAL (MDOR). We define the total displacement in the new layout as the sum of the Euclidian distances between the initial position (x,y) and the final position (x',y') of the centers of all rectangles. A layout adjustment is orthogonal-order preserving if the order of the rectangles with respect to the x- and the y-axis does not change. More formally, the order is preserved if and only if for any pair of rectangles r_i and r_j it holds that x_i ≤ x_j ⇒ x'_i ≤ x'_j and that y_i ≤ y_j ⇒ y'_i ≤ y'_j.