計算幾何学の書籍一覧

これは計算幾何学に関する書籍の一覧です。2つの主要なカテゴリーがあり、それらはほとんど重複していません。

• 組み合わせ計算幾何学は、離散的なオブジェクトの集合、または離散的な用語で定義されたオブジェクト（点、線、多角形、多面体など）を扱い、離散的/組み合わせ的な特性を持つアルゴリズムが使用されます。
• 数値計算幾何学は、幾何学モデリングやコンピュータ支援幾何学設計(CAGD) とも呼ばれ、代数表現による曲線と面による現実の物体の形状のモデリングを扱います。

組合せ計算幾何学

一般教科書

• フランコ・P・プレパラタ、マイケル・イアン・シャモス(1985).計算幾何学入門. Springer-Verlag . ISBN 0-387-96131-3. 第1版、第2刷、訂正・増補、1988年：ISBN 3-540-96131-3; ロシア語訳、1989年：ISBN 5-03-001041-6。

  本書は、計算幾何学という新興分​​野の基礎的側面を体系的に網羅した、大学院教科書レベルの包括的なモノグラフとしては初の書籍です。この分野の創始者によって執筆されており、初版では過去10年間の主要な進展をすべて網羅しています。

  包括性という点では、1984年の概説論文Lee, D, T., Preparata, FP: "Computational Geometry - a survey". IEEE Trans. on Computers . Vol. 33, No. 12, pp. 1072–1101 (1984)に次ぐものであった。この論文は2次元の問題に焦点を当てているが、高次元の問題にも触れている。^{[ 1 ] [ 2 ]}

  この本の元々の中心はミシャモスの博士論文だったが、それを本にすることを提案したのはこの分野のもう一人の先駆者であるロナルド・グラハムだった。

  この入門書では、この分野の歴史、基本的なデータ構造、計算と幾何学の理論の必要な概念について説明します。

  以降のセクションでは、幾何学的探索（点の位置、範囲探索）、凸包計算、近接性関連の問題（最近点、ボロノイ図の計算と応用、ユークリッド最小全域木、三角形分割など）、幾何学的交差問題、等長長方形の集合のアルゴリズムについて説明します。

• ハーバート・エデルスブルンナー(1987). 『組合せ幾何学におけるアルゴリズム』シュプリンガー・フェアラーク. ISBN 0-89791-517-8。

  このモノグラフは、計算幾何学における問題とアプローチについて、特に超平面配置の役割に焦点を当てた、かなり高度な解説書である。超平面配置は、この分野の特定の領域において、基本的な組み合わせ幾何学的構造を構成することが示唆されている。主な対象読者は、応用開発者ではなく、この分野で活動する理論研究者である。計算幾何学に関する多くの書籍が2次元および3次元の問題（計算幾何学の応用のほとんどが2次元および3次元の問題である）に焦点を当てているのとは異なり、本書は一般的な多次元設定においてその主題を扱うことを目指している。^{[ 3 ]}

• マーク・デ・バーグ;オトフリード・チョン;マーク・ヴァン・クレベルド;マーク・オーヴァーマーズ(2008)。計算幾何学(第 3 改訂版)。スプリンガー・フェルラーグ。ISBN 978-3-540-77973-5. 第1版（1997年）：ISBN 3-540-61270-X。

  この教科書は、実用的応用の観点から計算幾何学を入門的に解説しています。導入章から始まり、残りの15章ではそれぞれ、実際の応用問題を定式化し、その背後にある幾何学的問題を定式化し、その解決に役立つ計算幾何学の手法を、擬似コードで示されたアルゴリズムを用いて解説しています。本書では主に2次元および3次元幾何学を扱っています。

  この本の目的は、分野の最先端の研究ではなく、方法とアプローチの包括的な入門を提供することです。提示されたアルゴリズムは、計算幾何学の基本的な「構成要素」に基づいた、透明性が高く、合理的に効率的なソリューションを提供します。^{[ 4 ] [ 5 ]}

  この本は、次の章で構成されています (タイトルのトピックとその応用の両方のソリューションを提供します)。「計算幾何学 (入門)」「線分の交差」「多角形の三角形分割」「線形計画法」「直交範囲探索」「点の位置」「ボロノイ図」「配置と双対性」「ドロネー三角形分割」「その他の幾何学的データ構造」「凸包」「バイナリ空間分割」「ロボットの動作計画」「四分木」「可視性グラフ」「単体範囲探索」。

