Минимальный эллипсоид содержащий точки

[Brukvalub]

(Оффтоп)

Как и было очевидно, не стоило изобретать самокат, все уже украдено придумано до нас.

[slavav]

(Оффтоп)

Самокат придуман лет тридцать-сорок назад. Называется вычислительная геометрия. Безумно красиво и интересно. С моей точки зрения.

[proger256]

slavav , спасибо)
Что-то найдено, и аж линейной сложности.

Кстати, мое предположение про 3 точки на границе шара почти верно.
Если шар имеет на границе 1 точку, то двигая по всему пространству возможный центр шара, натыкаемся на остальные точки границей шара меньшего радиуса.
Если шар имеет на границе 2 точку - то бегаем по плоскости - серединному перпендикуляру этих точек. Единственное ограничение - шар может дойти до середины отрезка не наткнувшись границей на другие точки. Значит минимальный шар может быть в центре 2 максимально удаленных точек. Особый случай.
Ну а если шар наткнется на что-то, то он будет иметь не менее 3 точек.

[slavav]

Правильный ответ:
минимальный шар опирается на четыре точки, причём тетраэдр на этих четырёх точках содержит центр шара ИЛИ
минимальный шар опирается на три точки, причём треугольник на этих трёх точках содержит центр шара ИЛИ
минимальный шар опирается на две точки, причём отрезок на этих двух точках содержит центр шара ИЛИ
минимальный шар имеет нулевой радиус и содержит только одну точку, которая совпадает с его центром.

Это я берусь доказать. Всё это конечно свести в одну фразу про шар, небольшое число точек и их выпуклую оболочку.

-- 18.03.2016, 13:46 --

Не могу удержаться. Правильная реализация mindisk не вычисляет центр шара! Удивительный алгоритм.