Johna Hershbergera

John E. Hershberger (ur. 1959) to amerykański informatyk i specjalista od oprogramowania, główny inżynier w Mentor Graphics Corporation od 1993 roku. Znany jest ze swoich badań w dziedzinie geometrii obliczeniowej i inżynierii algorytmów .

Biografia

Hershberger odbył studia licencjackie w California Institute of Technology , które ukończył w 1981 roku. Uzyskał stopień doktora. w dziedzinie informatyki na Uniwersytecie Stanforda w 1987 roku pod kierunkiem Leonidasa Guibasa . Był członkiem personelu technicznego w Digital Equipment Corporation Systems Research Center w Palo Alto w Kalifornii do 1993 roku, kiedy dołączył do Mentor Graphics jako inżynier oprogramowania i lider projektu.

Był przewodniczącym komitetu programowego 25th ACM Symposium on Computational Geometry w 2009 roku oraz współprzewodniczącym komitetu programowego Workshop on Algorithm Engineering and Experiments (ALENEX) w 2009 roku.

W 2012 roku został wybrany na członka Association for Computing Machinery „za wkład w obliczenia geometryczne i narzędzia do projektowania układów scalonych”.

Mieszka w Tigard w stanie Oregon .

Składki

Geometria obliczeniowa

John Hershberger wniósł znaczący wkład w geometrię obliczeniową i społeczność algorytmów od połowy lat 80. Jego najwcześniejsze prace koncentrowały się na najkrótszych ścieżkach i widoczności. Wraz z Leonidasem Guibasem i samodzielnie opracował optymalne algorytmy czasu liniowego do obliczania wielokątów widoczności , drzew najkrótszych ścieżek , wykresów widoczności i struktur danych dla zapytań o najkrótszą ścieżkę w czasie logarytmicznym w prostych wielokątach. Wraz z Jackiem Snoeyinkiem rozszerzył algorytmy dla prostych wielokątów, aby obliczyć homotopijne najkrótsze ścieżki wśród wielokątów przeszkody w samolocie . Wynalazł również algorytmy równoległe do rozwiązania kilku problemów związanych z najkrótszą ścieżką i widocznością .

Jednym z najbardziej znaczących osiągnięć tego okresu jest jego algorytm (wspólna praca z Subhashem Suri ) do obliczania najkrótszych ścieżek wśród wielokątnych przeszkód w płaszczyźnie przy użyciu tylko czasu O( n log n ) . Algorytm ten stanowił ogromną poprawę w stosunku do z grubsza kwadratowego czasu działania , który można było osiągnąć metodami opartymi na wykresach widoczności , i rozwiązał problem, który był otwarty i intensywnie badany od lat.

Struktura danych dla „Pedestrian ray shooting”, opracowana przez Johna i Subhasha Suri , odpowiada na zapytania dotyczące strzelania promieniami w prostym wielokącie . Składa się ze specjalnej triangulacji , tak że dowolny odcinek linii wewnątrz wielokąta przecina tylko trójkąty O (log n ); na zapytania dotyczące strzelania promieniami można odpowiedzieć po prostu przechodząc od trójkąta do trójkąta, aż promień zapytania dotrze do granicy wielokąta.

Struktury danych kinetycznych , zaproponowane przez Leonidasa Guibasa , Juliena Bascha i Hershbergera, miały i nadal mają wpływ na geometrię obliczeniową. Pracując samodzielnie iz różnymi współautorami, John opracował struktury danych kinetycznych, aby zachować zasięg ruchomych punktów; połączone elementy ruchomych dysków jednostkowych, prostokątów i hipersześcianów; klastry dla zbiorów ruchomych punktów; oraz struktury danych do wykrywania kolizji między wielokątami w ruchu.

Wybrane publikacje

• Guibas, Leonidas ; Hershberger, John (1989), „Zapytania optymalnej najkrótszej ścieżki w prostym wielokącie”, Journal of Computer and System Sciences , 39 (2): 126–152, doi : 10.1016/0022-0000 (89) 90041-x .
•    Hershberger, Jan; Suri, Subhash (1999), „Optymalny algorytm dla najkrótszych ścieżek euklidesowych w płaszczyźnie” , 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), „Struktury danych dla danych mobilnych”, Journal of Algorithms , 31 (1): 1–28, CiteSeerX 10.1.1.134.6921 , doi : 10.1006/jagm.1998.0988 , S2CID 8013433 .
•   Hershberger, Jan; Maxel, Matt; Suri, Subhash (2007), „Znajdowanie k najkrótszych prostych ścieżek: nowy algorytm i jego implementacja”, ACM Transactions on Algorithms , 3 (4), Artykuł 45, doi : 10.1145/1290672.1290682 , S2CID 10703503 .
• Hershberger, John (2008), „Ulepszone zaokrąglanie przyciągania wrażliwe na dane wyjściowe”, Discrete and Computational Geometry , 39 (1–3): 298–318, doi : 10.1007 / s00454-007-9015-0 .

Linki zewnętrzne

• Johna Hershbergera w Scholar Wiki
• John Hershberger na DBLP Bibliography Server