Arkin, E. M.; Díaz, J.; Hurtado, F.; Kumar, P.; Mitchell, J. S. B.; Palop, B.; Pérez, P.; Saumell, M.; Silveira, R.I.
Computational geometry: theory and applications
Vol. 48, num. 2, p. 94-107
DOI: 10.1016/j.comgeo.2014.08.004
Date of publication: 2014
Journal article
We study a class of geometric optimization problems closely related to the 2-center problem: Given a set S of n pairs of points in the plane, for every pair, we want to assign red color to a point of the pair and blue color to the other point in order to optimize the radii of the minimum enclosing ball of the red points and the minimum enclosing ball of the blue points. In particular, we consider the problems of minimizing the maximum and minimizing the sum of the two radii of the minimum enclosing balls. For each case, minmax and minsum, we consider distances measured in the L2L2 and in the L8L8 metrics.