Formulação de polígono convexo

Temos uma lista ordenada de comprimentos laterais que podem ser usados para formar um polígono. Existem tais valores ( ). $n$ $n \le 1000$

Agora precisamos descobrir se podemos usar 10 desses valores para formar um polígono convexo não degenerado.

Como abordamos isso? Qualquer coisa na ordem de é aceitável. Melhor se possível. Preciso da idéia geral de como proceder, das propriedades dos polígonos convexos que podem ser explorados aqui, etc. $O(n^2 \log n)$

algorithms computational-geometry Alice
fonte

Posso perguntar o que você precisa disso? Seus limites específicos de entrada e tempo são interessantes ... De qualquer maneira, parece uma pergunta difícil.

Jmite

Duas observações: a convexidade não é importante. Veja isto: cs.mcgill.ca/~cs507/projects/1998/mas/main2.html É fácil determinar se é possível criar um polígono a partir de conjuntos de comprimentos: mathoverflow.net/questions/96617/…

Chao Xu

Isso é para o problema TKCONVEX no Codechef ? O objetivo dessas competições é encontrar os algoritmos relevantes ou pelo menos a literatura relevante por conta própria. (Observe que em Ciência da Computação , não temos política contra concursos em andamento , diferentemente da Matemática .)

Gilles 'pára de ser mau'

@Gilles até o algoritmo abaixo dará uma WA. Isso não é suficiente para corrigir o problema. E nós somos estudantes de graduação que não são tão bons em programação, mas queremos aprender. E concursos motivam a todos. E se aprendermos até 10 novos algoritmos por concurso, o ganho é enorme. Se alguém nos indicar a direção certa (observe que apenas apontar, sem códigos, nada), há mais chances de aprendermos o algoritmo real do problema. Então, apenas tentando aprender ... se eu resolver mais um problema, isso não afetará a tabela de classificação. Então eu acho que isso não importa, se ele nos ajuda a aprender

Alice

Acho que Codechef tem um fórum de discussão onde as pessoas postam soluções após o término do concurso.

precisa

Respostas:

Teorema 1. Para cada polígono com seqüência de comprimento de aresta , existe um polígono convexo com a mesma seqüência de comprimento de aresta. $a_1,\ldots,a_m$

Prova. Aqui .

Definição. são reais não negativos. Satisfaz a desigualdade (estrita) de se para todos . $a_1,\ldots,a_n$ $n$ $n$ $2a_j < \sum_{i=1}^n a_i$ $j$

Teorema 2. A sequência é uma sequência de comprimento da aresta para um polígono se satisfizer a desigualdade de -gon. $a_1,\ldots,a_n$ $n$

Prova. Aqui . (observe que a prova aqui requer matemática avançada e também prova o teorema 1)

O problema é reduzido para:

Dada uma sequência de reais não negativos, encontre uma subsequência do elemento que satisfaça a desigualdade de -gon. $n$ $k$ $k$

Um algoritmo simples: verifique se é uma solução para cada . Se nenhum deles funcionar, não haverá solução. $a_i,\ldots,a_{i+k-1}$ $1 \leq i\leq n-k+1$

Prova. Se tivermos qualquer solução , encontre o maior , de modo que (ex .: existe uma lacuna). Se não existe essa lacuna, estamos prontos. Se houver, também é uma solução. (intuitivamente, usamos o elemento maior na lacuna e removemos o menor elemento). Podemos repetir essa etapa (no máximo vezes) e preencher todas as lacunas. Eventualmente, produzimos uma solução do formato para alguns . $a_{i_1},\ldots,a_{i_k}$ $j$ $a_{i_{j+1}}-a_{i_j}>1$ $a_{i_2},\ldots,a_{i_{j}},a_{i_{j+1}-1},a_{i_{j+1}},\ldots,a_{i_k}$ $k-1$ $a_{i_k}-k+1,a_{i_k}-k,\ldots,a_{i_k}-1,a_{i_k}$ $i$

O algoritmo pode ser feito ingenuamente no tempo . Talvez haja uma maneira mais inteligente de fazer isso. $O(kn)$

Uma questão interessante de acompanhamento:

Dada uma sequência de reais não negativos, encontre a subsequência mais longa , de modo que todo elemento subsequente de satisfaça a desigualdade de -gon . $n$ $S$ $k$ $S$ $k$

Chao Xu
fonte

esse teorema 2 é uma extensão da desigualdade do triângulo? E por que a classificação é necessária? Podemos escolher qualquer subconjunto k dos pontos dados que satisfaça o segundo teorema.

Alice

Você não precisa classificar, a classificação apenas reduz a complexidade do tempo: verifique apenas subsequências em vez de .

O (n)

$O(n)$

2^{n}

$2^n$

Chao Xu

parece não funcionar. tem certeza de que precisamos verificar apenas polígonos nk?

Alice

Forneça um exemplo quando isso não funcionar.

precisa

Existe uma maneira um pouco melhor de fazer isso. Mantenha um total de execução das últimas arestas (adicionando e subtraindo o desse total de execução) e use esse total de execução para verificar a desigualdade de -gon. Isso reduz o tempo de a .

k

$k$

a_{i + k}

$a_{i+k}$

a_{i}

$a_i$

k

$k$

O (k n)

$O(kn)$

O (n)

$O(n)$

Peter Shor