Godfried Toussaint

Who is Godfried Toussaint?

Godfried T. Toussaint is a Research Professor of Computer Science at New York University Abu Dhabi in Abu Dhabi, United Arab Emirates. He does research on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition, motion planning, visualization, knot theory, linkage reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, unimodality, and others. Other interests include meander, compass and straightedge constructions, instance-based learning, music information retrieval, and computational music theory.

He has been editor and associate editor of a number of scientific journals. He is a co-founder of the Annual ACM Symposium on Computational Geometry, and the Annual Canadian Conference on Computational Geometry. He has published more than 360 papers and articles in journals and conference proceedings. He has an Erdős number of two due to his collaboration with David Avis and Richard Pollack.

Along with Selim Akl, he is an author and namesake of the efficient "Akl-Toussaint algorithm" for the construction of the convex hull of a planar point set. This algorithm exhibits a computational complexity with expected value linear in the size of the input. In 1980 he introduced the relative neighborhood graph to the fields of pattern recognition and machine learning, and showed that it contained the minimum spanning tree, and was a subgraph of the Delaunay triangulation. These graphs are members of the family of proximity graphs. Three other well known proximity graphs are the nearest neighbor graph, the Urquhart graph, and the Gabriel graph. The first is contained in the minimum spanning tree, and the Urquhart graph contains the RNG, and is contained in the Delaunay triangulation. Since all these graphs are nested together they are referred to as the Toussaint hierarchy.