Implementação de árvores de partição?

11

As árvores de partição já foram implementadas?

Aqui, eu estou falando sobre as árvores de partição da geometria computacional. As primeiras (quase) ótimas versões foram devidas a Matousek e outros, e mais recentemente a Timothy Chan:

https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf

Parece loucura para mim que isso nunca tenha sido implementado, mas o Google não encontrou implementações sobre as quais alguém já tenha relatado.

ds.data-structures implementation computational-geometry Pat Morin
fonte
De onde é essa citação? Meu leitor de PDF não o encontra no artigo de T. Chan ao qual está vinculado.
Jbapple #
É de um manuscrito, não do papel de Chan. Eu só quero verificar isso o mais completamente possível antes que seja publicado.
Pat Morin
6
Não conheço o contexto dessa pergunta, mas: (1) Se você estiver revisando um manuscrito, não acho que seja bom compartilhar parte do manuscrito sob revisão como este. (2) Um artigo não deve fazer uma afirmação como essa porque, mesmo que seja verdade, não é verificável. Por exemplo, ninguém pode descartar a possibilidade de alguém os ter implementado como um projeto pessoal e nunca se dar ao trabalho de compartilhá-lo publicamente.
Tsuyoshi Ito
1
Obrigado pelo conselho útil. É um manuscrito de uma tese escrita pelo meu aluno. Eu provavelmente reformularia como: apesar de pesquisar minuciosamente, não temos conhecimento de nenhuma implementação de árvores de partição. (Procurando completamente é o que eu estou fazendo agora, em parte com esta questão.)
Pat Morin
2
Você poderia simplificar a pergunta removendo a citação do manuscrito? Atualmente, sua postagem implica duas perguntas (nenhuma das quais é explicitamente declarada): (1) Como devo verificar a veracidade da alegação de que as árvores de partição nunca foram implementadas? Resposta: Você não deveria. (2) As pessoas conhecem alguma implementação de árvores de partição? Não sei a resposta para esta parte, mas acho que está bem como uma pergunta. O único problema com (2) é que ninguém pode dizer "não" a essa pergunta, mas você pode deduzi-lo depois de algum tempo, se ninguém aparecer com uma implementação.
Tsuyoshi Ito

Respostas:

3

Pela definição no artigo vinculado na página 5, a afirmação está errada. Partição espaço binário (BSP) árvores têm sido usados há décadas em computação gráfica para acelerar as consultas espaciais, assim como quadtrees e octrees . As árvores Kd são usadas extensivamente no aprendizado de máquina para acelerar as pesquisas dos vizinhos mais próximos. Se você apertar os olhos um pouco, as árvores de decisão também se encaixam na definição geral.

Neil Toronto
fonte
2
Sim, eu estava ciente disso. O que eu não encontrei, no entanto, é qualquer implementação de uma árvore BSP para conjuntos de pontos que faça qualquer coisa sofisticada necessária para também manter seu número de punhaladas próximo a O (sqrt (n)).
Pat Morin
3
Essas não são árvores de partição no sentido em que a pergunta está sendo feita. Eu acho que o OP está procurando especificamente estruturas de dados para pesquisa no intervalo de meio espaço.
Mikola