How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians
de Mt Mark Berg, Dhp Dirk Gerrits, Amirali Khosravi, Ignaz Rutter, K. Tsirogiannis, Alexander Wolff · TU/e Research Portal · 2010
Let R be a finite set of red point sites in R^d and let B be a set of n blue point sites in R^d. We want to establish "safe" connections between the red sites by deleting a minimum number of blue sites such that the region controlled by the red sites is connected. More precisely, we want to find a minimum-size subset B_del \\subseteq B such that the red cells in the Voronoi diagram of R \\cup B \\ B_del form a connected region. For |R| = 2 we present an optimal O(n log n)-time algorithm for d = 2, and an O(n^(d-1))-time algorithm for d \\geq 3; we also show that the problem is 3SUM-hard for d = 3. Furthermore, we show that the general problem, where the number of red sites is not a constant, is NP-hard.