
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.
LEIA TAMBÉM
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.





















