## 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.
### Abstract

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.