kealon(Ruslan)пардон, поиск ближайшей точки если верить википедии несколько хуже O(H*Ln(H)) H - высота дерева
А вот здесь готовая реализация


Я предлагаю этот вариант

Сначала определить четерехугольник из меющихся точек
содержащих в своей площади точку с известной координатой,
а потом определить какая из вершин черерехугольника ближе к искомой точке.

Для этого нужно отдельно осортировать все точки по координатам, отдельно по X
отдельно по Y, когда вы попытаетесь вставить вашу точку
в деревья индексов координат, соседние к ней точки по осям ( 2 по оиси Х 2 по оиси Y )
дадут 4 точки вершин 4-х угольника, содержащего заданную на поверхности.
Останется из 4 точек найти ближайшую.

kealon(Ruslan)ДохтаРЯ предлагаю этот вариант

ДохтаР, вы предлагаете мой вариант, но кажется не представляете сложность построения K-d дерева. По пробуйте сделать дерево для начала или хотя бы оценить сложность его построения

Я не предлагаю чистое k-d дерево , а упрощенный вариант.

kd дерево разбивает простнанство на прямоугольники, я предлагаю
выделять из имеющихся точек четырехугольник.

в kd дереве задаче сведется к 2-м прямоугольникам,
а потом по вашему алгоритму.

Что касается реализации , то когда в длинных срачах в разделе
другие СУБД я постил 2 класса которые должны хранить в себе
самобалансирующееся Р -дерево.

Задача интересная , но в своем окружении я не вижу ее монетизанции,
и поэтому у меня нет мотива развивать мысль и писать код.

SashaMercuryДохтаР,

в одномерном случае очевидным(и классическим) решением было бы упорядочивание элементов по одному ключу (nlgn), в многомерном упорядочивание по нескольким ключам, это видимо то, о чём вы написали. К сожалению вы предлагаете ссылку на википедию, потому спрошу лучше у вас. Какова асимптотика в многомерном случае?


Я не предлагаю каких либо готовых деревьев или алгоритмов ,
я предлагаю решение для конкретной задачи, в массиве множества точек
найти ближайшую к указанной координате.

Многомернойсть отличается только масштабируемой реализацией.
Для многомерного случая коодинтаты точки хранятся не в переменных , а в массиве



приблизительно так....


SashaMercuryВопрос ко всем, вы возможно знаете как реализовать, у меня пока нет идей.
Пусть у нас есть точка x, множество точек p_i, i=1..n.
Как сделать так:
1. Точка x начинает распространять волну.
2. Как только любая из точек p_i получит сигнал, она останавливает алгоритм и говорит о том что она первая получила сигнал.

Кому говорит ?
Какая разница в скорости распостранения волны и сигнала говорения?

Физическая суть волны в том, что если волна ( импульс) запущена, то ее получат все
точки пространства пока она будет иметь достаточную аплитуду для сенсоров точек.

kealon(Ruslan)ДохтаРЯ предлагаю этот вариант

ДохтаР, вы предлагаете мой вариант, но кажется не представляете сложность построения K-d дерева. По пробуйте сделать дерево для начала или хотя бы оценить сложность его построения

Я не вижу необходимости применения универсального алгоритма kd дерева
для данной задачи. Задача решается проще.

kealon(Ruslan)SashaMercuryДохтаР,

в одномерном случае очевидным(и классическим) решением было бы упорядочивание элементов по одному ключу (nlgn), в многомерном упорядочивание по нескольким ключам, это видимо то, о чём вы написали. К сожалению вы предлагаете ссылку на википедию, потому спрошу лучше у вас. Какова асимптотика в многомерном случае?

Вопрос ко всем, вы возможно знаете как реализовать, у меня пока нет идей.
Пусть у нас есть точка x, множество точек p_i, i=1..n.
Как сделать так:
1. Точка x начинает распространять волну.
2. Как только любая из точек p_i получит сигнал, она останавливает алгоритм и говорит о том что она первая получила сигнал.
вот для этого как раз и нужно разбиение плоскости на треугольники по условию Делоне

Кстате вы правы , я вчера подумал над своим алгоритмом , в большенстве случаев ,
и в частности в этом 17691216
алгоритм будет выходить не на 4 угольник , а вырождаться в треугольник.
В данном случае совпадение точек найденных по индексам
X Y будет ближайшей точкой, но это совпадение , в результате поиска алгоритм
должен получить именно четерехугольник из 4 ближайших точек
на плоскости которого содержится заданная координата
от которой мы ищем ближайшую точку.
То есть в некоторых случаях нужно брать не только ближайшие соседние X Y
но и просматривать следующие за ними.

