ジョン・ハーシュバーガー

ジョン・E・ハーシュバーガー（1959年生まれ）は、アメリカのコンピュータ科学者、ソフトウェア専門家であり、1993年からメンター・グラフィックス・コーポレーションの主席エンジニアを務めています。彼は、計算幾何学とアルゴリズム工学の研究で知られています。

バイオグラフィー

ハーシュバーガーはカリフォルニア工科大学で学士号を取得し、1981年に卒業しました。 1987年にはスタンフォード大学でレオニダス・ギバスの指導の下、コンピュータサイエンスの博士号を取得しました。カリフォルニア州パロアルトにあるディジタル・イクイップメント・コーポレーション・システムズ・リサーチ・センターの技術スタッフに勤務し、1993年にメンター・グラフィックスにソフトウェアエンジニア兼プロジェクトリーダーとして入社しました。

彼は2009年の第25回ACM計算幾何学シンポジウムのプログラム委員長を務め、また2009年のアルゴリズム工学と実験ワークショップ（ALENEX）のプログラム委員会の共同委員長も務めた。^{[ 1 ]}^{[ 2 ]}

2012年に彼は「幾何学計算と集積回路の設計ツールへの貢献」により計算機協会のフェローに選出された。 ^{[ 3 ]}

彼はオレゴン州タイガードに住んでいます。

貢献

計算幾何学

ジョン・ハーシュバーガーは1980年代半ばから計算幾何学とアルゴリズムコミュニティに多大な貢献をしてきました。彼の初期の研究は、最短経路と可視性に焦点を当てていました。レオニダス・ギバスと共同で、また単独で、可視多角形、最短経路木、可視グラフ、そして単純多角形における対数時間最短経路クエリのためのデータ構造を計算するための最適な線形時間アルゴリズムを考案しました。ジャック・スノーインクと共同で、単純多角形用のアルゴリズムを拡張し、平面上の多角形障害物間のホモトピック最短経路を計算しました。また、いくつかの最短経路問題と可視問題を解くための並列アルゴリズムも発明しました。

この時期の最も重要な成果の一つは、平面上の多角形障害物間の最短経路をわずかO( n log n )の時間で計算するアルゴリズム（ Subhash Suriとの共同研究）である。このアルゴリズムは、可視性グラフベースの手法で達成可能なほぼ2乗の実行時間を大幅に改善し、長年にわたり未解決のまま精力的に研究されてきた問題を解決した。

John SuriとSubhash Suriによって考案された「歩行レイシューティング」のデータ構造は、単純なポリゴン内でレイシューティングクエリに応答します。この構造は、ポリゴン内の任意の線分がO(log n )個の三角形とのみ交差するような特殊な三角形分割で構成されています。レイシューティングクエリは、クエリレイがポリゴン境界に当たるまで三角形から三角形へと移動するだけで回答できます。

レオニダス・ギバス、ジュリアン・バッシュ、ハーシュバーガーによって提唱された運動データ構造は、計算幾何学においてこれまで、そして現在もなお影響力を持ち続けています。ジョンは、自身および複数の共著者と共同で、移動点の範囲を維持するための運動データ構造、移動単位円、長方形、超立方体の連結成分、移動点の集合を表すクラスター、そして移動中の多角形間の衝突を検出するためのデータ構造を考案しました。

選定された出版物

ギバス、レオニダス; ハーシュバーガー、ジョン (1989)、「単純多角形における最適最短経路クエリ」、コンピュータとシステム科学ジャーナル、39 (2): 126– 152、doi : 10.1016/0022-0000(89)90041-x。
ハーシュバーガー、ジョン;スリ、スハッシュ(1999)、「平面におけるユークリッド最短経路の最適アルゴリズム」、SIAM Journal on Computing、28 (6): 2215– 2256、CiteSeerX 10.1.1.47.2037、doi : 10.1137/S0097539795289604、MR 1698954。
Basch, Julien; Guibas, Leonidas ; Hershberger, John (1999)「モバイルデータのためのデータ構造」Journal of Algorithms , 31 (1): 1– 28, CiteSeerX 10.1.1.134.6921 , doi : 10.1006/jagm.1998.0988 , S2CID 8013433。
Hershberger, John; Maxel, Matt; Suri, Subhash (2007)、「k最短単純経路の探索：新しいアルゴリズムとその実装」、ACM Transactions on Algorithms、3 (4)、Article 45、doi : 10.1145/1290672.1290682、S2CID 10703503。
ハーシュバーガー、ジョン（2008）、「出力に敏感なスナップ丸めの改良」、離散および計算幾何学、39（1-3）：298-318、doi：10.1007/s00454-007-9015-0。

参考文献

外部リンク

Scholar WikiのJohn Hershberger
DBLP書誌サーバーのジョン・ハーシュバーガー

[1] ACMデジタルライブラリの第25回計算幾何学シンポジウムの議事録

[2] siam.org の ALENEX09

[3] ACMフェロー賞の引用、2013年1月22日閲覧。

[ 1 ]

[ 2 ]

[ 3 ]