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) in

Abu Dhabi Abu Dhabi is the capital city of the United Arab Emirates. The city is the seat of the Abu Dhabi Central Capital District, the capital city of the Emirate of Abu Dhabi, and the UAE's List of cities in the United Arab Emirates, second-most popu ...

, 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 Pattern recognition is the task of assigning a class to an observation based on patterns extracted from data. While similar, pattern recognition (PR) is not to be confused with pattern machines (PM) which may possess PR capabilities but their p ...

( k-nearest neighbor algorithm,

cluster analysis Cluster analysis or clustering is the data analyzing technique in which task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more Similarity measure, similar (in some specific sense defined by the ...

), motion planning, visualization (computer graphics),

knot theory In topology, knot theory is the study of knot (mathematics), mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot be und ...

( stuck unknot problem),

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

reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, unimodality ( unimodal function), and others. Other interests included

meander (art) __NOTOC__ A meander or meandros () is a decorative border constructed from a continuous line, shaped into a repeated Motif (visual arts), motif. Among some Italians, these patterns are known as "Greek Lines". Such a design may also be called the ...

, compass and straightedge constructions, instance-based learning, music information retrieval, and computational

music theory Music theory is the study of theoretical frameworks for understanding the practices and possibilities of music. ''The Oxford Companion to Music'' describes three interrelated uses of the term "music theory": The first is the "Elements of music, ...

. 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 In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first Moment (mathematics), moment) is a generalization of the weighted average. Informa ...

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 study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...

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

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 university, public research university with campuses near University of British Columbia Vancouver, Vancouver and University of British Columbia Okanagan, Kelowna, in British Columbia, Canada ...

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 faculty in 1972, and became a

professor emeritus ''Emeritus/Emerita'' () is an honorary title granted to someone who retirement, retires from a position of distinction, most commonly an academic faculty position, but is allowed to continue using the previous title, as in "professor emeritus". ...

there in 2007. After retiring from McGill, he became a professor of computer science and head of the computer science department at New York University Abu Dhabi. 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 university, private Ivy League research university in Cambridge, Massachusetts, United States. Founded in 1636 and named for its first benefactor, the History of the Puritans in North America, Puritan clergyma ...

doing research on musical similarity, a branch of music cognition. From 2005 he was also a researcher at the Centre for Interdisciplinary Research in Music Media and Technology in the Schulich School of Music at McGill University. He applied computational geometric and

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

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

in particular. In 2004 he discovered that the

Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is a ...

for computing the

greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...

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

to carry out a research project on the

phylogenetics In biology, phylogenetics () is the study of the evolutionary history of life using observable characteristics of organisms (or genes), which is known as phylogenetic inference. It infers the relationship among organisms based on empirical dat ...

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 Academic staff of McGill University Academic staff of New York University Abu Dhabi