Não tem condições de realizar esse tipo de busca sem otimizar a estrutura de dados antes, eu pensaria em uma forma de criar algum cluster de regiões maiores e ficar medindo com base nela tipo alguma estrutura de árvore mas sem conhecer o que você tem a disposição fica dificil