Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.05.2010, 10:06
Аватар для laseroff
Новичок

Отправить личное сообщение для laseroff Посмотреть профиль Найти все сообщения от laseroff
 
Регистрация: 16.05.2010
Сообщений: 1

Найти точку находящуюся на наименьшем расстоянии от всех остальных
В общем есть множество точек в трехмерном пространстве, надо найти точку которая находится как бы в "центре". Сейчас у меня для каждой точки считается сумма Евклидовых расстояний до всех остальных. Потом из сумм выбирается наименьшая. Существуют ли более быстрые алгоритмы?
  #2  
Старый 16.05.2010, 10:50
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Можно построить минимальную сферу содержащую данные точки, а затем выбрать из них ближайшую к центру сферы. Временная сложность такого алгоритма линейная.
  #3  
Старый 16.05.2010, 10:52
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Или вначале найти среднюю арифметическую всех точек, а потом найти ближайшую к ней. Это проще.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
найти точку пересечения прямой и плоскости oln Математические алгоритмы 4 13.10.2009 07:42
Вычислить прямую, проходящую через заданную точку гость Вычислительная геометрия 10 13.03.2009 17:33
Как найти длины всех простых подциклов в графе? гость Графы 3 07.06.2008 23:14
задача о наименьшем покрытии Катя Реализация, исходники, языки 5 21.05.2008 14:43
найти "случайную" точку пересечения прямых в 3d Igor_34_rus Вычислительная геометрия 9 05.07.2007 16:17