格子L字描画のコンパクトな符号

摘要

長方形を幾つかの長方形とL字形に分割したグラフの描画をL字描画という.これは，長方形を幾つかの長方形に分割したグラフの描画である方形描画を一般化したものである.方形描画やL字描画は，VLSIの設計などに応用がある.各点の座標が全て整数であるような描画を格子描画という.格子方形描画のコンパクトな符号力s知られている.本文は，格子L字描画のコンパクトな符号を設計する.符号の長さはたかだかL + m + f_L + (d-1)·f_L/4 + 2ビットである.ここで，Lは与えられた格子L字描画の辺の長さの総和であり，mは辺の本数であり，dは辺の最大の長さであり，f_LはL字形の個数である.もしf_L=0のとき，L + m + 2ビットの符号となり，格子方形描画の符号をほぼ自然に拡張したものとなっている.