幾何アルゴリズム
| アルゴリズム | 提供者 | 提供形態 | 必要環境 | 動作確認 |
|---|---|---|---|---|
| ２次元幾何 | ||||
| ２次元ボロノイ図 一般図形ボロノイ図 |
杉原 厚吉 （東京大学） |
Fortran ソース webデモ  |
F77 | |
| ２次元ラゲールボロノイ図 | 杉原 厚吉 （東京大学） |
Fortran ソース | F77 | |
| ３次元幾何 | ||||
| ３次元ドロネー図 | 杉原 厚吉 （東京大学） |
Fortran ソース | F77 | |
| ３次元ラゲールドロネー図 | 杉原 厚吉 （東京大学） |
Fortran ソース | F77 | |
| 球面ボロノイ図 | 杉原 厚吉 （東京大学） |
Fortran ソース | F77 | |
| 球面ラゲールボロノイ図 | 杉原 厚吉 （東京大学） |
Fortran ソース | F77 | |
| ３次元凸包 | 杉原 厚吉 （東京大学） |
Fortran ソース webデモ  |
F77 | |
| ４次元幾何 | ||||
| ４次元凸包 | 杉原 厚吉 （東京大学） |
Fortran ソース | F77 | |
| 逐次添加アルゴリズム | ||||
| 線分集合のボロノイ図 | 今井 敏行 （和歌山大学） |
Fortran ソース | ||
| 多角形集合のボロノイ図 | 今井 敏行 （和歌山大学） |
Fortran ソース | ||
| アルゴリズム | 提供者 | 提供形態 | 必要環境 | 動作確認 |
|---|---|---|---|---|
| 平面走査法の３つの異なった手法(使用言語C、LEDAのバージョンもある） | ||||
| brute.c:与えられた多数の線分間の交差を求める腕力法のプログラム | ||||
| shamos.c:与えられた多数の線分間に交差があるかどうかを判定するShamosのアルゴリズム | ||||
| bentley.c:与えられた多数の線分間の交差をすべて求めるBentleyのアルゴリズム | ||||
| 平面走査法の応用(使用言語C、LEDAのバージョンもある） | ||||
| rdecomp.c:与えられたrectilinear polygonの内部を長方形に分割するプログラム | ||||
| トポロジカルウォークアルゴリズム(使用言語C、LEDAのバージョンもある） | ||||
| walk.c:トポロジカルウォークを用いて半平面の共通部分で重みが極大のものをすべて求めるプログラム | ||||
| 凸包計算の3つの異なったアルゴリズム(使用言語C、LEDAのバージョンもある） | ||||
| d-and-c.c:分割統治法で凸包を求めるアルゴリズム | ||||
| sorthull.c:ｘ方向のソーティングの基づく方法 | ||||
| incremt.c:逐次添加法のアルゴリズム | ||||
| 最小包含円アルゴリズム(使用言語C、LEDAのバージョンもある） | ||||
| mdisc.c:与えられた点をすべて包含する最小の円を求めるランダマイズアルゴリズム | ||||
| 高速行列探索法 (使用言語C） | ||||
| matrix.c:高速行列探索のプログラム | ||||
| far.c:高速行列探索を用いて凸多角形の各頂点の最遠点を求めるプログラム | ||||
| 領域分割アルゴリズム (使用言語C） | ||||
| newseg.c:与えられた画像に含まれる物体を背景からｘ単調な曲線で分離する方法 | ||||
| 格子充填曲線の生成プログラム（n×n の２次元格子の、左上隅からはいり右下隅から抜ける、ランダムなハミルトン経路を生成するアルゴリズムで） | ||||
| アルゴリズム | 提供者 | 提供形態 | 必要環境 | 動作確認 |
|---|---|---|---|---|
| 幾何データ処理用のデータ構造 (使用言語C） | ||||
| btree.c:普通の２分探索木 | ||||
| avl.c:平衡２分探索木（ＡＶＬ木） | ||||
| 23tree.c:２３-木 | ||||
| optree.c:最適２分探索木（各節点の探索確率を考慮して動的計画法で最適化したもの） | ||||
| segtree.c:セグメントツリー（区分木） | ||||
| quad.c:四分木 | ||||
| k-d.c:k-d木（２次元版） | ||||
| pstree.c:プライオリティーサーチツリー | ||||
| range.c:領域木 | ||||
| 探索問題関係(使用言語C） | ||||
| sel1.c:逐次比較法 | ||||
| sel2.c:ｍーブロック法（ソート列をｍ個のブロックに分けて，最初に各ブロックの最大要素と比較して，質問要素を含みうるブロックを限定し，その後でブロック内を逐次探索） | ||||
| sel3.c:２重ｍブロック法（ブロック内の探索も同じ方法を再帰的に行うもの） | ||||
| sel4.c:２分探索法 | ||||
| セレクション問題(使用言語C） | ||||
| select1.c:ソートしてｋ番目の要素を選ぶ方法 | ||||
| select2.c:クイックソートの要領でｋ番目の要素を含みうる区間を絞って行く方法 | ||||
| select3.c:ランダムサンプリングに基づくランダマイズアルゴリズム | ||||
| ソーティング関係(使用言語C, LEDAバージョンあり、入力データの複雑さをコントロールできるプログラムつき．） | ||||
| bubble.c:バブルソート | ||||
| select.c:セレクション法 | ||||
| insert.c:インサーションソート | ||||
| shell.c:シェルソート | ||||
| heap.c:ヒープソート | ||||
| quick.c:クイックソート | ||||
| merge.c:マージソート | ||||
| bucket.c:バケット法 | ||||
| monotone.c:与えられた列を単調列に区切った後，隣接する単調列をマージしていく方法 | ||||
| symsort.c:対称ヒープを用いたソート法 | ||||
| 画像処理 | ||||
| デジタルハーフトーニング | 浅野哲夫 （ 北陸先端科学技術大学院大学） |
Cソース | C汎用 | |
| グラフ描画関係 | ||||
| グラフの簡易エディタ | 中野 眞一 （群馬大学） |
|||
| グラフの平面判定( n^2の簡易版) | 中野眞一 （群馬大学） |
|||
| 平面グラフの三角化 | 中野眞一 （群馬大学） |
|||
| 平面グラフの格子直線描画 | 中野眞一 （群馬大学） |
|||
| 平面グラフの直交描画 | 中野眞一 （群馬大学） |
|||
| 平面グラフの矩形描画 | 中野眞一 （群馬大学） |
|||
| 領域分割関係 | ||||
| 点位置決定問題（スラブ法） | 今井桂子 （中央大学） |
|||
| 最短経路関係 | ||||
| 単調な多角形の三角形分割 一般の多角形の単調な多角形への分割 多角形内の最短路と一点からの可視多角形 |
今井桂子 （中央大学） |
Cソース | C汎用 | |
| DPベースのTSPアルゴリズム | 玉木久夫 （明治大学） |
Javaバイナリ | JDK1.2以上 | JDK1.2.2(Linux) |
| ハイパーグラフの極小横断 | 玉木久夫 （明治大学） |
webデモ |
||
| 地図情報処理関係 | ||||
| グラフのラベル付け | 今井桂子 （中央大学） |
Cソース | C汎用 | |
| 行数可変のマップラベルアルゴリズム | 徳山 豪 （東北大学） |
|||