We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own, given region. Different shapes of placement regions and different sets of alignment orientations are also considered. More generally, we assume that a graph is given on the points, and only the alignments of points that are connected in the graph count. We show that for planar graphs the problem is NP-hard, and we provide inapproximability results for general graphs. For the case of trees and planar graphs, we give approximation algorithms whose performance depends upon the shape of the given regions and the set of orientations. When the orientations to consider are the ones given by the axes and the regions are axis-parallel rectangles, we obtain a polynomial time approximation scheme.
Cabello and van Kreveld REF studied approximation algorithms for aligning points octilinearly, where each point can be placed anywhere in a locally defined region.
Approximation algorithms for aligning points
SCG '03
Computer Science