Пустой запрос круг алгоритм

Question

Я пытаюсь придумать алгоритм, который будет делать следующее:

Если множество точек дается, найти для точки запроса самый большой круг (с точки запроса в его центр), который не содержит точек из множества.

До сих пор я думал об использовании диаграммы Voronoi для поиска областей (ячеек), которые содержат точки, наиболее близкие к точке сайта набора, а затем использовать список краев из Voronoi для построения трапецеидального разложения. Из декомпозиции я смогу найти, в какой ячейке находится точка запроса, а затем радиус круга будет расстоянием от точки запроса до точки (сайта) этой ячейки. Я думаю, что хранилище, необходимое для создания чего-то подобного, является линейным, так как Voronoi нуждается в O (n) -хранилище, а создание трапецеидальной декомпозиции из Voronoi также может быть выполнено с O (n) хранилищем.

* Редактировать: время запроса должно быть O (logn), что означает, что я не могу перебирать все точки набора по одному.

Правильно ли это, или я чего-то не хватает?

Кроме того, если у кого-то есть ссылки, которые я мог бы рассмотреть относительно этого алгоритма, пожалуйста, дайте мне знать. Спасибо :)

Answer 1

Этот вопрос, кажется, просит расстояние от точки запроса до ближайшей точки к нему в наборе, поэтому одним из способов ответа на него было бы найти ту ближайшую точку. Один из разумно стандартных способов сделать это будет с http://en.wikipedia.org/wiki/K-d_tree, и этот вопрос в общем случае рассмотрен в http://en.wikipedia.org/wiki/Nearest_neighbour_search

Answer 2

Это звучит слишком сложно. Я даже не знаю, что такое диаграмма Ворони, но при условии, что ваши точки все находятся в 2D-плоскости (что, кажется, имеет место, поскольку вы упоминаете круг, а не сферу) это довольно тривиально:

Итерации через все точки и найти точку, которая ближе всего к точке запроса. Это расстояние - это только теорема Пифагора sqrt((point_x - query_x)^2 + (point_y - query_y)^2). Наименьшее расстояние - это радиус круга.