Bernard Chazelle
Encyclopedia
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
. Much of his work is in computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, where he has found many of the best-known algorithms, such as linear-time triangulation
Polygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
of a simple polygon
Simple polygon
In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....
, as well as many useful complexity results, such as lower bound techniques based on discrepancy theory
Discrepancy theory
In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be. It is also called theory of irregularities of distribution. This refers to the theme of classical discrepancy theory, namely distributing points in some space such that they are evenly...
. He is also known for his invention of the soft heap
Soft heap
In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time for 5 types of operations. This is achieved by carefully "corrupting" the keys of at most a certain fixed percentage of values in the heap...
data structure and the most asymptotically efficient known algorithm for finding minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
s.
Chazelle originally grew up in Paris, France, where he received his bachelors degree and masters degree in applied mathematics
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
at the Ecole des Mines de Paris in 1977. Then, at the age of 22, he came to Yale University
Yale University
Yale University is a private, Ivy League university located in New Haven, Connecticut, United States. Founded in 1701 in the Colony of Connecticut, the university is the third-oldest institution of higher education in the United States...
in the United States, where he received his Ph.D. in computer science under the supervision of David P. Dobkin
David P. Dobkin
David Paul Dobkin is the Dean of the Faculty and Phillip Y. Goldman '86 Professor of Computer Science at Princeton University.Dobkin was born February 29, 1948, in Pittsburgh, Pennsylvania. After receiving a B.S. from the Massachusetts Institute of Technology in 1970, he moved to Harvard University...
. He went on to claim important research positions at institutions such as Carnegie Mellon
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
, Brown
Brown University
Brown University is a private, Ivy League university located in Providence, Rhode Island, United States. Founded in 1764 prior to American independence from the British Empire as the College in the English Colony of Rhode Island and Providence Plantations early in the reign of King George III ,...
, NEC, Xerox PARC
Xerox PARC
PARC , formerly Xerox PARC, is a research and co-development company in Palo Alto, California, with a distinguished reputation for its contributions to information technology and hardware systems....
, and the Paris institutions Ecole Normale Supérieure
École Normale Supérieure
The École normale supérieure is one of the most prestigious French grandes écoles...
, Ecole Polytechnique
École Polytechnique
The École Polytechnique is a state-run institution of higher education and research in Palaiseau, Essonne, France, near Paris. Polytechnique is renowned for its four year undergraduate/graduate Master's program...
, and INRIA. As of 2004, he has 191 published articles, 93 of which are journal articles, and published two books. He has received 18 grants, 12 of which are from the National Science Foundation
National Science Foundation
The National Science Foundation is a United States government agency that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National Institutes of Health...
. He is a fellow of the ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
, the American Academy of Arts and Sciences
American Academy of Arts and Sciences
The American Academy of Arts and Sciences is an independent policy research center that conducts multidisciplinary studies of complex and emerging problems. The Academy’s elected members are leaders in the academic disciplines, the arts, business, and public affairs.James Bowdoin, John Adams, and...
, the John Simon Guggenheim Memorial Foundation
John Simon Guggenheim Memorial Foundation
The John Simon Guggenheim Memorial Foundation was founded in 1925 by Mr. and Mrs. Simon Guggenheim in memory of their son, who died April 26, 1922...
, and NEC, as well as a member of the European Academy of Sciences
European Academy of Sciences
The European Academy of Sciences has as mission to promote excellence in science and technology and their essential roles in fostering social and economic development and progress. It is registered in and operates under rules and regulations of Belgium. The European Academy of Sciences is an...
.
Chazelle has also written a few polemical essays, such as "Bush's Desolate Imperium" http://www.cs.princeton.edu/~chazelle/politics/bush-article.html and "Anti-Americanism: A Clinical Study" http://www.cs.princeton.edu/~chazelle/politics/antiam.html, which draw from his life experience in both France
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
and the United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
.