• ジャン＝ダニエル・ボワソナ、マリエット・イヴィネック(1998).アルゴリズム幾何学.ケンブリッジ大学出版局. ISBN 0-521-56529-41995年のフランス語版の翻訳。
• ジョセフ・オルーク（1998年）『C言語による計算幾何学』（第2版）ケンブリッジ大学出版局、ISBN 0-521-64976-5。
• サティアン・デヴァドス、ジョセフ・オルーク(2011). 『離散幾何学と計算幾何学』プリンストン大学出版局. ISBN 978-0-691-14553-2。
• ジム・アーロウ(2014). 『インタラクティブ計算幾何学 - 分類学的アプローチ』マウンテン・ウェイ・リミテッド. ISBN 978-0-9572928-2-6. 第1版。

  この本は、計算幾何学の基本的なアルゴリズムをインタラクティブに紹介したもので、 Mathematicaに基づくソフトウェアを使用して表示できるインタラクティブなドキュメントとしてフォーマットされています。

専門教科書と研究論文

• Selim G. Akl ; Kelly A. Lyons (1993).並列計算幾何学. Prentice-Hall . ISBN 0-13-652017-0。
• Franz Aurenhammer、Rolf Klein、Der-Tsai Lee (2013). Voronoi Diagrams and Delaunay Triangulations . World Scientific.
• Erik D. Demaine、Joseph O'Rourke (2007). 『幾何学的折り畳みアルゴリズム：リンク、折り紙、多面体』 Cambridge University Press. ISBN 978-0-521-85757-4。
• Efi Fogel、Dan Halperin、Ron Wein (2012). CGALアレンジメントとその応用：ステップバイステップガイド. Springer-Verlag . ISBN 978-3-642-17283-0。
• Clara I. Grima & Alberto Márquez (1990). 『曲面上の計算幾何学：円筒、球、トーラス、円錐における計算幾何学の実践』Kluwer Academic Publishers . ISBN 1-4020-0202-5。
• ファジー・リー;ラインハルト・クレット (2011)。ユークリッド最短経路。スプリンガー・フェルラーグ。ISBN 978-1-4471-2255-5。
• Kurt Mehlhorn (1984). 『データ構造と効率的アルゴリズム3：多次元探索と計算幾何学』 Springer -Verlag .
• Kurt Mehlhorn、Stefan Näher (1999). LEDA, 組み合わせ計算と幾何学計算のためのプラットフォーム. Cambridge University Press . ISBN 0-521-56329-1。
• ケタン・マルムリー(1994). 『計算幾何学：ランダム化アルゴリズムによる入門』プレンティス・ホール出版. ISBN 0-13-336363-5。
• ギリ・ナラシムハン、ミヒール・スミッド（2007年）『幾何学的スパナネットワーク』ケンブリッジ大学出版局、ISBN 978-0-521-81513-0。
• 岡部篤之、バリー・ブーツ、杉原厚吉、宋諾邇（2000年）『空間テッセレーション：ボロノイ図の概念と応用』（第2版）John Wiley & Sons.
• ジョセフ・オルーク（1987年）『アートギャラリーの定理とアルゴリズム』オックスフォード大学出版局
• János Pach ; Pankaj K. Agarwal (1995).組合せ幾何学. John Wiley and Sons . ISBN 0-471-58890-3。
• ハナン・サメット（1990）『空間データ構造の設計と分析』アディソン・ウェズリー社、ISBN 978-0-201-50255-8。
• Philip J. Schneider、David H. Eberly (2002).コンピュータグラフィックスのための幾何学的ツール. Morgan Kaufmann .
• ミカ・シャリル、パンカジ・K・アガルワル(1995).ダベンポート・シンツェル数列とその幾何学的応用.ケンブリッジ大学出版局. ISBN 0-521-47025-0。
• ゴーシュ、スビル・クマール（2007年）『平面における可視性アルゴリズム』ケンブリッジ大学出版局、ISBN 978-0-521-87574-5。
• ボワソナ, ジャン＝ダニエル; シャザル, フレデリック;イヴィネック, マリエット(2018).幾何学的推論と位相的推論. ケンブリッジ応用数学テキスト.ケンブリッジ大学出版局.

