An approach to optimize centroid-based clustering of flat objects is suggested, which is practically important for efficiently solving metric facility location problems. In such problems, the task is to find the best warehouse locations to optimally service a given set of consumers. An example is assigning mobiles to base stations of a wireless communication network. We suggest a hexagonal-pattern-based approach to partition flat nodes into clusters quicker than the