Michael Hoffmann, Vincent Kusters, Günter Rote, Maria Saumell, and Rodrigo I. Silveira:

Convex hull alignment through translation

In: Proceedings of the 25th Canadian Conference on Computational Geometry, (CCCG'2013), Waterloo, Ontario, August 2013, pp. 295–300.


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.

  pdf file (gzipped)
other papers about this subject
Last update: November 10, 2014.