John_Hershberger
「JohnHershberger」
John E. Hershberger（1959年生まれ）は、アメリカのコンピューターサイエンティスト兼ソフトウェアの専門家であり、1993年からMentorGraphicsCorporationの主任エンジニアです。彼は計算ジオメトリとアルゴリズムエンジニアリングの研究で知られています。
コンテンツ
1 バイオグラフィー
2 貢献
2.1 計算幾何学
3 選択された出版物
4 参考文献
5 外部リンク
バイオグラフィー
ハーシュバーガーはカリフォルニア工科大学で学部課程を修了し、1981年に卒業しました。博士号を取得しました。レオニダスギバスの監督の下、1987年にスタンフォード大学でコンピュータサイエンスの博士号を取得。彼は、1993年にソフトウェアエンジニアおよびプロジェクトリーダーとしてメンターグラフィックスに入社するまで、カリフォルニア州パロアルトにあるデジタルイクイップメントコーポレーションシステムリサーチセンターの技術スタッフのメンバーでした。
彼は、2009年に第25回計算幾何学に関するACMシンポジウムのプログラム委員長を務め、2009年にアルゴリズム工学と実験に関するワークショップ（ALENEX）のプログラム委員会の共同議長を務めました。
2012年に、彼は「幾何学的コンピューティングと集積回路の設計ツールへの貢献により」 、 Association forComputingMachineryのフェローに選出されました。
彼はオレゴン州タイガードに住んでいます。
貢献
計算幾何学
John Hershbergerは、1980年代半ば以来、計算幾何学とアルゴリズムコミュニティに大きく貢献してきました。彼の初期の作品は最短経路と可視性に焦点を当てていました。Leonidas Guibasと彼自身で、可視ポリゴン、最短経路ツリー、可視グラフ、および単純なポリゴンでの対数時間最短経路クエリのデータ構造を計算するための最適な線形時間アルゴリズムを考案しました。ジャック・スノーインクとともに、彼は単純なポリゴンのアルゴリズムを拡張して、平面内のポリゴンの障害物間のホモトピー 最短経路を計算しました。彼はまた、いくつかの最短経路と可視性の問題を解決するための並列アルゴリズムを発明しました。
この期間の最も重要な成果の1つは、O（n log n）時間のみを使用して平面内の多角形の障害物間の最短経路を計算する彼のアルゴリズム（ Subhash Suriとの共同作業）です。このアルゴリズムは、可視グラフベースの方法で達成可能なほぼ2次の実行時間を大幅に改善し、長年にわたって熱心に研究されてきた問題を解決しました。
JohnとSubhashSuriによって考案された「Pedestrianrayshooting」のデータ構造は、単純なポリゴンで光線射撃のクエリに答えます。これは、ポリゴン内の線分がO（log n）三角形のみと交差するような特別な三角形分割で構成されています。レイシュート-クエリレイがポリゴンの境界に当たるまで三角形から三角形へと歩くだけで、クエリに答えることができます。
Leonidas Guibas、Julien Basch 、Hershbergerによって提案された速度論的データ構造は、計算幾何学に影響を与え続けてきました。ジョンは、自分自身とさまざまな共著者と協力して、移動するポイントの範囲を維持するための動的データ構造を考案しました。移動単位円板、長方形、および超立方体の連結成分。移動点のセットのクラスター。移動中のポリゴン間の衝突を検出するためのデータ構造。
選択された出版物
ギバス、レオニダス; Hershberger、John（1989）、「単純なポリゴンでの最適な最短経路クエリ」、Journal of Computer and System Sciences、39（2）：126–152、doi：10.1016 / 0022-0000（89）90041-x。
ハーシュバーガー、ジョン; Suri、Subhash（1999）、「平面内のユークリッド最短経路の最適なアルゴリズム」、SIAM Journal on Computing、28（6）：2215–2256、CiteSeerX 10.1.1.47.2037、doi：10.1137 / S0097539795289604、MR 1698954。
バッシュ、ジュリアン; ギバス、レオニダス; Hershberger、John（1999）、「モバイルデータのデータ構造」、Journal of Algorithms、31（1）：1–28、CiteSeerX 10.1.1.134.6921、doi：10.1006 / jagm.1998.0988。
ハーシュバーガー、ジョン; マクセル、マット; Suri、Subhash（2007）、「k個の最短の単純なパスの検索：新しいアルゴリズムとその実装」、ACM Transactions on Algorithms、3（4）、Article 45、doi：10.1145 / 1290672.1290682、S2CID 10703503。
Hershberger、John（2008）、「改良された出力に敏感なスナップ丸め」、Discrete and Computational Geometry、39（1–3）：298–318、doi：10.1007 / s00454-007-9015-0。
参考文献
^ ACMデジタルライブラリからの計算幾何学に関する第25回年次シンポジウムの議事録 ^ siam.orgのALENEX09 ^ ACMフェロー賞の引用、
外部リンク ScholarWikiのJohnHershberger DBLPBibliographyServerのJohnHershberger _
“