Минимальная окружность, покрывающая множество точек

Дано n точек
Необходимо найти окружность минимального радиуса такую, чтобы все точки лежали либо внутри, либо на границе этой окружности

    Очевидно, что на искомой окружности должны лежать точки, так как если они на ней не лежат, то радиус окружности можно уменьшить и, значит, эта окружность не была минимальной.
    Будем перебирать все тройки точек и строить мнимальную окружность, покрывающую их. После этого будем проверять, принадлежать ли все точки найденной окружности. Из всех подходящих окружностей выберем ту, у которой минимальный радиус. Эта окружность и будет искомой.

    Асимтотика O(N⁴).

Листинг С++

// минимальная окружность, покрывающая три любые точки
circle min_circle_for_three_point (point a, point b, point c)
{
    // если это треугольник, то описываем его
    if (abs (area_triangle (a, b, c)) > eps)
        return described_circle (a, b, c);
    // иначе это отрезок и точка в нём - из середины проводим окружность диаметром в отрезок
    point maxP = max_px (max_px (a, b), c);
    point minP = min_px (max_px (a, b), c);
    return circle (part_segment (maxP, minP, 1, 1), 0.5 * dist (minP, maxP));
}
// минимальная окружность, покрывающая множество точек
circle min_described_circle (vector < point > p)
{
    int n = p.size ();
    int i, j, k;
    circle c = circle (0, 0, 1e9);
    for (i = 0; i < n; ++ i)
        for (j = i + 1; j < n; ++ j)
            for (k = j + 1; k < n; ++ k)
            {
                circle t = min_circle_for_three_point (p[i], p[j], p[k]);
                int u;
                for (u = 0; u < n; ++ u)
                    if (point_in_circle (p[u], t) == 2) break;
                if (u >= n && t.r < c.r)
                    c = t;
            }
    return c;
}

16.07.2009
14:02

По всем вопросам обращаться: rumterg@gmail.com