機能メモリは、通常の半導体メモリに簡単な論理機能を付加したもので、
全てのワードに対して与えられたキーワードで部分一致検索、部分書き込みが
可能である。この機能をくりかえし用いることにより多数のワード上で並列に
加算等の簡単な演算が行える。従ってワードをそれぞれ簡単なプロセッサと
考えれば、メモリ内の膨大なデータを並列に処理する超並列計算機と
みなすことができる。
ボロノイ図は空間上に母点の集合Sが与えられたとき、Sの要素pに対してSの
他の点のどの点よりもpに近い空間上の点を求めて得られるものである。
計算機上でボロノイ図の応用では、要素pにより領域を分割した
離散空間のボロノイ図、すなわち離散ボロノイ図を扱うことが多い。
本論文では、機能メモリを用いて離散ボロノイ図を効率よく求めるアルゴリズムを
提案し、さらに求めた離散ボロノイ図の情報をもとに与えられた母点が
つくる凸包の頂点集合を効率よく求める手法を提案する。
離散ボロノイ図は、各離散点においてpのうちもっとも距離の近いものを
求めることで得られるが、この処理は各離散点で並列に行うことができる。
計算時間はシーケンシャルアルゴリズムでは離散点数に比例していた
のに対し、このアルゴリズムでは母点数のみに比例する時間で求めることができる。
離散平面の端の各離散点において、もっとも近い母点の要素を求めたとき、
そこに現れない母点の要素は凸包頂点にはならないという性質がある。
母点集合の凸包頂点を求めるには傾き情報が必要であり、除算が多く行われるが、
離散ボロノイ図が求まっていれば、この性質より凸包頂点にならない
母点の要素は計算から除外することができ、結果全体の計算量が
減らせることがわかった。