Cobrindo um polígono simples com círculos

10

Suponha que eu tenha um polígono simples e um número inteiro . Quais são algumas das abordagens existentes para encontrar o menor raio modo que eu possa cobrir com círculos de raio ? Que tal se for corrigido e eu quero minimizar ?SkrSkrrk

cg.comp-geom planar-graphs set-cover user771871
fonte

Respostas:

11

Use o algoritmo de agrupamento k-center: consulte a Seção 4.2 em http://goo.gl/pLiEO .

Pode-se obter o algoritmo de aproximação de 1 + eps usando grades deslizantes.

É natural supor que o problema seja NP-Hard por causa do trabalho de Feder e Greene.

Sariel Har-Peled
fonte
11
Isso é o que a grade deslizante dá-lhe ...
Sariel Har-Peled
Obrigado pela sua resposta. Estou mais ou menos familiarizado com grades deslizantes. No cenário de pontos, ele depende crucialmente de que em cada célula da grade é possível resolver o problema de cobertura de maneira ideal, uma vez que cada disco contém dois pontos em seu limite, mais o número de discos para cobrir a célula é limitado. Assim, pode-se resolver a força bruta. Mas, na configuração de um polígono, não vejo como resolver o problema em uma célula da grade de maneira ideal. Você se importaria de fornecer algumas dicas sobre isso?
101011
As grades deslizantes sugerem que dentro da célula da grade o tamanho da solução é pequeno. Então você precisa resolver o problema dentro de cada célula da grade (geralmente exatamente) usando outro algoritmo. Aqui está uma maneira alternativa de pensar sobre isso - experimente o polígono com muita densidade e resolva o problema na amostra ... E sim, detalhes exatos de como fazer isso podem ser bastante dolorosos ... Então, suponha que você tenha um polígono com n arestas e você sabe que a solução ideal é do tamanho k. Você sabe como resolver o problema exatamente neste caso?
Sariel Har-Peled
Mais uma vez obrigado. Depois de pensar um pouco mais, ainda não sei como cobrir o polígono de maneira ideal com discos k, mesmo que eu saiba k. O fato de haver pouca natureza discreta torna a costura muito difícil para mim. Quanto à sua abordagem de amostragem: Após a amostragem, você gostaria de cobrir apenas a parte amostrada? Não estamos enfrentando o problema de desperdiçar muitos discos para preencher as lacunas?
101011
11
Considere o quadrado. Cubra-o com uma grade , para . É fácil provar que qualquer disco k que cubra todos esses pontos cobriria todo o quadrado depois que você expandir cada disco pela fração de seu raio. Quanto ao polígono, triangule-o, forme uma grade como acima para cada triângulo (isso requer alguns cuidados, mas não é especialmente difícil). Você obtém a mesma garantia, se fizer a união de todos esses conjuntos de pontos. Isso é semelhante à construção do conjunto de cores para o cluster do k-center. N×NN=O(k/ϵ)ϵ
Sariel Har-Peled