SashaMercuryДохтаР,
о чём вы написали. К сожалению вы предлагаете ссылку на википедию, потому спрошу лучше у вас. Какова асимптотика в многомерном случае?


Да , я говорил о необходисоти иметь свой индекс по каждой размерности пространства.
В этом основная суть идеи.
Ссылку на википедию я привел как порядок действий когда через мерджинг индексов
по размерностям ространства будет определено минимальное количество
точек из которых нужно искать ближайшую.

maytonПредлагаю в качестве промежуточного итога такую табличку

Методы поиска ближайшей точки (условно)

МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА?В обсужденииМетод ДохтарА на К-деревьях?В обсуждении

Можете оспаривать и дополнять. Я не против.

Последний вычеркивай ,
это заключительный этап предыдущего пункта.
На этом этапе идет полный перебор как в первом пункте,
только из гораздо меньшего числа точек.

maytonДихотомический метод ДохтарА;?;В обсуждении


Скорость зависит от алгоритма скорости вставки
значения в дерево или сортированный список .

Время работы с одним множеством умножатеся на количество
измерений пространства + О _4..8 ( как для полного перебора)

maytonПредлагаю в качестве промежуточного итога такую табличку

Методы поиска ближайшей точки (условно)

МетодСложностькомментарииПолный переборo(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)?В обсужденииОбход Змейкой by maytono(n)Быстрее но линейное время остаётся в формулеK-D дерево?В обсужденииДихотомический метод ДохтарА?В обсужденииМетод ДохтарА на К-деревьях?В обсуждении

Можете оспаривать и дополнять. Я не против.

Все что я тут написал это развитие идеи
17691463

Поэтому прошу к авторству добавить Dima T

ДохтаРmaytonДихотомический метод ДохтарА;?;В обсуждении


Скорость зависит от алгоритма скорости вставки
значения в дерево или сортированный список в зависимости от
реализации алгоритма поиска места вставки числа в списко.

Время работы с одним множеством умножатеся на количество
измерений пространства S + О _2,3,4*s ( как для полного перебора)

Так будет точнее универсальнее и масштабируемее.

Dima TЯ бы так решал:
Если конечное множество фиксированное (в котором искать), то превратить его в два ассоциативных массива (или сортированных списка)
Mx[X] = Y и My[Y] = X
Например для точек (1,1), (5,3), (4,2)


для поиска ближайшей от (x,y) сначала проходим по массиву Mx, затем My. в обе стороны каждый. Затем из 4х выбрать ближайшую.
Например для точки (3,3) идем вверх. Следующая точка (4,2), расстояние до нее 1.4, поэтому следующую проверять не надо, т.к. (5,3) дальше.

Тут надо еще подумать как от корней избавится при расчете длины. Заменить на квадраты, т.к. умножение гораздо быстрее. И немного соптимизировать, добавить проверку для Mx => |x - xi| > |y - yi| чтобы не обсчитывать заведомо далекие точки.

От корней избавляться не нужно , у нас еть равенство
квадрат гипотенузы равен суме квадратов катетов,
нет смысла сравнивать корни, можно сравнивать квадратичные значения.
Для вещественных координат нужно все приводить в значения больше единицы,
что бы не попасть в конфуз, так как квадрат числа меньшего единицы меньше
числа возводимого в степень.

ДохтаРДохтаРпропущено...


Скорость зависит от алгоритма скорости вставки
значения в упорядоченое множество в зависимости от
реализации алгоритма поиска места для вставки .

Время работы с одним множеством умножатеся на количество
измерений пространства S + О _2,3,4*s ( как для полного перебора)

Так будет точнее универсальнее и масштабируемее.

Так ще более фундаментально получается.

зы задача интересная и точно где то пригодится ,
меня мучает мысль как это можно продать :)

kealon(Ruslan)mayton,

сложности будет две, подготовка вспомогательной структуры и сам поиск с помощью неё

Позволю себе напомнить условия 17690651 :
AntipichМножество точек N фиксированное и задается в начале.
Поэтому время "подготовительной работы" не критично.
А вот потом пойдет неслабый поток случайных точек,
которым надо найти ближайшую. И как раз этот процесс и надо оптимизировать.

maytonДля целочисленной плоскости в диапазоне short можно весь универсум
проиндексировать. Каждому пикселу сопоставить ссылку на ближайший
объект точки.

Это нормальная цена решения?

Думаю что нет, потому что алгоритмика решения в такой постановке
не масштабируется на 3D.