Implémentation d'arbres de partition?

11

Des arborescences de partition ont-elles déjà été implémentées?

Ici, je parle des arbres de partition de la géométrie de calcul. Les premières versions (presque) optimales étaient dues à Matousek et à d'autres, et plus récemment à Timothy Chan:

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

Cela me semble fou que ceux-ci n'aient jamais été implémentés, mais la recherche sur Google n'a révélé aucune implémentation sur laquelle personne n'a jamais signalé.

ds.data-structures implementation computational-geometry Pat Morin
la source
D'où vient cette citation? Mon lecteur PDF ne le trouve pas dans le document de T. Chan auquel vous êtes lié.
jbapple
C'est à partir d'un manuscrit, pas du papier de Chan. Je veux juste vérifier cela aussi complètement que possible avant qu'il ne soit publié.
Pat Morin du
6
Je ne connais pas le contexte de cette question, mais: (1) Si vous examinez un manuscrit, je ne pense pas qu'il soit acceptable de partager une partie du manuscrit en cours d'examen comme ceci. (2) Un article ne devrait pas faire une telle affirmation car même si elle est vraie, elle n'est pas vérifiable. Par exemple, personne ne peut exclure la possibilité que quelqu'un les ait mis en œuvre en tant que projet personnel et n'a jamais pris la peine de le partager publiquement.
Tsuyoshi Ito
1
Merci pour les conseils utiles. C'est un manuscrit d'une thèse écrite par mon étudiant. Je reformulerais probablement ceci: malgré une recherche approfondie, nous ne connaissons aucune implémentation d'arbres de partition. (La recherche approfondie est ce que je fais maintenant, en partie avec cette question.)
Pat Morin
2
Pourriez-vous simplifier la question en supprimant la citation du manuscrit? Actuellement, votre message implique deux questions (dont aucune n'est explicitement énoncée): (1) Comment dois-je vérifier la véracité de l'affirmation selon laquelle les arborescences de partition n'ont jamais été mises en œuvre? Réponse: Vous ne devriez pas. (2) Les gens connaissent-ils des implémentations d'arbres de partition? Je ne connais pas la réponse à cette partie, mais je pense que c'est bien comme question. Le seul problème avec (2) est que personne ne peut dire «non» à cette question, mais vous pouvez en déduire après un certain temps si personne ne propose une implémentation.
Tsuyoshi Ito du

Réponses:

3

Selon la définition du document lié à la page 5, l'énoncé est faux. Les arbres de partition d'espace binaire (BSP) ont été utilisés pendant des décennies sur l'infographie pour accélérer les requêtes spatiales, tout comme les quadtre et les octrees . Les arbres Kd sont largement utilisés dans l'apprentissage automatique pour accélérer les recherches du plus proche voisin. Si vous plissez les yeux un peu, les arbres de décision correspondent également à la définition générale.

Neil Toronto
la source
2
Oui, j'en étais conscient. Ce que je n'ai pas trouvé, cependant, est une implémentation d'une arborescence BSP pour les ensembles de points qui fait tout ce qui est nécessaire pour garder également son numéro de stabilisation proche de O (sqrt (n)).
Pat Morin
3
Ce ne sont pas des arbres de partition au sens où la question se pose. Je pense que l'OP recherche spécifiquement des structures de données pour la recherche sur une demi-plage d'espace.
Mikola