Godfried Toussaint

Godfried Theodore Patrick Toussaint (1944 to July 2019) was a Canadian computer scientist, professor of computer science, and head of the Computer Science Program at New York University Abu Dhabi. Considered the father of computational geometry in Canada, he researched computational geometry, discrete geometry and their applications, including pattern recognition, motion planning, visualization, knot theory, mechanical linkage reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, and unimodality. He co-founded the Annual ACM Symposium on Computational Geometry and the Canadian Conference on Computational Geometry. With Selim Akl he authored the Akl-Toussaint algorithm for constructing the convex hull of a planar point set, which has expected linear time complexity. In 1980 he introduced the relative neighborhood graph to pattern recognition and machine learning, showing it contains the minimum spanning tree and is a subgraph of the Delaunay triangulation; this and related proximity graphs, including the nearest neighbor graph, the Urquhart graph and the Gabriel graph, are referred to together as the Toussaint hierarchy.