Есть ли более эффективный способ получить 2-х ближайших соседей всех вершин в (2D) триангуляции Делоне, чем вычислить для каждого набора вершин, достижимых не более двух ребер, и выбрать 2-й ближайший из них?
Потому что даже когда мы знаем, на каком максимальном расстоянии мы его найдем, поиск по дальности все же кажется более медленным.
Это была тема моего экзамена несколько лет назад.
Если вы можете читать по-французски:
http://www.loria.fr/~odevil/master/exam10.pdf
Других решений пока нет …