Задача: Каков наименьший возможный диаметр круга, который охватывает заданные N точек на 2D-плоскости?
Какой алгоритм является наиболее эффективным для решения этой проблемы и как онработа
Это задача наименьшего круга . См. Ссылки для ссылок на предлагаемые алгоритмы.
E.Welzl, самые маленькие вмещающие диски (Шарики и эллипсоиды), у Г. Маурера (Ред.), Новые результаты и новые тенденции в Информатика, Конспект лекций в Информатика, Vol. 555, Springer-Verlag, 359–37 (1991)
является ссылкой на «самый быстрый» алгоритм.
Существует несколько алгоритмов и реализаций для задачи Самые маленькие вмещающие шарики .
Для 2D и 3D Реализация Гертнера вероятно, самый быстрый.
Для более высоких измерений (скажем, до 10000) взгляните на https://github.com/hbf/miniball,, который представляет собой реализацию алгоритма Гертнера, Куца иФишер (примечание: я один из соавторов).
Для очень и очень больших размеров алгоритмы core-set (приближение) будут быстрее.
Примечание: Если вы ищете алгоритм для вычисления наименьшей охватывающей сферы из сфер , вы найдете реализацию C ++ в Библиотека алгоритмов вычислительной геометрии (CGAL) .(Вам не нужно использовать весь CGAL; просто извлеките требуемый заголовок и исходные файлы.)
Подход к диаграмме Вороной в самой дальней точке
http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html
оказывается действительно очень хорошим решением для 2-й задачи.Это не итеративно и (почти наверняка) гарантированно точно.Я подозреваю, что это не так хорошо распространяется на более высокие измерения, поэтому в литературе этому уделяется мало внимания.
Если есть интерес, я опишу его здесь - приведенная выше ссылка немного сложна.следовать я думаю.
изменить другую ссылку: http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6704