Detectando dois tipos de polígonos quase simples

22

Estou interessado na complexidade de decidir se um determinado polígono não simples é quase simples, em um dos dois sentidos formais diferentes: fracamente simples ou não-auto-atravessante . Como esses termos não são amplamente conhecidos, deixe-me começar com algumas definições.

  • Pp0,p1,p2,,pn1pipipi+1modn

  • Um polígono é simples se todos os vértices forem distintos e as arestas se cruzarem apenas em seus pontos finais. Equivalentemente, um polígono é simples se for homeomórfico a um círculo e cada aresta tiver comprimento positivo. Em geral, no entanto, os vértices e as arestas de um polígono podem se cruzar arbitrariamente ou mesmo coincidir. 1n

  • Considere dois caminhos poligonais e cuja interseção é um subcaminho comum de ambos (possivelmente um único ponto). Dizemos que e cruz se seus endpoints alternativo no limite de um bairro do comum subpath . Um polígono é auto-cruzamento se tiver dois subcaminhos de passagem e não-auto-cruzamento caso contrário. 2B A BABAB A BA(0),B(0),A(1),B(1)AB

  • Um polígono é fracamente simples se for o limite de uma sequência de polígonos simples ou, equivalentemente, se houver uma perturbação arbitrariamente pequena dos vértices que torna o polígono simples. Todo polígono fracamente simples é sem auto-cruzamento; no entanto, alguns polígonos sem auto-cruzamento não são fracamente simples.

Por exemplo, considere os seis pontos mostrados abaixo.a,b,p,q,x,y

insira a descrição da imagem aqui

  • O polígono é simples; veja a figura da esquerda.abpqyz

  • O polígono é fracamente simples; a figura do meio mostra um polígono simples próximo. No entanto, esse polígono não é simples, porque ele visita três vezes.ppapbpqyqzqp

  • O polígono é de cruzamento automático, porque os subcaminhos e cruzam. Veja a figura certa para alguma intuição.b p q z y q p apapbpqzqyqbpqzyqpa

  • Finalmente, o polígono (que serpenteia duas vezes ao redor do polígono meio) é não-auto-cruzamento, mas é não simples fracamente. Intuitivamente, o número de giro deste polígono é , enquanto o número de giro de qualquer polígono simples deve ser . (Uma prova formal requer alguma análise de caso, em parte porque o número de virada não é realmente bem definido para polígonos com !)± 2 ± 1 0 papbpqyqzqpapbpqyqzq±2±10

Update (setembro 13): Na figura abaixo, o polígono é não-auto-cruzamento e tem transformando número 1 , mas não é simples fracamente. O polígono tem indiscutivelmente várias sub- passagens não simples , mas não possui sub-caminhos simples . (Eu digo "indiscutivelmente" porque não está claro como definir quando dois passeios não simples se cruzam!)abcabcxyzxpqrxzyx

insira a descrição da imagem aqui

Então, finalmente, aqui estão minhas perguntas reais:

  • Com que rapidez podemos determinar se um determinado polígono é sem auto-cruzamento?

  • Com que rapidez podemos determinar se um determinado polígono é fracamente simples?

O primeiro problema pode ser resolvido no tempo seguinte maneira. Como existem n vértices, existem O ( n 2 ) subcaminhos de vértice para vértice; podemos testar se algum subcaminho em particular é simples no tempo O ( n 2 ) (por força bruta). Para cada par de subcaminhos simples de vértice para vértice, podemos testar se eles se cruzam no tempo O ( n ) . Mas esse não pode ser o melhor algoritmo possível.O(n5)nO(n2)O(n2)O(n)

Não sei se o segundo problema pode ser resolvido em tempo polinomial. Eu acho que posso calcular rapidamente um número de virada bem definido para qualquer polígono não simples (a menos que a união das arestas do polígono seja apenas um caminho, nesse caso, o polígono deve ser fracamente simples); veja minha resposta abaixo. No entanto, o novo exemplo de polígono acima implica que o número 1 que não se cruza e gira automaticamente não implica uma fraqueza simples.

Podemos determinar se um determinado polígono é simples no tempo verificando cada par de arestas para interseção, ou no tempo O ( n log n ) usando um algoritmo de varredura padrão, ou mesmo no tempo O ( n ) usando o método de Chazelle algoritmo de triangulação. (Se o polígono de entrada não for simples, qualquer algoritmo de triangulação lançará uma exceção, um loop infinito ou produzirá uma saída que não é uma triangulação válida.) Mas nenhum desses algoritmos resolve os problemas que estou perguntando. O(n2)O(nlogn)O(n)


