凸多角形の直径

説明

convex_diameter はキャリパー法を用いて凸多角形の直径を求める．ただし凸多角形の直径とはその最遠頂点対間距離のことである．

キャリパー法は次のようなアルゴリズムである．まず初期値として対心点対 (p,q) をひとつとる．これはたとえば y 座標の最小のものと最大のものを取ればよい．次に (p,q) から (next(p), q) と (p, next(q)) の対心点になるほうに状態を遷移する．どちらが対心点対になるかを判定するために next(p)--p が張るベクトルと next(q)--q が張るベクトルの符号付面積を用いることができる．この操作を元の点対に戻るまで繰り返すことですべての対心点対を走ることができる．直径は対心点が張るので，この走査中に距離を保存しておけば解がもとまる．

このアルゴリズムを用いると，たとえば二次元平面にばら撒かれた点集合から最遠点対（farthest point pair），すなわちすべての点対の中で最も離れているものを効率よく計算することができる．具体的には，まず点集合の凸包を計算し，次にそれの直径を計算する．これによって最悪 O(n log n) で最遠点対が計算できる．最遠点対が凸包上に乗ることから，このアルゴリズムの正当性が証明される．

なお，キャリパーとはノギスとも呼ばれる精密計測器で，このアルゴリズムは凸多角形をキャリパーで測る操作に類似しているため，キャリパー法と呼ばれている．

計算量

• O(n)．

ソースコード

#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
#define diff(P, i) (next(P, i) - curr(P, i))
number convex_diameter(const polygon &pt) {
  const int n = pt.size();
  int is = 0, js = 0;
  for (int i = 1; i < n; ++i) {
    if (imag(pt[i]) > imag(pt[is])) is = i;
    if (imag(pt[i]) < imag(pt[js])) js = i;
  }
  number maxd = norm(pt[is]-pt[js]);

  int i, maxi, j, maxj;
  i = maxi = is;
  j = maxj = js;
  do {
    if (cross(diff(pt,i), diff(pt,j)) >= 0) j = (j+1) % n;
    else i = (i+1) % n;
    if (norm(pt[i]-pt[j]) > maxd) {
      maxd = norm(pt[i]-pt[j]);
      maxi = i; maxj = j;
    }
  } while (i != is || j != js);
  return maxd; /* farthest pair is (maxi, maxj). */
}

Verified

• PKU 2187 (Beauty Contest), 154 ms, 900 kb