Tecnologia

Algoritmo acelera a escolha de quatro cores para mapas planos

Uma equipe internacional apresentou dois métodos. O mais recente, divulgado em preprint, gasta tempo proporcional ao tamanho da entrada.

Diagrama de quatro regiões. Três triângulos vizinhos têm tons diferentes entre si e da área ao redor.
Exemplo de mapa com quatro cores · Matutino

Uma equipe de seis pesquisadores apresentou um algoritmo para colorir mapas planos com até quatro cores sem repetir a cor em regiões que compartilham uma fronteira. A Universidade de Copenhague divulgou os resultados em 17 de novembro, após o primeiro trabalho da equipe receber o prêmio de melhor artigo em uma conferência de computação teórica.

O teorema das quatro cores, demonstrado em 1976, garante que a coloração existe. A contribuição dos novos trabalhos é reduzir o tempo necessário para encontrá-la.

Do mapa ao grafo

Para fazer o cálculo, cada região é representada por um ponto e cada fronteira compartilhada, por uma ligação entre dois pontos. Em um mapa plano, essa rede pode ser desenhada sem cruzamentos entre ligações. Regiões que só se tocam em um vértice podem ter a mesma cor.

No artigo premiado, o tempo de cálculo cresce pouco acima da proporção do tamanho da entrada. O trabalho mais recente, divulgado como preprint, descreve um método de tempo linear.

No método mais rápido, os pesquisadores reorganizam as informações da rede antes de iniciar as etapas mais custosas da coloração. Isso reduz o trabalho necessário à medida que o número de regiões aumenta.

O tempo linear descreve o crescimento do custo do algoritmo em função da entrada. O estudo não fornece um cronômetro de execução para aplicativos de cartografia.

Compartilhe

Encontrou um erro? Fale com a redação.

Últimas

Em perspectiva

Mais notícias