hirax.net::Keywords::「コネクティングドット」のブログ

■NP困難？な「点を結んでいくと絵が浮かび上がる」新ルールのコネクティング・ドット　

　点を結んでいくと（たとえば数字の順番にしたがって点を純に繋いでいくと）、次第に一枚の絵が浮かび上がってくる…コネクティング・ドットが好きだ。なぜかというと、意味なくばらまかれた点を、ひとつひとつ、今いる点から次の点へとただ辿っているうちに、いつの間にか何かしらのものが描かれていく、というのが人生そのものみたいで面白いからだ。

　そんなコネクティング・ドットで、たとえば明暗の階調（グラデーション）豊かな絵を細かな場所ごとに表現しようとすると、ひとつの問題に行き当たる。それは、濃い部分は密集した線で描かれることとなり、当然のように、そうした部分には（線を繋ぐための）点が密集する。…すると、密度バラバラにばらまかれた点群は、それだけで「何が描かれているか」わかってしまう（下左図）。そして、それどころか、その点群を線で結ぶと、絵はわかりにくく・汚くなってしまうのだ（下右図）。

　そこで、 Bob Bosch and Tom Wexler たちが考え・行った研究が When the Mona Lisa Is NP-Hard（モナリザがNP困難になる時）に紹介されている。彼らは、新たなコネクティング・ドットの「ルール」、「規則正しく配置された点群を、一筆書きしつつ通過しながら、目的の絵に一番似るような全景を描き出すルートで通っていく」というものを考えてみたのだ。たとえば、左下のような規則正しい「格子点」の上を、目的を思い浮かべながら描いていくと、右のような一枚の絵が浮かび上がってくる。

　本当は、意味なくランダムに見える点群を、ただ目の前の次の点へと辿った結果として、一枚の絵が浮かび上がってくる方が（人生に似ていて）好きだ。…けれど、人によっては、自分の目標を心に描きつつ、無味乾燥とした格子点の上に、自分の足で何かを描いていこうとする人もいるかもしれない。そんな人の好みを考えると、こんなコネクティング・ドットも面白いかもしれない、と思う＊。