直訳すると「直線を掃くアルゴリズム」ですかね。ちょっとsweepの品詞がよくわからない(多分名詞)から訳は勘弁してください。
以下この記事中ではsweep line algorithmを略してSLAと書きます。
どういうアルゴリズムか
このアルゴリズムは「ある平面上(または空間内)で、直線(もしくは平面)を端から端に動かす」アルゴリズムの総称です。
つまりこれ自身はアルゴリズムと呼びません。「〇〇アルゴリズムはSLAだ」こんな感じで、アルゴリズムのグループを指し示すだけです。
具体的にどのアルゴリズムがSLAか
Bentley–Ottmann algorithm や、 Fortune's algorithmなんかがSLAです。他のアルゴリズムはまだ見つけてません。
SLAに名前がついてる理由
英語wiki読むと、どうやら「ユークリッド空間での様々な問題を解く時に役に立つ考え方だから名前がついている」ようです。
英語wikiの上のアニメーションが紛らわしい
あれはあくまでFortune's algorithmであって、SLAのアニメーションではありません。クイックソートのwikiなんかはクイックソートの画像載せてるので余計紛らわしいですよね。
