[занимательная геометрия] Метрика Минковского

При условии что задана ориентация taxicab geometry, этой точкой будет центр минимального повернутого на pi/4 описаного квадрата

Описанного вокруг чего? Вокруг двух максимально удаленных друг от друга точек из множетсва?

Вроде звучит логично. Хм. Даже гениально просто, я б сказал )

>>Надо найти минимум функции f(x)=max{||x-x_i||}, где x_i - точки из заданного множества, а x - любая точка плоскости.

Ну так такая конструкция и называется радиусом (ну или диаметром с точностью до множителя) множества.

А в метрике «городского такси» заместо окружности работает квадрат.

Кажись это правильный ответ. Спасибо!

А теперь другой вопрос:

Какая точка является решением задачи Штейнера (сумма расстояний от данной точки до точек из множества минимальна) в данном случае?

mclaud'у молчать, если знает. Все остальные думают.

>>А в метрике «городского такси» заместо окружности работает квадрат.

Но, в отличие от обычной евклидовой нормы, такая норма неинвариантна к повороту системы отсчета и появляется анизотропия. Потому я и оговорил выбор осей координат.

>Ну так такая конструкция и называется радиусом (ну или диаметром с точностью до множителя) множества.

Правильно ли я понимаю, что радиусом множества на евклидовой плоскости является точка Ферма? И правильно ли я понимаю, что в случае обычной метрики найти такую точку в случае переменных больше 3-х невозможно аналитически?

>>Правильно ли я понимаю, что радиусом множества на евклидовой плоскости является точка Ферма?

Если ты про то, что расстояние от точки Ферма до самой удаленной точки является радиусом, то это не так. Диаметр - это свойство лишь пары самых удаленных друг от друга точек, не меняющееся при небольшом сдвиге остальных. А точка Ферма едет при движении любой точки множества.

И правильно ли я понимаю, что в случае обычной метрики найти такую точку в случае переменных больше 3-х невозможно аналитически?

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

>Если ты про то, что расстояние от точки Ферма до самой удаленной точки является радиусом, то это не так. Диаметр - это свойство лишь пары самых удаленных друг от друга точек, не меняющееся при небольшом сдвиге остальных. А точка Ферма едет при движении любой точки множества.

Не всегда. Возьми три точки, которые образуют остроугольный треугольник. Расстояние от точки, делящей самую длинную сторону пополам до третьей вершины может быть больше расстояний от нее до первой/второй вершины

Да хотя бы равносторонни треугольник.

Метрика Минковского - вчерашний день! Даешь финслерову геометрию!!!

>Метрика Минковского - вчерашний день! Даешь финслерову геометрию!!!

Вот ты ржешь, а мне она прямо сейчас помогает вместо того, чтобы писать немаленькую программу на octave (надо решить real-life задачу по мат-моделированию), пойти бухать пиво и трындеть на ЛОРе.

>>Если ты про то, что расстояние от точки Ферма до самой удаленной точки является радиусом, то это не так. Диаметр - это свойство лишь пары самых удаленных друг от друга точек, не меняющееся при небольшом сдвиге остальных. А точка Ферма едет при движении любой точки множества.

Не всегда. Возьми три точки, которые образуют остроугольный треугольник. Расстояние от точки, делящей самую длинную сторону пополам до третьей вершины может быть больше расстояний от нее до первой/второй вершины

Да но диаметр множества не изменится. И радиус тоже, определенный как полудиаметр.

Просто понятие полудиаметра и понятие радиуса минимальной описаной окружности различаются. Я ошибочно смешал их тут http://www.linux.org.ru/jump-message.jsp?msgid=6220250&cid=6220330

Правильно так:

Минимум f(x)=max{||x-x_i||}, где x_i - точки из заданного множества, а x - любая точка плоскости. Такая конструкция и называется радиусом минимальной описанной окружности.

Эта величина всегда больше или равна радиусу (полудиаметру) множества.

>>Правильно ли я понимаю, что радиусом множества на евклидовой плоскости является точка Ферма?

Итого, прикидки дали следующее соотношение

d/2 ≤ r_мин_опис_окр ≤ r_проведенный_из_точки_ферма

Формулировку условий равенства предоставляем читателю ;)

Дык прямоугольный треугольник же.

Для сужения «круга подозреваемых» можно найти «центр тяжести» всех точек, а затем, постепенно увеличивающимся радиусом сканировать, какие точки попадут в гиперсферу. Не пойдет?

Таким образом ты найдешь минимальную сферу, а нужна минимальная из максимальных.

А это

максимальное из расстояний от нее до любой из точек заданного множества было бы минимальным

разве не то же самое?

Куда уж меньше?

Наверное я тебя не совсем правильно понимаю...

Может ты имеешь в виду это:

Ищем минимальный радиус, исходящий из центра тяжести, при котором в окружность попадают все точки? Но ты ограничиваешься окружностью из центра тяжести. А это не есть решением.

Или я опять не так понял?

Не совсем: ищем ЦТ, далее из него строим гиперсферу с некоторым радиусом, считаем, сколько точек в нее влезет. Радиус можно взять равным, скажем, трем сигмам разброса расстояний точек от ЦТ. Потом перебираем точки, попавшие в эту гиперсферу, чтобы найти искомую.

ИМХО, это будет быстрее, нежели деревья расстояний строить с дальнейшим поиском искомого узла.

>>Даешь финслерову геометрию!!!

http://hypercomplex.xpsweb.com

вытекли глаза, теперь придется домысливать финслерову геометрию самостоятельно.

Это если точки три. А в общем случае условие равенства центра описаной окружности точке Ферма весьма нетривиально.

Зачем так сложно? Задача-то - построить миниальный описывающий квадрат (повернутый на 45 градусов) и найти длину его стороны. Меряем штангенциркулем по одной диагонали, получаем a, меряем по другой - получаем b. Берем наибольную из сторон - она и будет искомой. А конкретных квадратов будет бесконечное множество - и все с центрами на отрезке длиной |a-b|. Этот отрезок и будет множеством решений.

вытекли глаза, теперь придется домысливать финслерову геометрию самостоятельно.

Зато не надо всякий бред вроде темной материи и т.п. придумывать :)