地理的最適化

【ちりてきさいてきか (geographical optimization)】

ボロノイ図という幾何学図形を用いて定式化される施設配置問題とその解法を呼ぶ. ボロノイ図は, $n$ 個の点が与えられたとき, 平面上の点をそのどれに近いかによって分割することでできる図形である. この図は, 与えられた点を施設とみなすと, 自然にその施設の勢力圏を与えており, この性質を用いて種々の施設配置問題が考えられる. このボロノイ図の高速構成算法が計算幾何学の分野で開発され, 実用的な規模の問題が解けるようになった.