1 Branko Grünbaum. Polígonos: Meister estava certo e Poinsot estava errado, mas prevaleceu . Beiträge zur Algebra und Geometrie 53 (1): 57–71, 2012.

2 Ver, por exemplo: Erik D. Demaine e Joseph O'Rourke. Algoritmos de dobramento geométrico: ligações, origami, poliedros . Cambridge University Press, 2007.

Jeffε
fonte
Eu não entendo por que alguém votaria contra esta pergunta ?!
Kaveh
Posso estar entendendo totalmente a pergunta e talvez isso esteja muito errado, mas parece-me que a maneira como você conta os vértices significa que a segunda pergunta necessariamente leva tempo exponencial. Deixe-me explicar: em seu último exemplo, você usa os mesmos vértices várias vezes. Parece fácil construir gráficos onde existe um número exponencial de ciclos únicos.
Joe Fitzsimons
Se sua entrada for o polígono fornecido como em seus exemplos, é possível que a entrada seja exponencial no número de vértices sem nunca repetir um ciclo. Se o gráfico contiver seu exemplo de gráfico (2 e 3) como um subgráfico, ele terá ciclos que não cruzam e ciclos que cruzam. Como resultado, é necessário ler a sequência inteira para garantir que você não tenha nenhum ciclo de cruzamento (que pode ou não ter sido incluído). Isso leva tempo exponencial em no pior caso. n
Joe Fitzsimons
1
@ JoeFitzsimons: A entrada é apenas uma sequência de pontos (ou seja, pares de números reais), que não precisam ser distintos. O tamanho da entrada é o comprimento dessa sequência, não o número de pontos exclusivos. n
21412 Jefferson
2
@ Kaveh: Talvez muito abstrato / especializado? Muitas palavras? Eu deveria ter nomeado os pontos Ga, Ka, Naa, Taa, Tin, Khat ?
21412 Jefferson

Respostas:

2

Parece que a primeira pergunta tem um algoritmo (embora provavelmente também não seja o ideal). Supondo que haja uma travessia, a chave para descobrir que parece ser que as arestas que devem ser encontradas são as imediatamente em ambos os lados do subcaminho comum. Portanto, analisamos todos os pares de pares consecutivos de arestas. Há um número quadrático deles. Se encontrar um par de pares de arestas com vértices de um b c e d e f tal que bordas b c e e f são os mesmos, então seguimos o subpath comum até o fim e inspecionar as arestas que deixá-lo. Se eles formarem uma travessia junto comO(n3)abcdefbcef e d e , então terminamos; caso contrário, passamos ao próximo par. Seguir o subcaminho comum é, no máximo, uma operação de tempo linear, portanto todo o algoritmo é O ( n 3 ) .abdeO(n3)

