Triângulos de aprendizagem no avião

Eu atribuído meus alunos o problema de encontrar um triângulo consistente com uma coleção de pontos em R 2 , rotulado com ± 1 . (Um triângulo T é consistente com a amostra rotulada se T contém todos os pontos positivos e nenhum dos pontos negativos; por suposição, a amostra admite pelo menos 1 triângulo consistente).$m$$\mathbb{R}^2$$\pm1$$T$$T$

O melhor que eles (ou I) poderiam fazer é um algoritmo executado no tempo , em que m é o tamanho da amostra. Alguém pode fazer melhor?$O(m^6)$$m$

Como o @TsuyoshiIto sugere, existe um algoritmo de tempo para esse problema, devido a Edelsbrunner e Preparata. De fato, seu algoritmo encontra um polígono convexo com o número mínimo possível de arestas que separa os dois conjuntos de pontos. Eles também provam um Ω ( n log n $O(n\log n)$$\Omega(n\log n)$ limite inferior para o problema mais geral no modelo de árvore de decisão algébrica; no entanto, não está claro se esse limite inferior se aplica à caixa do triângulo.

Uma descrição completa do algoritmo é muito longa para ser postada aqui, mas aqui está a idéia básica. Seja o casco convexo dos pontos positivos. Para cada ponto negativo q , considerar as linhas através q que são tangentes a C . Essas linhas dividem o avião em quatro fatias, uma das quais contém C ; deixar W ( q ) ser a cunha oposta aquela que contém C . Finalmente, seja F (a "região proibida") a união de todas as cunhas W ( q ) . Qualquer triângulo separador deve separar C de $C$$q$$q$$C$$C$$W(q)$$C$$F$$W(q)$$C$$F$. Ambos e F podem ser construídos em O ( N log N ) tempo.$C$$F$$O(n\log n)$

Rotule as bordas de alternadamente no sentido horário e anti-horário. Edelsbrunner e Preparata provam ainda que, se existir um triângulo de separação, existe um triângulo de separação cujas arestas são colineares com as arestas de F no sentido horário . Em O ( n ) tempo adicional, podemos encontrar a borda (necessariamente no sentido horário) de F atingida pela primeira vez por um raio de cada borda no sentido horário e ; chame essa vantagem de "sucessora" de $F$$F$$O(n)$$F$$e$$e$ . Os ponteiros sucessores dividem as arestas no sentido horário em ciclos; se houver um triângulo separador, um desses ciclos sucessores terá comprimento 3 (e nenhum terá comprimento maior que 4).

Consulte o documento original para obter mais detalhes:

• Herbert Edelsbrunner e Franco P. Preparata. Separação poligonal mínima . Information and Computation 77 (3): 218-232, 1988.

Parece-me que é suficiente considerar as linhas tangentes dos pontos '-1' no casco convexo dos pontos '+1' como candidatos aos lados de (digamos que os pontos '+1' serão internos para T ).$T$$T$

Pena que não posso publicar imagens aqui. Mas imagine o seguinte: é a linha tangente ao casco convexo que passa por algum ponto '-1'. A é o ponto de tangência. B é o ponto extremo (veja abaixo) em t , e B C é a linha tangente do ponto B ( C é o ponto de tangência).$t$$A$$B$$t$$BC$$B$$C$

Portanto, o algoritmo é o seguinte. Para cada linha das linhas tangentes, podemos tentar construir um triângulo com base nela:$t$

1. Calcule os pontos de interseção de com todas as outras linhas;$t$
2. Encontre um ponto extremo (mais distante de ) B e a linha correspondente t ′ à direita (ou esquerda) de A , de modo que o psdotriangulo A B C (= A B , B C e a parte do casco convexo entre A e C ) não contém pontos '-1' (ou seja, não contém pontos).$A$$B$$t'$$A$$ABC$$AB$$BC$$A$$C$
3. Faça o mesmo com a linha e veja se podemos' fechar 'o triângulo.$t'$

Parece que esse seria um tempo de execução de . Talvez isso possa ser melhorado usando algumas estruturas de dados?$O(m^2)$