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 New York University Abu Dhabi (NYUAD, ar, جامعة نيويورك أبوظبي) is a degree granting, portal campus of New York University serving as a private, liberal arts college, located in Abu Dhabi, United Arab Emirates. Together with ...

(NYUAD) 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 Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic ge ...

, and their applications:

pattern recognition Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphics ...

(

k-nearest neighbor algorithm In statistics, the ''k''-nearest neighbors algorithm (''k''-NN) is a non-parametric supervised learning method first developed by Evelyn Fix and Joseph Hodges in 1951, and later expanded by Thomas Cover. It is used for classification and reg ...

, cluster analysis),

motion planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is use ...

visualization (computer graphics) Visualization or visualisation (see spelling differences) is any technique for creating images, diagrams, or animations to communicate a message. Visualization through visual imagery has been an effective way to communicate both abstract and ...

, knot theory (

stuck unknot In mathematics, a stuck unknot is a closed polygonal chain that is topologically equal to the unknot but cannot be deformed to a simple polygon by rigid motions of the segments.G. T. Toussaint, "A new class of stuck unknots in Pol-6," ''Contributio ...

problem),

linkage (mechanical) A mechanical linkage is an assembly of systems connected to manage forces and movement. The movement of a body, or link, is studied using geometry so the link is considered to be rigid. The connections between links are modeled as providing i ...

reconfiguration, the

art gallery problem The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem: In the geometric version of the problem, the layout of the art gallery is represented ...

, polygon triangulation, the largest empty circle problem, unimodality ( unimodal function), and others. Other interests included meander (art), compass and straightedge constructions,

instance-based learning In machine learning, instance-based learning (sometimes called memory-based learning) is a family of learning algorithms that, instead of performing explicit generalization, compare new problem instances with instances seen in training, which have b ...

music information retrieval Music information retrieval (MIR) is the interdisciplinary science of retrieving information from music. MIR is a small but growing field of research with many real-world applications. Those involved in MIR may have a background in academic musicol ...

, and computational music theory. 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 Selim G. Akl (Ph.D., McGill University, 1978) is a professor at Queen's University in the Queen's School of Computing, where he leads the Parallel and Unconventional Computation Group. His research interests are primarily in the area of algorithm ...

, 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. In 1980 he introduced the relative neighborhood graph (RNG) to the fields of

and

machine learning Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence. Machine ...

, and showed that it contained the

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

, and was a subgraph of the

Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...

. 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.

Biography

Toussaint was born in 1944 in Belgium. After graduating in 1968 from the University of Tulsa,Biography
McGill university, retrieved 2019-03-27 he went to the

University of British Columbia The University of British Columbia (UBC) is a public research university with campuses near Vancouver and in Kelowna, British Columbia. Established in 1908, it is British Columbia's oldest university. The university ranks among the top thre ...

for graduate study, completing his Ph.D. there in 1972. His dissertation, ''Feature Evaluation Criteria and Contextual Decoding Algorithms in Statistical Pattern Recognition'', was supervised by Robert W. Donaldson. He joined the

McGill University McGill University (french: link=no, Université McGill) is an English-language public research university located in Montreal, Quebec Montreal ( ; officially Montréal, ) is the second-most populous city in Canada and most populous ...

faculty in 1972, and became a

professor emeritus ''Emeritus'' (; female: ''emerita'') is an adjective used to designate a retired chair, professor, pastor, bishop, pope, director, president, prime minister, rabbi, emperor, or other person who has been "permitted to retain as an honorary title ...

there in 2007. After retiring from McGill, he became a professor of computer science and head of the computer science department at

. He died in July 2019 in Tokyo, Japan. He was in Tokyo to present his work on "The Levenshtein distance as a measure of mirror symmetry and homogeneity for binary digital patterns" in a special session titled "Design & Computation in Geovisualization" convened by the International Cartographic Association Commission on Visual Analytics at the 2019 International Cartographic Conference.

Mathematical research in music

He spent a year in the Music Department at

Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of high ...

doing research on

musical similarity The notion of musical similarity is particularly complex because there are numerous dimensions of similarity. If similarity takes place between different fragments from one musical piece, a musical similarity implies a repetition of the first occurr ...

, a branch of

music cognition Music psychology, or the psychology of music, may be regarded as a branch of both psychology and musicology. It aims to explain and understand musical behaviour and experience, including the processes through which music is perceived, created, res ...

. From 2005 he was also a researcher at the Centre for Interdisciplinary Research in Music Media and Technology in the

Schulich School of Music The Schulich School of Music (also known as Schulich) is one of the constituent faculties of McGill University in Montreal, Quebec, Canada. It is located at 555, rue Sherbrooke Ouest (555, Sherbrooke Street West). The faculty was named after benef ...

. He applied computational geometric and discrete mathematics methods to the analysis of symbolically represented music in general, and

rhythm Rhythm (from Greek , ''rhythmos'', "any regular recurring motion, symmetry") generally means a " movement marked by the regulated succession of strong and weak elements, or of opposite or different conditions". This general meaning of regular re ...