参考文献

• ジェイコブ・E・グッドマン、ジョセフ・オルーク編 (2004) [1997].離散幾何学と計算幾何学ハンドブック.ノースホランド. ISBN 0-8493-8524-5。初版：、第2版：ISBN 1-58488-301-4。

  本書の構成は、アルゴリズムの古典的なハンドブック『アルゴリズム入門』に類似しており、その包括性は離散幾何学、計算幾何学、計算位相幾何学、そしてそれらの幅広い応用に限定されています。第2版では本書の半分が拡張され、14章が追加され、以前の章は最新のものに更新されました。65章（1,500ページ以上）は、この分野で活躍する大規模な研究者チームによって執筆されています。^{[ 6 ]}

• Jörg-Rudiger Sack ; Jorge Urrutia (1998).計算幾何学ハンドブック. North-Holland . ISBN 0-444-82537-1。初版:、第2版 (2000): 1-584-88301-4。

  このハンドブックには、超平面配置、ボロノイ図、幾何学的および空間的データ構造、ポリゴン分解、ランダム化アルゴリズム、デランダム化、並列計算幾何学 (決定論的およびランダム化)、可視性、アート ギャラリーと照明の問題、最近点問題、リンク距離問題、幾何学的オブジェクトの類似性、ダベンポート-シンツェル シーケンス、幾何学的グラフの全域木とスパナ、幾何学的アルゴリズムの堅牢性と数値的問題、アニメーション、およびグラフ描画などの幾何学的アルゴリズムの古典的および新しい研究の概要に関する章が含まれています。

  さらに、本書では、地理情報システム、幾何学的最短経路、ネットワーク最適化、メッシュ生成などの分野における幾何学アルゴリズムの応用についても概説しています。

• Ding-Zhu Du、Frank Hwang (1995).ユークリッド幾何学におけるコンピューティング. コンピューティングに関する講義ノートシリーズ. 第4巻（第2版）. World Scientific. ISBN 981-02-1876-1。

  「この本は、計算ユークリッド幾何学の分野における最近の発展についての調査と探究的な記事を集めたものです。」^{[ 7 ]} 11の章では、定量的幾何学、計算幾何学の歴史、メッシュ生成、幾何学的証明の自動生成、ランダム化幾何学アルゴリズム、シュタイナー木問題、ボロノイ図とドロネー三角形分割、制約解決、スプライン面、ネットワーク設計、幾何学計算のための数値プリミティブを扱っています。

数値計算幾何学（幾何学モデリング、コンピュータ支援幾何学設計）

モノグラフ

• ID・フォークス、マイケル・J・プラット（1980年）『設計と製造のための計算幾何学（数学とその応用）』プレンティス・ホール出版、ISBN 0-470-27069-1。
• アラン・デイヴィス、フィリップ・サミュエルズ(1996). 『曲線と曲面のための計算幾何学入門』オックスフォード大学出版局. ISBN 0-19-853695-X。
• Jean-Daniel Boissonnat、Monique Teillaud (2006).曲線と曲面のための効果的な計算幾何学(数学と可視化シリーズ 編). Springer Verlag . ISBN 3-540-33258-8。
• ジェラルド・ファリン（1988年）『コンピュータ支援幾何学設計のための曲線と曲面』アカデミック・プレス、ISBN 0-12-249050-9。
• リチャード・H・バーテルズ、ジョン・C・ビーティー、ブライアン・A・バースキー（1987年）『コンピュータグラフィックスと幾何学モデリングにおけるスプライン』モーガン・カウフマン、ISBN 0-934613-27-3。
• クリストフ・M・ホフマン（1989年）『幾何学とソリッドモデリング入門』モーガン・カウフマン社ISBN 1-55860-067-1。この本は絶版です。主な章は以下の通りです。
  • 基本概念
  • 境界表現におけるブール演算
  • 堅牢でエラーのない幾何学的演算
  • 曲線のエッジと面の表現
  • サーフェスの交差
  • グレブナー基底テクニック