Essa análise provavelmente não é rigorosa, pois o número de vezes que um subcaminho comum de comprimento linear será seguido não é linear no número de pares de pares. Deve haver apenas um número constante deles. Da mesma forma, se a duração do subcaminho comum mais longo for constante, então estamos bem em termos de quantidade de tempo após os subcaminhos comuns. Eu esperaria que o pior caso ocorra quando houver um único subcaminho de comprimento que é comum aO(O(n)subcaminhos. Então existemO(n)interações e em cada interaçãoO(O(n)O(n)arestas estão sendo seguidas. Mesmo assim, o número de arestas que se seguem éo(n2)e o limite é fornecido pelo número de pares. Assim, eu diria que o verdadeiro limite desse algoritmo éO(n2).O(n)o(n2)O(n2)

Chris Gray
fonte
1
"Seguir o subcaminho comum é no máximo uma operação de tempo linear ..." Isso é verdade? Lembre-se de que os subcaminhos não são idênticos. Um pode dobrar-se para frente e para trás ao longo da imagem do outro. De fato, não está claro (para mim) quando você sabe que está pronto.
Pat Morin
Bom ponto. Seria possível, como uma etapa de pré-processamento, colocar o polígono em algum tipo de forma padrão? Nós escolheríamos caminhos que se dobram imediatamente, assim como vértices que são colineares com seus vizinhos imediatos. Em seguida, a frase que você citou seria mais bem definida - o subcaminho comum consiste em arestas que possuem os mesmos vértices e você sabe que está pronto porque atinge vértices diferentes. Provar que a resposta permanece a mesma no polígono na forma padrão não deve ser muito difícil.
Chris Gray
@ ChrisGray: Talvez, mas não tão facilmente quanto você sugeriu. Se a imagem de é uma árvore, a eliminação recursiva de todos os botões de retorno reduz P a um único ponto. PP
31412 Jeff Jeff
Sim, você está certo, essa ideia não vai funcionar. A figura mais à direita que você forneceu acima seria reduzida para um único ponto.
Chris Gray
Estou planejando deixar a recompensa expirar; metade dos pontos será automaticamente atribuída a esta resposta.
Jeffε
2

Por sugestão de Pat Morin, aqui está minha ideia para calcular o número da curva. Desculpe se isso é um pouco desleixado; Eu ainda estou lutando contra os demônios da notação. Além disso, o comentário de Pat à resposta de Chris revela que eu ignorei alguns casos importantes e degenerados. Mas vou postar aqui de qualquer maneira, caso outros achem útil.

Para qualquer índice , seja θ ( p i ) = θ ( p i - 1 , p i , p i + 1 ) denotar o ângulo externo assinado no vértice p i ; este é o ângulo no sentido anti-horário entre os raios p i - 1 p i e p i p i + 1 , normalizados na faixa - π θ iiθ(pi)=θ(pi1,pi,pi+1)pipi1pipipi+1 . (Toda aritmética do índice é implicitamente mod n .) O número de virada de P é definido como T u r n ( P ) = 1πθiπnP Deixe-me chamar um vérticepiumestímulose ointernoângulo empié igual a0. O ângulo externoθia um estímulo não é bem definida; poderia serπou-π. De maneira mais geral, o número de giro dePé bem definido se, e somente se,Pnão tiver esporas (e nenhum vértices repetidospi=

Turn(P)=12πi=0n1θ(pi).
pipi0θiππPP ). Não é difícil provar que t u r n ( P ) é um número inteiro, se for bem definida; em particular, T u r n ( P ) = ± 1 se P for um polígono simples.pi=pi+1Turn(P)Turn(P)=±1P

Suponhamos agora que contém um pé da forma p r s r q , em que p q e o caminho r s representa a inversão do trajecto s r . Então s é um estímulo; chamada r a raiz de s . Nesse caso, deixe-me definir o ângulo externo em s da seguinte maneira: ˜ θ ( s ) = π s g nPprsrqpqrssrsrss (Mas e se θ ( p , r , q ) = 0 ? Como Pat observa, isso pode realmente acontecer.Provavelmente há algum tipo de maneira recursiva para definir ˜ θ ( s )

θ~(s)=πsgnθ(p,r,q)={πif θ(p,r,q)>0πif θ(p,r,q)<0
θ(p,r,q)=0θ~(s) mesmo neste caso, mas não sei o que é.)

Se é fracamente simples, existe um n -gon ˜ P arbitrariamente próximo de P ; tet ~ s ser o vértice da ~ P mais próximo de P . Como ~ P se aproxima de P , o ângulo interno a ~ s se aproxima de zero. Não é difícil provar (por indução no comprimento de r s ) que o ângulo externo θ ( ~ s ) se aproxima ~ θ ( s ) .PnP~Ps~P~PP~Ps~rsθ(s~)θ~(s)

Se consistir inteiramente em uma caminhada seguida por sua inversão, r s r , então os ângulos externos nos dentes retos r e s ainda não estão bem definidos. Mas neste caso, acredito que P é simples fracamente se e somente se a caminhada r s é não-auto-crossing. (Existem casos mais complexos em que não posso definir um número de viragem modificado razoável, em particular, se o polígono vagar por uma única caminhada. Mas em todos esses casos, parece que o polígono é fracamente simples se, e somente se, é não-auto-cruzamento.)PrsrrsPrs

θ~(pi)=θ(pi)piTurn~(P)=iθ~(pi)/2π=Turn(P~)±1P

Turn~(P)rs can itself contain spurs. The naive algorithm that finds the root of each spur by brute force actually takes Θ(n2) time in the worst case; consider an n-gon that has a subwalk of length Ω(n) that simply alternates between two points.

Jeffε
fonte