Given k finite point sets in the plane, we are interested in finding one translation for each point set such that the union of the translated point sets is in convex position. We show that if k is part of the input, then it is NP-hard to determine if such translations exist, even when each point set consists of at most three points.
The original motivation of this problem comes from the question of whether a given triangulation T of a point set is the empty shape triangulation with respect to some (strictly convex) shape S. In other words, we want to find a shape S such that the triangles of T are precisely those triangles about which we can circumscribe a homothetic copy of S that does not contain any other vertices of T. This is the Delaunay criterion with respect to S; for the usual Delaunay triangulation, S is the circle.
Last update: November 10, 2014.