Godfried Toussaint

Godfried Theodore Patrick Toussaint (1944 – July 2019) was a Canadian computer scientist, a professor of computer science, and the head of the Computer Science Program at New York University Abu Dhabi (NYUAD)^[1] in Abu Dhabi, United Arab Emirates. He is considered to be the father of computational geometry in Canada. He did research on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition (k-nearest neighbor algorithm, cluster analysis), motion planning, visualization (computer graphics), knot theory (stuck unknot problem), linkage (mechanical) reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, unimodality (unimodal function), and others. Other interests included meander (art), compass and straightedge constructions, instance-based learning, music information retrieval, and computational music theory.^[2]

He was a co-founder of the Annual ACM Symposium on Computational Geometry, and the annual Canadian Conference on Computational Geometry.

Along with Selim Akl, he was 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.^[3] In 1980 he introduced the relative neighborhood graph (RNG) 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. 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.^[4]