Dado n círculos com raio r1 ... rn, posicione-os de forma que nenhum círculo se sobreponha e o círculo delimitador seja de raio "pequeno".

O programa pega uma lista [r1, r2, ... rn] como entrada e exibe os centros dos círculos.

Peço "pequeno" porque o raio "mínimo" o converte em um problema muito mais difícil (a versão mínima já foi comprovada como NP difícil / completa - veja a nota de rodapé no final da pergunta). Nós não precisamos do mínimo. Se a forma criada pelos círculos parece ser bastante circular, isso é bom o suficiente.Você pode assumir que Rmax / Rmin <20, se ajudar.Uma preocupação de baixa prioridade - o programa deve ser capaz de lidar com mais de 2000 círculos. Para começar, até 100-200 círculos devem ficar bem.Você deve ter adivinhado que os círculos não precisam ser agrupados com força ou mesmo se tocando.

O objetivo é criar um arranjo visualmente agradável dos círculos indicados, que podem caber dentro de um círculo maior e não deixar muito espaço vazio. (como os círculos em umimagem do teste de daltonismo)

Você pode usar o código Python abaixo como ponto de partida (você precisaria de numpy e matplotlib para esse código - "sudo apt-get install numpy matplotlib" no linux) ...

import pylab
from matplotlib.patches import Circle
from random import gauss, randint
from colorsys import hsv_to_rgb

def plotCircles(circles):
    # input is list of circles
    # each circle is a tuple of the f,orm (x, y, r)
    ax = pylab.figure()
    bx = pylab.gca()
    rs = [x[2] for x in circles]
    maxr = max(rs)
    minr = min(rs)
    hue = lambda inc: pow(float(inc - minr)/(1.02*(maxr - minr)), 3)

    for circle in circles:
        circ = Circle((circle[0], circle[1]), circle[2])
        color = hsv_to_rgb(hue(circle[2]), 1, 1)
        circ.set_color(color)
        circ.set_edgecolor(color)
        bx.add_patch(circ)
    pylab.axis('scaled')
    pylab.show()

def positionCircles(rn):
    # You need rewrite this function
    # As of now, this is a dummy function
    # which positions the circles randomly
    maxr = int(max(rn)/2)
    numc = len(rn)
    scale = int(pow(numc, 0.5))
    maxr = scale*maxr

    circles = [(randint(-maxr, maxr), randint(-maxr, maxr), r)
               for r in rn]
    return circles

if __name__ == '__main__':
    minrad, maxrad = (3, 5)
    numCircles = 400

    rn = [((maxrad-minrad)*gauss(0,1) + minrad) for x in range(numCircles)]

    circles = positionCircles(rn)
    plotCircles(circles)

Informações adicionadas: o algoritmo de empacotamento circular geralmente referido nos resultados de pesquisa do Google não é aplicável a esse problema.

A declaração do problema do outro "algoritmo de empacotamento circular" é assim: Dado um K complexo (os gráficos nesse contexto são chamados de complexos simples ou complexos em suma) e condições de contorno apropriadas, calcule os raios do empacotamento circular correspondente para K .. ..

Basicamente, parte de um gráfico que indica quais círculos estão se tocando (os vértices do gráfico indicam círculos e as arestas indicam a relação toque / tangencial entre os círculos). É preciso encontrar os raios e as posições do círculo para satisfazer a relação tocante indicada pelo gráfico.

O outro problema tem uma observação interessante (independente desse problema):

Teorema da Embalagem do Círculo - Todo empacotamento circular possui um gráfico planar correspondente (esta é a parte fácil / óbvia) e todo gráfico planar possui um empacotamento circular correspondente (a parte não tão óbvia). Os gráficos e as embalagens são duplos e são únicos.

Não temos um gráfico planar ou uma relação tangencial para começar no nosso problema.

Este papel -Robert J. Fowler, Mike Paterson e Steven L. Tanimoto: A embalagem e a cobertura ideais no plano são NP-Complete - prova que a versão mínima desse problema é NP-complete. No entanto, o documento não está disponível online (pelo menos não facilmente).