найти максимальное расстояние в наборе точек

[mrgloom 242]

как быстро найти максимальное расстояние в наборе точек?(быстрее чем перебирать каждую с каждой)

пробовал найти максимумы и минимумы по х,у, но такое решение, не всегда дает правильный результат, когда максимум по диагонали.

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

[Smorodov 579]

Я думаю достаточно близкой аппроксимацией этого расстояния будет диаметр графа (или я Вас не правильно понял?).

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

[mrgloom 242]

а какой граф в данном случае, все со всеми? у меня просто набор точек, или контур допустим.

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

[Smorodov 579]

Можно попробовать через ConvexHull, это прилично сократит кол-во рассматриваемых точек.

[Pavia00 32]

Оно через ConvexHull и делается.

Вычислительная геометрия введение (1989)Препарата Ф., Шеймос М.

[mrgloom 242]

ну ConvexHull это мы получаем выпуклый многогранник вокруг точек, а потом всё равно надо все вершины перебирать?

[Smorodov 579]

Так максимальное расстояние будет между точками, принадлежащими этой оболочке.

[mrgloom 242]

я имел ввиду все вершины оболочки.

[Smorodov 579]

Да,решается полным перебором, но вершин в оболочке не так много.

[Pavia00 32]

а потом всё равно надо все вершины перебирать?

Да перебирать. В книжке приведен алгоритм как сделать такой перебор за N - число точек выпуклой оболочки.

Объяснения в книжке сложные, но алгоритм простой. Страница 221