An optimal minimization of clustering involves a variant of the NP-complete geometric set cover problem and is intractable, however the near-linear algorithm here should be an improvement on our naive heuristic and might be worth implementing if the naive clustering minimization is too slow or inaccurate.
Pankaj K. Agarwal and Jiangwei Pan. 2014. Near-Linear Algorithms for Geometric Hitting Sets and Set Covers. In Proceedings of the thirtieth annual symposium on Computational geometry (SOCG'14). Association for Computing Machinery, New York, NY, USA, 271–279. https://doi.org/10.1145/2582112.2582152
An optimal minimization of clustering involves a variant of the NP-complete geometric set cover problem and is intractable, however the near-linear algorithm here should be an improvement on our naive heuristic and might be worth implementing if the naive clustering minimization is too slow or inaccurate.
Pankaj K. Agarwal and Jiangwei Pan. 2014. Near-Linear Algorithms for Geometric Hitting Sets and Set Covers. In Proceedings of the thirtieth annual symposium on Computational geometry (SOCG'14). Association for Computing Machinery, New York, NY, USA, 271–279. https://doi.org/10.1145/2582112.2582152