L字形描画の列挙

高木 正博  中野 眞一  

誌名
電子情報通信学会論文誌 D   Vol.J87-D1   No.1   pp.1-11
発行日: 2004/01/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: アルゴリズム
キーワード: 
グラフ,  平面グラフ,  描画,  列挙,  リスト,  

本文: PDF(820.1KB)
>>論文を購入


あらまし: 
グラフを,各面がL字形(退化したL字形として長方形を含む)であるように,かつ,辺が交差することなく,平面に描画したものを,グラフのL字形描画と呼ぶ.本論文は,すべての底辺付きL字形描画を,重複も抜けもなく列挙する高速なアルゴリズムを与える.本論文のアルゴリズムは,内面の個数がちょうど n 個である底辺付きL字形描画のすべてを,重複も抜けもなく,描画一つ当り O(1) 時間で生成する.このアルゴリズムが使用する作業用記憶領域はアルゴリズム全体で O(n) である.