Skip to content

Randomized Incremental Algorithm

Introduction

Randomized incremental algorithm is an important algorithm in computational geometry. It requires minimal theoretical knowledge, has low time complexity, and is widely applicable.

The idea of the incremental algorithm is similar to the principle of mathematical induction. Its essence is to reduce a problem to a subproblem of exactly one smaller size. After solving the subproblem, the current object is added. Expressed recursively:

\[ T(n)=T(n-1)+g(n) \]

The incremental algorithm has a concise form and can be applied to many geometric problems.

The incremental algorithm is often combined with randomization to avoid worst-case scenarios.

Minimum Enclosing Circle Problem

Problem Description

Given \(n\) points on a plane, find the circle with the smallest radius that can cover all points.

Process

Assume circle \(O\) is the minimum enclosing circle for the first \(i-1\) points. When adding the \(i\)-th point, if it lies inside or on the circle, do nothing. Otherwise, the new minimum enclosing circle must pass through the \(i\)-th point.

Then, using the \(i\)-th point as the base (with radius \(0\)), repeat the above process by adding the \(j\)-th point. If the \(j\)-th point lies outside the circle, the minimum enclosing circle must pass through the \(j\)-th point.

Repeat the above steps. (Since at most three points are needed to determine the minimum enclosing circle, repeat three times.)

After traversing all points, the resulting circle is the minimum enclosing circle covering all points.

Properties

Time Complexity: \(O(n)\). For proof, refer to the references.

Space Complexity: \(O(n)\)

Implementation

Code Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

int n;
double r;

struct point {
  double x, y;
} p[100005], o;

double sqr(double x) { return x * x; }

double dis(point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }

bool cmp(double a, double b) { return fabs(a - b) < 1e-8; }

point geto(point a, point b, point c) {
  double a1, a2, b1, b2, c1, c2;
  point ans;
  a1 = 2 * (b.x - a.x), b1 = 2 * (b.y - a.y),
  c1 = sqr(b.x) - sqr(a.x) + sqr(b.y) - sqr(a.y);
  a2 = 2 * (c.x - a.x), b2 = 2 * (c.y - a.y),
  c2 = sqr(c.x) - sqr(a.x) + sqr(c.y) - sqr(a.y);
  if (cmp(a1, 0)) {
    ans.y = c1 / b1;
    ans.x = (c2 - ans.y * b2) / a2;
  } else if (cmp(b1, 0)) {
    ans.x = c1 / a1;
    ans.y = (c2 - ans.x * a2) / b2;
  } else {
    ans.x = (c2 * b1 - c1 * b2) / (a2 * b1 - a1 * b2);
    ans.y = (c2 * a1 - c1 * a2) / (b2 * a1 - b1 * a2);
  }
  return ans;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
  for (int i = 1; i <= n; i++) swap(p[rand() % n + 1], p[rand() % n + 1]);
  o = p[1];
  for (int i = 1; i <= n; i++) {
    if (dis(o, p[i]) < r || cmp(dis(o, p[i]), r)) continue;
    o.x = (p[i].x + p[1].x) / 2;
    o.y = (p[i].y + p[1].y) / 2;
    r = dis(p[i], p[1]) / 2;
    for (int j = 2; j < i; j++) {
      if (dis(o, p[j]) < r || cmp(dis(o, p[j]), r)) continue;
      o.x = (p[i].x + p[j].x) / 2;
      o.y = (p[i].y + p[j].y) / 2;
      r = dis(p[i], p[j]) / 2;
      for (int k = 1; k < j; k++) {
        if (dis(o, p[k]) < r || cmp(dis(o, p[k]), r)) continue;
        o = geto(p[i], p[j], p[k]);
        r = dis(o, p[i]);
      }
    }
  }
  printf("%.10lf\n%.10lf %.10lf", r, o.x, o.y);
  return 0;
}

Practice

Minimum Enclosing Circle

「HNOI2012」Archery

CodeForces 442E

References and Further Reading

Randomized Incremental Algorithm - Xie Yilun

https://www.cnblogs.com/aininot260/p/9635757.html

https://www.cise.ufl.edu/~sitharam/COURSES/CG/kreveldnbhd.pdf

https://blog.csdn.net/u014609452/article/details/62039612

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用