Реализация деревьев разделов?

11

Были ли когда-либо реализованы деревья разделов?

Здесь я говорю о деревьях разбиений из вычислительной геометрии. Самые ранние (почти) оптимальные версии были из-за Matousek и других, а совсем недавно Тимоти Чана:

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

Мне кажется безумным, что они никогда не были реализованы, но поиск в Google не дал никаких реализаций, о которых кто-либо когда-либо сообщал.

ds.data-structures implementation computational-geometry Пэт Морин
источник
Откуда эта цитата? Мой читатель PDF не находит его в газете T. Chan, на которую вы ссылаетесь.
Jbapple
Это из рукописи, а не из бумаги Чана. Я просто хочу проверить это как можно более тщательно, прежде чем оно будет опубликовано.
Пэт Морин
6
Я не знаю контекста этого вопроса, но: (1) Если вы просматриваете рукопись, я не думаю, что можно поделиться частью рассматриваемой рукописи следующим образом. (2) Бумага не должна предъявлять такие требования, потому что даже если она верна, она не подлежит проверке. Например, никто не может исключить возможность того, что кто-то реализовал их как личный проект и никогда не удосужился поделиться им публично.
Tsuyoshi Ito
1
Спасибо за полезный совет. Это рукопись диссертации, написанной моим учеником. Я бы, вероятно, перефразировал бы так: несмотря на тщательный поиск, мы не знаем ни о каких реализациях деревьев разделов. (Тщательный поиск - вот что я делаю сейчас, частично с этим вопросом.)
Пэт Морин
2
Не могли бы вы упростить вопрос, удалив цитату из рукописи? В настоящее время ваш пост подразумевает два вопроса (ни один из которых прямо не указан): (1) Как мне проверить достоверность утверждения о том, что деревья разделов никогда не были реализованы? Ответ: не стоит. (2) Знают ли люди какие-либо реализации деревьев разделов? Я не знаю ответ на эту часть, но я думаю, что это хорошо, как вопрос. Единственная проблема с (2) - никто не может сказать «нет» на этот вопрос, но вы можете сделать вывод, что через некоторое время никто не придумает реализацию.
Tsuyoshi Ito

Ответы:

3

По определению в связанном документе на странице 5, это утверждение неверно. Деревья двоичных пространственных разделений (BSP) десятилетиями использовались в компьютерной графике для ускорения пространственных запросов, так же как и квадраты и октреи . Kd-деревья широко используются в машинном обучении для ускорения поиска ближайших соседей. Если вы немного косите, деревья решений также соответствуют общему определению.

Нил Торонто
источник
2
Да, я знал об этом. Однако чего я не нашел, так это какой-либо реализации дерева BSP для наборов точек, который выполняет любые изворотливые действия, необходимые для того, чтобы его число ударов оставалось близким к O (sqrt (n)).
Пэт Морин
3
Это не деревья разделов в том смысле, что задает вопрос. Я думаю, что ОП специально ищет структуры данных для поиска в полупространстве.
Микола