Godfried Toussaint
Encyclopedia
Godfried T. Toussaint is a Research Professor of Computer Science at New York University Abu Dhabi (NYUAD) in Abu Dhabi
, United Arab Emirates. He is an expert 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 include meander (art), compass and straightedge constructions, instance-based learning
, music information retrieval
, and computational music theory
.
He has been editor and associate editor of a number of scientific journals. He is a co-founder of the Annual ACM Symposium on Computational Geometry
, and the Annual Canadian Conference on Computational Geometry. He has published more than 360 papers and articles in journals and conference proceedings. He has an Erdős number
of two due to his collaboration with David Avis
and Richard Pollack.
He is 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
to the field of pattern recognition
, and showed that it contained the minimum spanning tree
, and was a subgraph of the Delaunay triangulation
. He has made contributions to many other problems in computational geometry including minimum bounding box algorithms, rotating calipers
, and the Erdős–Nagy theorem.
doing research on musical similarity
, a branch of music cognition
. Since 2005 he has also been a researcher in the Centre for Interdisciplinary Research in Music Media and Technology in the Schulich School of Music
at McGill University
. He applies computational geometric and discrete mathematics
methods to the analysis of symbolically represented music in general, and rhythm
in particular. In 2004 he discovered that the Euclidean algorithm
for computing the greatest common divisor
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
were covered in numerous publications in several languages, and were the focus of two Canadian television programs.
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 Harvard University
to carry out a research project on the phylogenetics
of the musical rhythms of the world.
Abu Dhabi
Abu Dhabi , literally Father of Gazelle, is the capital and the second largest city of the United Arab Emirates in terms of population and the largest of the seven member emirates of the United Arab Emirates. Abu Dhabi lies on a T-shaped island jutting into the Persian Gulf from the central western...
, United Arab Emirates. He is an expert on various aspects of computational geometry
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 are also considered to be part of computational...
, discrete 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 geometric objects, such as points, lines, planes, circles,...
, and their applications: pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
(k-nearest neighbor algorithm
K-nearest neighbor algorithm
In pattern recognition, the k-nearest neighbor algorithm is a method for classifying objects based on closest training examples in the feature space. k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until...
, cluster analysis), motion planning
Motion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
, visualization (computer graphics), knot theory
Knot theory
In topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life in shoelaces and rope, a mathematician's knot differs in that the ends are joined together so that it cannot be undone. In precise mathematical language, a knot is an embedding of a...
(stuck unknot
Stuck unknot
In mathematics, a stuck unknot is a polygonal closed loop that is topologically the unknot but cannot be simplified to a planar polygon by rigid motions of the segments.A related idea is to consider "stuck" polygonal open chains...
problem), linkage (mechanical)
Linkage (mechanical)
A mechanical linkage is an assembly of bodies connected together 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 ideal movement, pure rotation or sliding for...
reconfiguration, the art gallery problem
Art gallery problem
The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards which together can observe the whole gallery...
, polygon triangulation
Polygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
, the largest empty circle problem, unimodality (unimodal function), and others. Other interests include meander (art), compass and straightedge constructions, instance-based learning
Instance-based learning
In machine learning, instance-based learning or 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 been stored in memory...
, music information retrieval
Music information retrieval
Music information retrieval is the interdisciplinary science of retrieving information from music. MIR is a small but growing field of research with many real-world applications...
, and computational music theory
Music theory
Music theory is the study of how music works. It examines the language and notation of music. It seeks to identify patterns and structures in composers' techniques across or within genres, styles, or historical periods...
.
He has been editor and associate editor of a number of scientific journals. He is a co-founder of the Annual ACM Symposium on Computational Geometry
Symposium on Computational Geometry
The Annual Symposium on Computational Geometry is an academic conference in computational geometry. It was founded in 1985, and in most but not all of its years it has been sponsored by the Association for Computing Machinery's SIGACT and SIGGRAPH special interest groups.A 2010 assessment of...
, and the Annual Canadian Conference on Computational Geometry. He has published more than 360 papers and articles in journals and conference proceedings. He has an Erdős number
Erdos number
The Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...
of two due to his collaboration with David Avis
David Avis
David Michael Avis is a Canadian and British computer scientist known for his contributions to geometric computations. Avis is a professor in computational geometry and applied mathematics in the School of Computer Science, McGill University, in Montreal.Avis received his Ph.D. in 1977 from...
and Richard Pollack.
He is an author and namesake of the efficient "Akl-Toussaint algorithm" for the construction of the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of a planar point set. This algorithm exhibits a computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
with expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
linear in the size of the input. In 1980 he introduced the relative neighborhood graph
Relative neighborhood graph
In computational geometry, the relative neighborhood graph 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 both p and q than they are to each other...
to the field of pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
, and showed that it contained the minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
, and was a subgraph of the Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
. He has made contributions to many other problems in computational geometry including minimum bounding box algorithms, rotating calipers
Rotating calipers
In computational geometry, rotating calipers is a method used to construct efficient algorithms for a number of problems.The method was first used by Michael Shamos in 1978 for determining all antipodal pairs of points and vertices on a convex polygon....
, and the Erdős–Nagy theorem.
Mathematical research in music
He recently spent a year in the Music Department at Harvard UniversityHarvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
doing research on musical similarity
Musical similarity
Musical similarity is a certain similarity between two or more musical fragments. If these fragments are from one musical piece a musical similarity implies a repetition of the first occurring fragment. As well, eventually, the similarity does not occur by direct repetition, but by presenting in...
, a branch of music cognition
Music cognition
Music cognition is an interdisciplinary approach to understanding the mental processes that support musical behaviors, including perception, comprehension, memory, attention, and performance...
. Since 2005 he has also been a researcher in the Centre for Interdisciplinary Research in Music Media and Technology in the Schulich School of Music
Schulich School of Music
The Schulich School of Music is one of the constituent faculties of McGill University in Montréal, Canada. The faculty was named after benefactor Seymour Schulich.-History:Music at McGill – The Beginning...
at McGill University
McGill University
Mohammed Fathy is a public research university located in Montreal, Quebec, Canada. The university bears the name of James McGill, a prominent Montreal merchant from Glasgow, Scotland, whose bequest formed the beginning of the university...
. He applies computational geometric and discrete mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
methods to the analysis of symbolically represented music in general, and rhythm
Rhythm
Rhythm may be generally defined as a "movement marked by the regulated succession of strong and weak elements, or of opposite or different conditions." This general meaning of regular recurrence or pattern in time may be applied to a wide variety of cyclical natural phenomena having a periodicity or...
in particular. In 2004 he discovered that the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
for computing the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
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
Flamenco
Flamenco is a genre of music and dance which has its foundation in Andalusian music and dance and in whose evolution Andalusian Gypsies played an important part....
were covered in numerous publications in several languages, and were the focus of two Canadian television programs.
Awards
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 KillamIzaak Walton Killam
Izaak Walton Killam was one of Canada's most eminent financiers.-Early life:Born in Yarmouth, Nova Scotia, Killam rose from paper boy in Yarmouth to become one of Canada's wealthiest individuals.-Business ventures:...
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
University of Newcastle, Australia
The University of Newcastle is an Australian public university that was established in 1965. The University's main and largest campus is located in Callaghan, a suburb of Newcastle in New South Wales...
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
Radcliffe Institute for Advanced Study
The Radcliffe Institute for Advanced Study at Harvard is an educational institution in Cambridge, Massachusetts, and one of the semiautonomous components of Harvard University. It is heir to the name and buildings of Radcliffe College, but unlike that historical institution, its focus is directed...
at Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
to carry out a research project on the phylogenetics
Phylogenetics
In biology, phylogenetics is the study of evolutionary relatedness among groups of organisms , which is discovered through molecular sequencing data and morphological data matrices...
of the musical rhythms of the world.
Books and book chapters
- G. T. Toussaint, Editor, Computational Geometry, North-Holland Publishing Company, Amsterdam, 1985.
- G. T. Toussaint, Editor, Computational Morphology, North-Holland Publishing Company, Amsterdam, 1988.
- I. Khoury, G. Toussaint, A. Ciampi, I. Antoniano, C. Murie, and R. Nadon, “Proximity-Graph-Based Tools for DNA Custering,” Encyclopedia of Data Warehousing and Mining (Second Edition), John Wang, Editor, Vol. IV Pro-Z, August 2008, pp. 1623–1631.
- 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.
- H. A. ElGindy and G. T. Toussaint, “Computing the relative neighbor decomposition of a simple polygon,” in Computational Morphology, G. T. Toussaint, Editor, North-Holland, 1988, pp. 53–70.
- J. R. Sack and G. T. Toussaint, “Guard placement in rectilinear polygons,” in Computational Morphology, G. T. Toussaint, Ed., North-Holland, 1988, pp. 153–176.
- 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.
- B. K. Bhattacharya and G. T. Toussaint, “On geometric algorithms that use the furthest point Voronoi diagram,” in Computational Geometry, G.T. Toussaint, Ed., North-Holland Publishing Co., 1985, pp. 43–61.