Conjunto disjuntor máximo: qual é o fator de aproximação real do algoritmo guloso?

Considere o problema de encontrar um conjunto máximo disjuntado - um conjunto máximo de formas geométricas não sobrepostas, de uma determinada coleção de candidatos. Este é um problema NP-completo, mas em muitos casos, o seguinte algoritmo ganancioso gera uma aproximação com fator constante:

• Para cada forma candidata x , calcule seu número de interseção separado = o maior número de formas disjuntas que cruzam x .$DIN(x)$
• Selecione uma forma candidata com o menor DIN ( ). Remova-o e todas as formas que ele cruza.$\arg \min_{x} DIN(x)$
• Continue até que não haja mais candidatos.

Por exemplo, considere a seguinte figura na página da Wikipedia:

O disco verde intercepta 5 outros discos, mas seu DIN é 3 (os 3 discos vermelhos são disjuntos). Os discos vermelhos superior e inferior cruzam 2 outros discos, mas eles mesmos se cruzam, portanto, seu DIN é 1. Os discos amarelos têm um DIN igual a 2. O algoritmo ganancioso seleciona, assim, o disco vermelho superior ou inferior.

Se o DIN mínimo pode ser limitado por uma constante, o algoritmo guloso é uma aproximação de fator constante polinomial.

Por exemplo, se todas as formas candidatas são discos unitários, Marathe et al (1995) mostram que sempre existe um disco com um DIN no máximo 3: o disco mais à esquerda (o disco com a menor coordenada x) cruza no máximo 3 outros discos disjuntos . Portanto, o algoritmo ganancioso gera uma aproximação de 3 porque obtém 1 disco para cada (no máximo) 3 discos na solução ideal.

Da mesma forma, se todas as formas candidatas forem discos de tamanho arbitrário, o algoritmo ganancioso gera uma aproximação de 5, porque o menor disco cruza no máximo 5 outros discos disjuntos, ou seja, o DIN mínimo é no máximo 5.

Até aí tudo bem, mas esses fatores de 3 e 5 são justos? Não tenho certeza.

Considere a figura acima. A seleção do disco mais à esquerda (verde) encontrará um conjunto separado de tamanho 1, que é de fato uma aproximação 3 ao conjunto conjunto máximo de tamanho 3 (vermelho), mas o algoritmo ganancioso não selecionará o disco verde - ele selecionará o disco vermelho superior / inferior, cujo DIN é 1. Nesse caso, o algoritmo guloso encontrará a solução ideal.

Não consegui encontrar um contra-exemplo para o geral , em que o algoritmo ganancioso encontra um conjunto disjuntivo com discos de unidade, enquanto o conjunto disjuntor máximo tem . Na verdade, eu não conseguia nem construir um contra-exemplo geral em que o DIN mínimo seja realmente 3. O melhor que pude apresentar é o seguinte, no qual cada disco de unidade intercepta no máximo 2 outros discos disjuntos (ou seja, o DIN mínimo é 2). Mas mesmo aqui, o algoritmo ganancioso encontra a solução ideal em vez de uma aproximação 2:$n$$n$$3n$

Minhas perguntas são:

• Qual é o DIN máximo mínimo real nas coleções de unidades de disco? Discos de tamanho arbitrário?
• Qual é o fator de aproximação real do algoritmo ganancioso para coleções de discos de unidade? Para discos de tamanho arbitrário? (esse fator é no máximo tão grande quanto o DIN mínimo máximo, mas pode ser menor).

UPDATE: Para cada tupla k de formas, , defina = o maior número de formas disjuntas interceptadas pela união . Defina como o DIN mínimo de todas as k-tuplas de formas disjuntas.$x_1,...,x_k$$DIN(x_1,...,x_k)$$x_1\cup...\cup x_k$$minDIN_k$

Por exemplo, na resposta de Yury abaixo, , porque cada círculo cruza 3 outros círculos. , porque é possível selecionar 2 círculos separados, um do círculo externo e outro do círculo interno, que juntos interceptam apenas outros 4 círculos. Para cada , .$minDIN_1=3$$minDIN_2=4$$k$$minDIN_k\leq k+2$

Eu acho que a taxa de aproximação do algoritmo ganancioso pode ser limitada por , porque, para cada na solução ideal, temos pelo menos formas na saída do algoritmo. Isso está correto?$\frac{minDIN_k}{k}$$minDIN_k$$k$

Edição: Agora estou lendo o excelente livro Pesquise problemas em geometria discreta . Embora não tenha encontrado esse problema exato, encontrei um problema que parece relacionado. Na seção "2.5 Embalagens finas com muitos vizinhos", há exemplos de embalagens circulares nas quais cada círculo toca em outros 5 círculos. Gostaria de saber se essa embalagem pode produzir uma configuração de círculos com DIN = 5.

Qual é o DIN mínimo máximo real nas coleções de unidades de disco?

É 3.