他の

• Thomas H. Cormen 、 Charles E. Leiserson、Ronald L. Rivest、Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、1990年。ISBN 0-262-03293-7. — この本には幾何学アルゴリズムに関する章があります。
• フランク・ニールセン著『ビジュアルコンピューティング：グラフィックス、ビジョン、ジオメトリ』チャールズ・リバー・メディア、2005年。ISBN 1-58450-427-7— 本書はグラフィックス、ビジョン、幾何学的コンピューティングを融合させたもので、ゲーム開発とグラフィックスを専門とする上級学部生およびプロフェッショナルを対象としています。一般的なタスクのための簡潔なC++コードも含まれています。
• ジェフリー・ウルマン著『VLSIの計算的側面』Computer Science Press, 1984年, ISBN 0-914894-95-1— 第 9 章「VLSI 設計ツールのアルゴリズム」では、電子設計自動化(設計ルール チェック、回路抽出、配置および配線)に関係するポリゴン操作のアルゴリズムについて説明します。
• DT Lee、Franco P. Preparata、「Computational Geometry - A Survey」、IEEE Trans. Computers、vol 33 no. 12、1984、1072-1101。（Errata: IEEE Tr. C. vol.34、no.6、1985）書籍ではありませんが、この30ページの論文は、354項目の参考文献とともに、1984年の新興分野の概要を包括的にまとめた最初の論文であるため、歴史的に興味深いものです。
• ジョージ・T・ハイネマン、ゲイリー・ポリス、スタンレー・セルコウ (2008). 「第9章 計算幾何学」. 『アルゴリズム入門』 .オライリー・メディア. pp.  251– 298. ISBN 978-0-596-51624-6。— この本には、完全なJava実装を含むコードリポジトリが付属しています

会議

• 計算幾何学に関する年次シンポジウム（SoCG）
• カナダ計算幾何学会議( CCCG )
• 離散幾何学および計算幾何学に関する日本会議 ( JCDCG )

下記の会議は幅広い範囲にわたり、この分野で多くの重要な論文を発表しました。

• ACM-SIAM離散アルゴリズムシンポジウム(SODA)
• 年次ACM コンピューティング理論シンポジウム(STOC)
• IEEEコンピュータサイエンス基礎シンポジウム（FOCS）
• 通信、制御、コンピューティングに関する年次アラートン会議 ( ACCC )

紙のコレクション

• 「組合せ幾何学と計算幾何学」、ジェイコブ・E・グッドマン、ヤノシュ・パッハ、エモ・ウェルツル編（MSRI出版、第52巻）、2005年、ISBN 0-521-84862-8。
  • 幾何学的配置、多面体、パッキング、被覆、離散凸性、幾何学的アルゴリズムとその計算複雑性、幾何学的オブジェクトの組み合わせ複雑性に関する調査および研究記事を含む 32 件の論文。
• 「離散幾何学と計算幾何学の概説：20年後」（「現代数学」シリーズ）、アメリカ数学会、2008年、ISBN 0-8218-4239-0

参照

• 数学における重要な出版物のリスト

参考文献

1. MR 0805539、 MR 1004870  
2. Zbl 0575.68037、 Zbl 0575.68059  
3. エデルスブルンナーの著書の書評（ Zbl 0634.52001） 
4. Zbl 0877.68001 (第 1 版)、 Zbl 0939.68134 (第 2 版)のレビュー  
5. de Berg、van Kreveld、Overmars、Schwarzkopf による本について
6. 『Geombinatoricsにおける計算幾何学ハンドブック』のレビュー。
7. 本の表紙より。

外部リンク

• 計算幾何学のページ