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 Abu Dhabi (, ; ar, أَبُو ظَبْيٍ ' ) is the capital and second-most populous city (after Dubai) of the United Arab Emirates. It is also the capital of the Emirate of Abu Dhabi and the centre of the Abu Dhabi Metropolitan Area. ...

, United Arab Emirates. He is considered to be the father of

computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

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

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

(

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

cluster analysis Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of ...

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

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 In the mathematical field of 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 ...

(

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

polygon triangulation In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is . Triangulations may be v ...

, the

largest empty circle In computational geometry, the largest empty sphere problem is the problem of finding a hypersphere of largest radius in ''d''-dimensional space whose interior does not overlap with any given obstacles. Two dimensions The largest empty circl ...

problem, unimodality (

unimodal function In mathematics, unimodality means possessing a unique mode. More generally, unimodality means there is only a single highest value, somehow defined, of some mathematical object. Unimodal probability distribution In statistics, a unimodal pr ...

), and others. Other interests included

meander (art) __NOTOC__ A meander or meandros ( el, Μαίανδρος) is a decorative border constructed from a continuous line, shaped into a repeated motif. Among some Italians, these patterns are known as "Greek Lines". Such a design also may be called ...

compass and straightedge constructions In geometry, straightedge-and-compass construction – also known as ruler-and-compass construction, Euclidean construction, or classical construction – is the construction of lengths, angles, and other geometric figures using only an ideali ...

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 Music theory is the study of the practices and possibilities of music. ''The Oxford Companion to Music'' describes three interrelated uses of the term "music theory". The first is the "rudiments", that are needed to understand music notation (ke ...

. 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 In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

of a planar point set. This algorithm exhibits a

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

with

expected value In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a l ...

linear in the size of the input. In 1980 he introduced the

relative neighborhood graph In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to ...

(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 nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from ''p'' to ''q'' whenever ''q'' is a nea ...

, the Urquhart graph, and the

Gabriel graph In mathematics and computational geometry, the Gabriel graph of a set S of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph G with vertex set S in which any two distinct po ...

. 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 The University of Tulsa (TU) is a private research university in Tulsa, Oklahoma. It has a historic affiliation with the Presbyterian Church and the campus architectural style is predominantly Collegiate Gothic. The school traces its origin to ...

,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 Vancouver and in Kelowna, British Columbia. Established in 1908, it is British Columbia's oldest university. The university ranks a ...

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, Canada. Founded in 1821 by royal charter granted by King George IV,Frost, Stanley Brice. ''McGill Universit ...

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

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

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

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 Izaak Walton Killam (July 23, 1885 – August 5, 1955) was a Canadian financier. Early life Born in Yarmouth, Nova Scotia, he was the son of William Dudman Killam and Arabella Hunter (Belle) Cann. Business ventures As a young banker with the ...

''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 language, Greek wikt:φυλή, φυλή/wikt:φῦλον, φῦλον [] "tribe, clan, race", and wikt:γενετικός, γενετικός [] "origin, source, birth") is the study of the evolutionary his ...

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

Books and book chapters

* G. T. Toussaint, ''

The Geometry of Musical Rhythm ''The Geometry of Musical Rhythm: What Makes a "Good" Rhythm Good?'' is a book on the mathematics of rhythms and drum beats. It was written by Godfried Toussaint, and published by Chapman & Hall/CRC in 2013 and in an expanded second edition in 20 ...

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