アルゴリズム工学データベース
---

幾何アルゴリズム

---



アルゴリズム提供者提供形態必要環境動作確認
2次元幾何
2次元ボロノイ図
一般図形ボロノイ図
杉原 厚吉
(東京大学)
Fortran ソース
webデモ
voronoi
F77
2次元ラゲールボロノイ図 杉原 厚吉
(東京大学)
Fortran ソース F77
3次元幾何
3次元ドロネー図 杉原 厚吉
(東京大学)
Fortran ソース F77
3次元ラゲールドロネー図 杉原 厚吉
(東京大学)
Fortran ソース F77
球面ボロノイ図 杉原 厚吉
(東京大学)
Fortran ソース F77
球面ラゲールボロノイ図 杉原 厚吉
(東京大学)
Fortran ソース F77
3次元凸包 杉原 厚吉
(東京大学)
Fortran ソース
webデモ
ConvexHull3
F77
4次元幾何
4次元凸包 杉原 厚吉
(東京大学)
Fortran ソース F77
逐次添加アルゴリズム
線分集合のボロノイ図 今井 敏行
(和歌山大学)
Fortran ソース
多角形集合のボロノイ図 今井 敏行
(和歌山大学)
Fortran ソース

幾何学アルゴリズム

アルゴリズム提供者提供形態必要環境動作確認
平面走査法の3つの異なった手法(使用言語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:x方向のソーティングの基づく方法
incremt.c:逐次添加法のアルゴリズム
最小包含円アルゴリズム(使用言語C、LEDAのバージョンもある)
mdisc.c:与えられた点をすべて包含する最小の円を求めるランダマイズアルゴリズム
高速行列探索法 (使用言語C)
matrix.c:高速行列探索のプログラム
far.c:高速行列探索を用いて凸多角形の各頂点の最遠点を求めるプログラム
領域分割アルゴリズム (使用言語C)
newseg.c:与えられた画像に含まれる物体を背景からx単調な曲線で分離する方法
格子充填曲線の生成プログラム(n×n の2次元格子の、左上隅からはいり右下隅から抜ける、ランダムなハミルトン経路を生成するアルゴリズムで)

幾何学アルゴリズムのために必要な基本的なデータ構造とアルゴリズム

アルゴリズム提供者提供形態必要環境動作確認
幾何データ処理用のデータ構造 (使用言語C)
btree.c:普通の2分探索木
avl.c:平衡2分探索木(AVL木)
23tree.c:23-木
optree.c:最適2分探索木(各節点の探索確率を考慮して動的計画法で最適化したもの)
segtree.c:セグメントツリー(区分木)
quad.c:四分木
k-d.c:k-d木(2次元版)
pstree.c:プライオリティーサーチツリー
range.c:領域木
探索問題関係(使用言語C)
sel1.c:逐次比較法
sel2.c:mーブロック法(ソート列をm個のブロックに分けて,最初に各ブロックの最大要素と比較して,質問要素を含みうるブロックを限定し,その後でブロック内を逐次探索)
sel3.c:2重mブロック法(ブロック内の探索も同じ方法を再帰的に行うもの)
sel4.c:2分探索法
セレクション問題(使用言語C)
select1.c:ソートしてk番目の要素を選ぶ方法
select2.c:クイックソートの要領でk番目の要素を含みうる区間を絞って行く方法
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デモ
Transversal
地図情報処理関係
グラフのラベル付け 今井桂子
(中央大学)
Cソース C汎用
行数可変のマップラベルアルゴリズム 徳山 豪
(東北大学)

データベース [ 離散最適化 | グラフ | 幾何 | 並列/分散 ]
[ キーワード検索 ] [ リンク集 ] [ 動作確認環境 ]
参加メンバー [ 可視化 | パッケージ製作 | デバッグ術 | 標準入出力 | Makefile | 雛型 ]

土村 展之(tutimura@logopt.com)
<最終更新日 2001年9月3日 16時56分>