in particular. In 2004 he discovered that the Euclidean algorithm for computing the

greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...

of two numbers implicitly generates almost all the most important traditional rhythms of the world. His application of mathematical methods for tracing the roots of Flamenco music were the focus of two Canadian television programs.

Awards

In 2018 he was awarded a ''Lifetime Achievement Award'' by the Canadian Association of Computer Science. In 1978 he was the recipient of the Pattern Recognition Society's ''Best Paper of the Year Award''. In 1985 he was awarded a two-year Izaak Walton Killam ''Senior Research Fellowship'' by the

Canada Council for the Arts The Canada Council for the Arts (french: Conseil des arts du Canada), commonly called the Canada Council, is a Crown corporation established in 1957 as an arts council of the Government of Canada. It acts as the federal government's principal i ...

. In 1988 he received an ''Advanced Systems Institute Fellowship'' from the British Columbia Advanced Systems Institute. In 1995 he was given the ''Vice-Chancellor's Research Best-Practice Fellowship'' by the University of Newcastle in Australia. In 1996 he won the Canadian Image Processing and Pattern Recognition Society's ''Service Award'' for his "outstanding contribution to research and education in Computational Geometry." In May 2001 he was honored with the ''David Thomson Award'' for excellence in graduate supervision and teaching at McGill University. In 2009 he won a ''Radcliffe Fellowship'' from the

Radcliffe Institute for Advanced Study The Radcliffe Institute for Advanced Study at Harvard University—also known as the Harvard Radcliffe Institute—is a part of Harvard University that fosters interdisciplinary research across the humanities, sciences, social sciences, arts, a ...

to carry out a research project on the

phylogenetics In biology, phylogenetics (; from Greek φυλή/ φῦλον [] "tribe, clan, race", and wikt:γενετικός, γενετικός [] "origin, source, birth") is the study of the evolutionary history and relationships among or within groups ...

of the musical rhythms of the world.The Harvard Gazette
/ref>

Books and book chapters

* G. T. Toussaint, '' The Geometry of Musical Rhythm'', Chapman and Hall/CRC, January 2013. * G. T. Toussaint, ''Computational Geometry'', Editor, North-Holland Publishing Company, Amsterdam, 1985. * G. T. Toussaint, ''Computational Morphology'', Editor, North-Holland Publishing Company, Amsterdam, 1988. * E. D. Demaine, B. Gassend, J. O'Rourke, and G. T. Toussaint, "All polygons flip finitely... right?" ''Surveys on Discrete and Computational Geometry: Twenty Years Later'', J. E. Goodman, J. Pach, and R. Pollack, Editors, in Contemporary Mathematics, Vol. 453, 2008, pp. 231–255. *J. O'Rourke and G. T. Toussaint, "Pattern recognition," Chapter 51 in the ''Handbook of Discrete and Computational Geometry'', Eds., J. E. Goodman and J. O'Rourke, Chapman & Hall/CRC, New York, 2004, pp. 1135–1162. * M. Soss and G. T. Toussaint, "Convexifying polygons in 3D: a survey," in ''Physical Knots: Knotting, Linking, and Folding Geometric Objects in R3'', AMS Special Session on Physical Knotting, Linking, and Unknotting, Eds. J. A. Calvo, K. Millett, and E. Rawdon, American Mathematical Society, Contemporary Mathematics Vol. 304, 2002, pp. 269–285. * G. T. Toussaint, "Applications of the Erdős–Nagy theorem to robotics, polymer physics and molecular biology," ''Año Mundial de la Matematica'', Sección de Publicaciones de la Escuela Tecnica Superior de Ingenieros Industriales, Universidad Politecnica de Madrid, 2002, pp. 195–198. *J. O'Rourke and G. T. Toussaint, "Pattern recognition," Chapter 43 in the ''Handbook of Discrete and Computational Geometry'', Eds., J. E. Goodman and J. O'Rourke, CRC Press, New York, 1997, pp. 797–813. * G. T. Toussaint, "Computational geometry and computer vision," in ''Vision Geometry, Contemporary Mathematics'', Volume 119, R. A. Melter, A. Rozenfeld and P. Bhattacharya, Editors, American Mathematical Society, 1991, pp. 213–224. * G. T. Toussaint, "A graph-theoretical primal sketch," in ''Computational Morphology'', G. T. Toussaint, Ed., North-Holland, 1988, pp. 229–260. * G. T. Toussaint, "Movable separability of sets," in ''Computational Geometry'', G.T. Toussaint, Ed., North-Holland Publishing Co., 1985, pp. 335–375.

References

{{DEFAULTSORT:Toussaint, Godfried T. 1944 births 2019 deaths Belgian computer scientists Canadian computer scientists Researchers in geometric algorithms University of Tulsa alumni University of British Columbia alumni McGill University faculty New York University Abu Dhabi faculty