Envelope superior dinâmico de linhas no plano

Existem algoritmos fáceis para calcular o envelope superior de um arranjo de linhas no plano. Veja, por exemplo, a seção 2.3 na pesquisa Sequências de Davenport-Schinzel e suas aplicações geométricas .

Existem algoritmos / estruturas de dados conhecidos para a versão dinâmica do mesmo problema? Ou seja, queremos manter o envelope superior de um conjunto de linhas no plano sob as seguintes operações:

• insert ): adiciona a linha ℓ ao conjunto$(\ell$$\ell$
• delete : remove a linha ℓ do conjunto$(\ell)$$\ell$
• query : retorna a linha com a coordenada x no envelope superior. Em outras palavras, retorne a linha do conjunto que primeiro é atingida por um raio vertical descendente a partir do ponto ( x , ∞ ) .$(x)$$x$$(x, \infty)$

"alguém" está certo. O artigo de Timothy Chan, "Operações planas dinâmicas do casco convexo em tempo amortizado quase logarítmico" parece resolver o problema com inserções / exclusões que levam tempo amortizado e consultas com tempo O ( log n ) . Ele resolve o seu problema, que é dual ao problema convexo do casco.$O(\log ^{1+\epsilon}n)$ $O(\log n)$

A estrutura de dados que eu estava procurando é chamada de pilha paramétrica . Ou seja, um monte em que cada tecla é uma função linear (uma linha) em vez de uma chave fixa. A query(x)operação descrita acima corresponde a uma find-min(x)operação em um heap paramétrico. Existe uma estrutura de dados relacionada, chamada heap cinético , que é um heap paramétrico em que o parâmetro, time, apenas progride para a frente. Em outras palavras, uma vez que temos uma find-min( ) consulta, podemos perguntar ( t $t_1$find-min$t_2$ ) apenas se .$t_2 \geq t_1$

Conforme observado por "alguém", o problema paramétrico do heap pode ser reduzido a um casco plano dinâmico convexo via dualidade de linha de ponto.

A maioria dos artigos que resolvem esse problema usa uma estrutura de dados semi-dinâmica "somente exclusões" e, em seguida, usa uma técnica de dinamização de Bentley e Saxe para transformar sua estrutura de dados e também suportar inserções. ( JL Bentley e JB Saxe, problemas de busca decomposable I:. Transformação Static-to-dinâmica ) Ver também J notas de aula do FFE$\epsilon$ para uma visão geral de como este tipo de obras de transformação.

O resultado clássico nessa área é devido a Overmars e van Leeuwen, Manutenção de configurações no avião , que atingem tempo de consulta O ( log n ) e O $O(\log n)$ (pior caso) tempo de actualização. Se quisermos implementar uma solução para esse problema, esta é a versão a seguir.$O(\log^2 n)$

No entanto, houve subsequentemente várias melhorias teóricas no resultado clássico. No FOCS 99, o artigo de Chan

• Operações planas dinâmicas do casco convexo em tempo amortizado quase logarítmico

deu uma estrutura de dados com tempo amortizado ϵ n)para atualizações.$O(\log^{1+\epsilon} n)$

Posteriormente, os seguintes autores (independentemente) aprimoram os limites de tempo para para exclusões e O ( log n log $O(\log n \log \log n)$$O(\log n \log \log \log n)$

• Casco Convexo Dinâmico Brodal e Jacob Planar na FOCS 2002

• Kaplan, Tarjan e Tsioutsiouliklis montes cinéticos mais rápidos e seu uso na programação de transmissão na SODA 2001

  Todas as citações acima suportam find-minconsultas em $O(\log n)$

$O(\log n)$ tempo amortizado de . Seus resultados são bastante complicados, e eu só consegui encontrar a versão completa do artigo em forma de rascunho ; no entanto, o resultado também é detalhado no Ph.D. de Jacob. Dissertação .

Recentemente, Chan deu outros resultados relacionados a consultas planas dinâmicas do casco planas, incluindo "Uma estrutura de dados totalmente dinâmica para manter um conjunto de n pontos no plano para que possamos encontrar as bordas do casco convexo que cruzam uma linha de consulta".

$\Theta(\log n / \log \log n)$$O(\log n \log \log n)$$O(\log^2 n)$ .