Диаметр множества. Объясните что это такое :-))

← →
Pat © (2003-04-06 21:39) [0]

Дано евклидово пространство размерностью n, в котором находится k точек. Составить программу нахождения диаметра данного множества (максимального расстояния между точками множества). Вывести координаты диаметра.
Собственно, объясните мне, что такое диаметр множества. Как его найти...и как считаются координаты диаметра.
P.S. Просьба к книгам не отправлять. Просто ответьте, кто знает.

← →
kaif © (2003-04-06 21:44) [1]

Ты же сам говоришь, что диаметром называется
"максимальное расстояние между точками множества".
Так в чем проблема?
Другое дело, что простой перебор всех расстояний при большом числе точек может оказаться слишком плохим алгоритмом...
Расстоянием между двумя точками, я так думаю, называется корень квадратный из суммы квадратов расстояний по всем осям системы координат.

← →
Pat © (2003-04-06 21:50) [2]

>kaif © (06.04.03 21:44)
ОК...с расстоянием, вообще-то больших проблем не было. Да и там все точки вручную вводятся. Так что, обычный перебор подошел..
А как быть с координатами диаметра? :-(( Вот тут совсем глухо. Хотя есть мысль, что это середина вектора, соединяющего крайние точки диаметра...

← →
uw © (2003-04-06 21:53) [3]

Ну, пусть это будут координаты начала и конца.

← →
NetBreaker666 © (2003-04-06 23:32) [4]

Если метрич. пространство - евклидово, то метрика (т.е. расстояние) задается как sum((x[i]-y[i])^2) ^(1/2).
Диаметр - максимальное расстояние мажду двумя точками множества.
Его координаты - есть координаты точек.
Условие задачи не корректно: тебе дано множество из пространства. (А не само пространство).

Можно тупым перебором, но алгоритмы и побыстрее. Ща на метро опаздываю - если интересно - завтра расскажу.

← →
Pat © (2003-04-07 00:58) [5]

Естественно интересно... :-))
Вот только не понятна формула sum((x[i]-y[i])^2) ^(1/2).
Всю жазнь расстояние считал как sqr((x1-x2)^2+(y1-y2)^2) - это для двухмерного пространства..аналогично и для n-мерного, только корень n-ой степени и сумма квадратов по всем координатам...

>Диаметр - максимальное расстояние мажду двумя точками множества.
Теперь для тех, кто в Таньке...т.е. для меня :-)) Это значит, что нужно найти всевозможные расстояние между всеми точками и выбрать среди них наибольшее. Это и будет диаметр. Так или я что-то не правильно понял?

← →
panov © (2003-04-07 01:36) [6]

Координаты диаметра... Ну-ну...

← →
MBo © (2003-04-07 06:27) [7]

>Вот только не понятна формула
Корень из суммы разностей координат двух точек по всем измерениям

k,l - номера точек
Sqrt(Sum по i до N, где N-размерность пространства Sqr(X[i,k]-X[i,l]))
X-общее обозначение координат, т.е., например, для трехмерного случая X[1]=x, X[2]=y, X[3]=z

← →
Думкин © (2003-04-07 07:15) [8]

Диаметр множества скаляр. О каких координатах может идти речь?
Другое дело найти координаты точек, где сей "диаметр" реализуется.

← →
kaif © (2003-04-07 10:17) [9]

Я думаю, что центром лучше всего называть точку, делящую "диаметр" пополам. То есть. если ты нашел две максимально удаленные точки, то это будет точка с координатами:
x2-x1/2,y2-y1/2....,
где x1 и x2 - координаты двух "крайних" точек по оси x и так далее.

← →
Pat © (2003-04-07 15:56) [10]

>Координаты диаметра... Ну-ну...
Почему диаметр не может быть вектором?

потому что диаметр - скалярная величина, геометрическая характеристика.

По определению
\diam M = sup_{x,y \in M} ||x-y||

diam M = sup ||x-y|| x,y in M

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

Кстати, ты не думал над способом задания множества? В общем случае задачка неразрешимая :)

> Естественно интересно... :-))
> Вот только не понятна формула sum((x[i]-y[i])^2) ^(1/2).
> Всю жазнь расстояние считал как sqr((x1-x2)^2+(y1-y2)^2)
> - это для двухмерного пространства..аналогично и для n-мерного,
> только корень n-ой степени и сумма квадратов по всем координатам...

Для n-мерного пространства в евклидовом метр. пр-ве метрика задается как SQRT(SUMM((x[i]-y[i])^2, i=1..n)) (если в терминах Maple :) )

По-моему все и так понятно. Диаметр - максимальный корень квадратный из суммы квадратов разниц координат по каждой оси между каждыми двумя точками. Центр - видимо, просто центр отрезка, соединяющего две точки, расстояние между которыми максимально.
Единственное противоречие, которое мне бросается в глаза, так это то, что непонятно, что считать центром, если нашлись 2 пары точек, расстояния между которыми (в каждой паре) в точности равны диаметру множества.
Я думаю именно это противоречие сводит на нет понятие центра.

> MBo © (07.04.03 16:06)

геометрические характерстики - это и многое иное. В данном случае речь, действительно, - просто о скаляре.

> kaif © (07.04.03 22:49)
Зачем мучить себя определениями, которые в угоду кому-то высасывать из пальца?
Если так, то что есть: "Прибыльно-убыточная экономика в свете планово-неубыточного факториала псевдодурости?"

Диаметр множества. Объясните что это такое :-)) Найти похожие ветки