Panda Noir

JavaScript の限界を究めるブログです。

Sweep line algorithmとは

直訳すると「直線を掃くアルゴリズム」ですかね。ちょっとsweepの品詞がよくわからない(多分名詞)から訳は勘弁してください。

以下この記事中ではsweep line algorithmを略してSLAと書きます。

どういうアルゴリズム

このアルゴリズムは「ある平面上(または空間内)で、直線(もしくは平面)を端から端に動かす」アルゴリズムの総称です。

つまりこれ自身はアルゴリズムと呼びません。「〇〇アルゴリズムSLAだ」こんな感じで、アルゴリズムのグループを指し示すだけです。

具体的にどのアルゴリズムSLA

Bentley–Ottmann algorithm や、 Fortune's algorithmなんかがSLAです。他のアルゴリズムはまだ見つけてません。

SLAに名前がついてる理由

英語wiki読むと、どうやら「ユークリッド空間での様々な問題を解く時に役に立つ考え方だから名前がついている」ようです。

英語wikiの上のアニメーションが紛らわしい

あれはあくまでFortune's algorithmであって、SLAのアニメーションではありません。クイックソートwikiなんかはクイックソートの画像載せてるので余計紛らわしいですよね。