Facebook

[Boriskin]

Решение сильно зависит от определения метрики одинокости ))

"Максимальное расстояние до ближайшей звезды."

[crypto5]

Решение сильно зависит от определения метрики одинокости ))

"Максимальное расстояние до ближайшей звезды."

А слово "максимальное" подразумевает что нужно учесть еще и траекторию звезд и исменение расстонаяния со временем? ))

[Boriskin]

Мне ничего не говорили на тему учитывания законов всемирного тяготения и факта движения звезд в галактике. Это, видимо, задача для тех, кто из Гугля хочет уволиться богатым.

[АццкоМото]

"Максимальное расстояние до ближайшей звезды."

Ну, это, по идее, совсем другая задача. И, КМК, сложнее.

[Boriskin]

"Максимальное расстояние до ближайшей звезды."

Ну, это, по идее, совсем другая задача. И, КМК, сложнее.

Я с т.з. геометрии

[АццкоМото]

Я с т.з. геометрии

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

[Tarasik]

"Максимальное расстояние до ближайшей звезды."

Ну, это, по идее, совсем другая задача. И, КМК, сложнее.

Дейкстра в помощь ? On^3 ?

[crypto5]

"Максимальное расстояние до ближайшей звезды."

Ну, это, по идее, совсем другая задача. И, КМК, сложнее.

Дейкстра в помощь ? On^3 ?

Помоему самый наивный подход за N^2 решается

[Boriskin]

Помоему самый наивный подход за N^2 решается

Yup, лобовой перебор "макс из мин".

[АццкоМото]

но, блин, должен же быть способ фефектифнее. но не только додуматься, даже нагуглить не получается
пока единственная мысль заключается в том, что если L - расстояние от самой одинокой звезды до ближайшей, то ближе, чем (для простоты пусть будут на плоскости) L/sqrt(2) по осям координат ничего нет. и если как-нибудь разбивать отрезки (Xmin, Xmax) и (Ymin, Ymax) пока не начнут появляться "квадратики" с одной звездой... но навскидку худший случай все равно будет около O(N*N)
И еще "самых одиноких" может быть больше одной, причем в общем случае - сколь угодно много, что тоже не добавляет оптимизма

[crypto5]

но, блин, должен же быть способ фефектифнее. но не только додуматься, даже нагуглить не получается
пока единственная мысль заключается в том, что если L - расстояние от самой одинокой звезды до ближайшей, то ближе, чем (для простоты пусть будут на плоскости) L/sqrt(2) по осям координат ничего нет. и если как-нибудь разбивать отрезки (Xmin, Xmax) и (Ymin, Ymax) пока не начнут появляться "квадратики" с одной звездой... но навскидку худший случай все равно будет около O(N*N)
И еще "самых одиноких" может быть больше одной, причем в общем случае - сколь угодно много, что тоже не добавляет оптимизма

Мне кажется там нужно спатиальные индексы юзать, вроде r-tree. Думаю создание дерева будет где-то О(nlogn), и потом найти ближайшую звезду для данной звезды O(logn), найти для каждой звезды ближайшую и вычислить к ней растояние - O(nlogn), найти максимальное расстояние к ближайшей звезде O(n), и того получаем O(nlogn).
Это все среднее время, худшее у операций над r-tree вроде линейное и все ломается.

[АццкоМото]

crypto5, очень похоже на правду. в деталях до конца не осознал, как эти r-trees и их различные варианты работают, но все указывает на то, что их доктор прописал