Publications Available Electronically

"640K ought to be enough for anybody." - Bill Gates (1981)

The following is a sample of my publications. These are copyrighted and can be used for personal purposes only.

"Only one thing is impossible for God: to find any sense in any copyright law on the planet."

Mark Twain

Eva R. Toussaint and Godfried T. Toussaint, "What is a pattern?" Proceedings of Bridges: Mathematics, Music, Art, Architecture, Culture, Gwacheon National Science Museum, Seoul, Korea, August 14-19, 2014, pp. 293-300.

PDF file: What is a Pattern.pdf

Godfried T. Toussaint and Juan F. Beltran, "Subsymmetries predict auditory and visual pattern complexity," Perception, Vol. 42, November 2013, pp. 1095-1100.

PDF file: Subsymmetries Predict Auditory and Visual Pattern Complexity.pdf

Godfried T. Toussaint, Luke Matthews, Malcolm Campbell, and Naor Brown, "Measuring musical rhythm similarity: Transformation versus feature-based methods," Journal of Interdisciplinary Music Studies, Vol. 6, Issue 1, Spring 2012, pp. 23-53.

PDF file: Rhythm Similarity-Transformation-Versus-Features-JIMS.pdf

Godfried T. Toussaint and Constantin Berzan, "Proximity-graph instance-based learning, support vector machines, and high dimensionality: An empirical comparison," Proceedings of the Eighth International Conference on Machine Learning and Data Mining, July 16-19, 2012, Berlin, Germany. P. Perner (Ed.): MLDM 2012, LNAI 7376, pp. 222–236, 2012. Springer-Verlag Berlin Heidelberg.

PDF file: Proximity-Graph Instance-Based Learning.pdf

Godfried T. Toussaint, Malcolm Campbell, and Naor Brown, "Computational models of symbolic rhythm similarity: Correlation with human judgments," Analytical Approaches to World Music Journal, Vol. 1, No. 2, 2011.

PDF file: Nanning-Proceedings-Paper.pdf

Yang Liu and Godfried T. Toussaint, "Mathematical notation, representation, and visualization of musical rhythm: A comparative perspective," Proceedings of the 2010 International Conference on Computer and Computational Intelligence, Nanning, China, December 25-26, 2010, Vol. 1, pp. 28-32.

PDF file: Computational Models of Symbolic Rhythm Similarity.pdf

Godfried T. Toussaint, Malcolm Campbell, and Naor Brown, "Modeling rhythm similarity: Experiments with Afro-Cuban timelines," Second Meeting of the Northeast Music Cognition Group, (NEMCOG), Department of Music, Yale University, New Haven, CT, May 1st, 2010.

PDF file: Rhythm-Similarity-Experiments-abstract.pdf

Zachary Abel, David Charlton, Sebastien Collette, Erik D. Demaine, Martin L. Demaine, Stefan Langerman, Joseph O'Rourke, Val Pinciu, and Godfried Toussaint, "Cauchy's arm lemma on a growing sphere," Los Alamos Eprint Archive, April 7, 2008 at 08:49:47 GM. (Cite as: arXiv:0804.0986v1 [cs.CG]).

arXiv:0804.0986v1

Justin Colannino, Mirela Damian, Ferran Hurtado, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane Souvaine, and Godfried T. Toussaint, "Efficient many-to-many point matching in one dimension," Graphs and Combinatorics", Vol. 23, June 2007, supplement, Computational Geometry and Graph Theory, The Akiyama-Chvatal Festschrift. The original publication is available at www.springerlink.com.

PDF file: akiyama-chvatal-festschrift.pdf

Godfried T. Toussaint, "Interlocking rhythms, duration interval content, cyclotomic sets, and the haxachordal theorem," Fourth International Workshop on Computational Music Theory, Universidad Politecnica de Madrid, Escuela Universitaria de Informatica, July 24-28, 2006 (Abstract only).

PDF file: interlocking-rhythms.pdf

Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nunez, David Rappaport and Godfried Toussaint, "Algorithms for computing geometric measures of melodic similarity," Computer Music Journal, Vol. 30, No. 3, Fall 2006, pp. 67-76. A preliminary extended abstract is available via the following links.

compressed PostScript file melody.cccg.ps.gz
PDF file

Justin Colannino, Mirela Damian, Ferran Hurtado, John Iacono, Henk Meijer, Suneeta Ramaswami and Godfried T. Toussaint, "An O(n log n)-time algorithm for the restriction scaffold assignment problem," Journal of Computational Biology", Vol. 13, No. 4, 2006.

PDF file

Binay Bhattacharya, Kaustav Mukherjee and Godfried T. Toussaint, "Geometric decision rules for instance-based learning algorithms," Proceedings Pattern Recognition and Machine Intelligence: First International Conference, S. K. Pal et al., (Eds.): LNCS 3776, Kolkata, India, December, 20-22, 2005, pp. 60-69.

PDF file

Godfried Toussaint, "The geometry of musical rhythm," Proceedings of the Japan Conference on Discrete and Computational Geometry, (JCDCG 2004), LNCS 3742, Springer-Verlag, Berlin-Heidelberg, 2005, pp. 198-212.

PDF file: geometry-of-rhythm.pdf

Justin Colannino and Godfried T. Toussaint, "A faster algorithm for computing the link distance between two point sets on the real line," School of Computer Science, McGill University, Technical Report SOCS-TR-2005.5, September 2005.

PDF file

Godfried T. Toussaint, "The Euclidean algorithm generates traditional musical rhythms," Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47-56.

PDF file: banff.pdf

Jose-Miguel Diaz-Banez, Giovanna Farigu, Francisco Gomez, David Rappaport, and Godfried Toussaint, "Similaridad y evolucion en la ritmica del flamenco: una uncursion de la matematica computational," La Gaceta de la Real Sociedad de Matematica Espanola, La Columna de Matematica Computacional de Tomas Recio, Vol. 8.2, 2005, pp. 489-509 (in Spanish).

Godfried Toussaint, "Mathematical features for recognizing preference in Sub-Saharan African traditional rhythm timelines," 3rd International Conference on Advances in Pattern Recognition, University of Bath, Bath, United Kingdom, August 22-25, 2005, pp. 18-27.

PDF file: off-beatness.pdf

Justin Colannino and Godfried Toussaint, "Faster algorithms for computing distances between one-dimensional point sets," Proceedings of the XI Encuentros de Geometria Computacional, Editors: Francisco Santos and David Orden, Servicio de Publicaciones de la Universidad de Cantabria, Santander, Spain, June 27-29, 2005, pp. 189-198.

PDF file

Justin Colannino and Godfried Toussaint, "An algorithm for computing the restriction scaffold assignment problem in computational biology," Information Processing Letters, Volume 95, Issue 4, August, 2005, pp. 466-471.

PDF file

Binay Bhattacharya, Kaustav Mukherjee and Godfried T. Toussaint, "Geometric decision rules for high dimensions," Proceedings of the 55th Session of the International Statistics Institute, Sydney, Australia, April 5-12, 2005 (invited paper).

PDF file

Godfried T. Toussaint, "Computational geometric aspects of musical rhythm," Abstracts of the 14th Annual Fall Workshop on Computational Geometry, Massachussetts Institute of Technology, November 19-20, 2004, pp. 47-48.

PDF file

Jose-Miguel Diaz-Banez, Giovanna Farigu, Francisco Gomez, David Rappaport, and Godfried Toussaint, "Analisis filogenetico del compas flamenco," Proceedings of XXXII Congreso Internacional de Arte Flamenco, Mairena del Alcor, Sevilla, Spain, September, 2004 (invited paper in Spanish).

PDF file

Godfried T. Toussaint, "A comparison of rhythmic similarity measures," Proceedings of ISMIR 2004: 5th International Conference on Music Information Retrieval, Universitat Pompeu Fabra, Barcelona, Spain, October 10-14, 2004, pp. 242-245. A longer version appeared in: School of Computer Science, McGill University, Technical Report SOCS-TR-2004.6, August 2004.

PDF file (long version)

Greg Aloupis, Erik Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu and Godfried Toussaint, "Unfolding polyhedral bands," Proceedings of the Sixteeth Canadian Conference on Computational Geometry, (CCCG'04), Concordia University, Montreal, August 9-11, 2004, pp. 60-63.

PDF file band-cccg.pdf

Miguel Diaz-Banez, Giovanna Farigu, Francisco Gomez, David Rappaport, and Godfried T. Toussaint, "El compas flamenco: A phylogenetic analysis," Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Southwestern College, Winfield, Kansas, July 30 to August 1, 2004, pp. 61-70.

PDF file

Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nunez, David Rappaport and Godfried Toussaint, "Computing a geometric measure of the similarity between two melodies," Proceedings of the 15th Canadian Conference on Computational Geometry," Dalhousie University, Halifax, Nova Scotia, Canada, August 11-13, 2003, pp. 81-84.

compressed PostScript file melody.cccg.ps.gz
PDF file

Ferran Hurtado, Godfried T. Toussaint, and Joan Trias, "On polyhedra induced by point sets in space," Proceedings of the 15th Canadian Conference on Computational Geometry," Dalhousie University, Halifax, Nova Scotia, Canada, August 11-13, 2003, pp. 107-110.

compressed PostScript file polyhedronizations.ps.gz
PDF file

David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint, "Output-sensitive algorithms for computing nearest-neighbour decision boundaries," Algorithms and Data Structures, F. Dehne, J.-R. Sack and M. Smid (Eds.), 8th International Workshop, July 30 - August 1, 2003, Ottawa, Ontario, Canada, Springer-Verlag, LNCS 2748, pp. 451-461, 2003.

Discrete and Computational Geometry version (accepted in 2004) PDF file
compressed PostScript file nn.boundary.ps.gz
PDF file

Godfried T. Toussaint, "Classification and phylogenetic analysis of African ternary rhythm timelines," Extended version of paper that appeared in: Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, University of Granada, Granada, Spain July 23-27, 2003, pp. 25-36.

compressed PostScript file ternary.ps.gz
PDF file
Conference proceedings version - PDF file

Godfried T. Toussaint, "Algorithmic, geometric, and combinatorial problems in computational music theory," Extended version of paper that appeared in: Proceedings of X Encuentros de Geometria Computacional, University of Sevilla, Sevilla, Spain June 16-17, 2003, pp. 101-107.

compressed PostScript file sevilla.long.ps.gz
PDF file (long)
Conference proceedings version - PDF file

H. Bronnimann, J. Iacono, J. Katajainen, P. Morin, J. Morrison and G. T. Toussaint, "Space-efficient planar convex hull algorithms," Theoretical Computer Science, in press, 2003.

compressed PostScript file insitu.ps.gz
PDF file

J. Antonio Sellares and Godfried T. Toussaint, "On the role of kinesthetic thinking in computational geometry," Journal of Mathematical Education in Science and Technology, Vol. 34, No. 2, 2003, pp. 219-237.

Compressed PostScript file kinesthetic.thinking.ps
PDF file kinesthetic.thinking.pdf

Elsa Omaña-Pulido and Godfried T. Toussaint, "Aperture-angle optimization problems in 3 dimensions," Journal of Mathematical Modelling and Algorithms, Vol. 1, 2002, pp. 301-329.

compressed PostScript file aperture3D.ps.gz
PDF file aperture3D.pdf

Benjamin Marlin and Godfried Toussaint, "Constructing convex 3-polytopes from two triangulations of a polygon," Proceedings of the 14th Canadian Conference on Computational Geometry , University of Lethbridge, Lethbridge, Alberta, August 12-14, 2002, pp. 36-39.

Compressed PostScript file inflating.polyhedra.ps.gz
PDF file inflating.polyhedra.pdf

Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu and Godfried T. Toussaint, "On flat-state connectivity of chains with fixed acute angles," Proceedings of the 14th Canadian Conference on Computational Geometry , University of Lethbridge, Lethbridge, Alberta, August 12-14, 2002, pp. 27-30.

Compressed PostScript file acute.ps.gz
PDF file acute.pdf

Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars and Godfried T. Toussaint, "Computing signed permutations of polygons," Proceedings of the 14th Canadian Conference on Computational Geometry , University of Lethbridge, Lethbridge, Alberta, August 12-14, 2002, pp. 68-71.

Compressed PostScript file permutations.ps.gz
PDF file permutations.pdf

Godfried T. Toussaint, "Proximity graphs for nearest neighbor decision rules: recent progress," Interface-2002, 34th Symposium on Computing and Statistics (theme: Geoscience and Remote Sensing), Ritz-Carlton Hotel, Montreal, Canada, April 17-20, 2002

compressed PostScript file interface.ps.gz
PDF file interface.pdf

Michael Soss and Godfried 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, Editors, Jorge A. Calvo, Keneth Millett, and Eric Rawdon, published by the American Mathematical Society, Contemporary Mathematics Vol. 304, 2002, pp. 269-285.

compressed PostScript file lasvegas.ps.gz
PDF file lasvegas.pdf

Godfried T. Toussaint, "A mathematical analysis of African, Brazilian, and Cuban clave rhythms," Proceedings of BRIDGES: Mathematical Connections in Art, Music and Science, Townson University, Towson, MD, July 27-29, 2002, pp. 157-168. Also the long version is Technical Report SOCS-02.2, May 2002.

long version clave.pdf
proceedings version PDF file

Godfried T. Toussaint, "Simple proofs of a geometric property of four-bar linkages," American Mathematical Monthly, Vol. 110, No. 6, June-July 2003, pp. 482-494. Also Tech. Report # SOCS-01.4, School of Computer Science, McGill University, April 12, 2001.

compressed PostScript file four-bar.ps.gz
PDF file:(with many applications)
With More detailed proofs here: PDF file

H. Bronnimann, J. Iacono, J. Katajainen, P. Morin, J. Morrison and G. T. Toussaint, "Optimal in-place planar convex hull algorithms," Proceedings of Latin American Theoretical INformatics, LATIN2002, Cancun, Mexico, April 3-6, 2002, pp. 494-507.

compressed PostScript file inplace.ps.gz
PDF file

Oswin Aichholzer, Carmen Cortes, Erik Demaine, Vida Dujmovic, Jeff Erickson, Henk Meijer, Mark Overmars, Belen Palop, Suneeta Ramaswami, and Godfried Toussaint, "Flipturning polygons," Discrete and Computational Geometry, Vol. 28, 2002, pp. 231-253.

Journal version

J. Antoni Sellares and Godfried T. Toussaint, "On the role of kinesthetic thinking in computational geometry," Technical Report IIiA 02-02-RR, Institut d'Informàtica i Aplicacions, Universitat de Girona, Spain, February 19, 2002.

compressed PostScript file thinking2.ps.gz
PDF file thinking2.pdf

Francisco Gomez, Ferran Hurtado, J. A. Sellares and Godfried T. Toussaint, "Nice perspetive projections," Journal of Visual Communication and Image Representation, Vol. 12, No. 4, 2001, pp. 387-400.

compressed PostScript file nice.perspective.ps.gz
PDF file

Greg Aloupis, Stefan Langerman, Michael Soss and Godfried T. Toussaint, "On the computation of the bivariate median and the Fermat-Toricelli problem for lines," Proceedings of the Thirteenth Canadian Conference on Computational Geometry, (extended abstract), University of Waterloo, August 13-15, 2001, pp. 21-24. See also: Tech. Report # SOCS-01.2, School of Computer Science, McGill University, February 28, 2001.

compressed PostScript file fermat.ps.gz
PDF file

Prosenjit Bose, Michael E. Houle and Godfried T. Toussaint, "Every set of disjoint line segments admits a binary tree," Discrete and Computational Geometry, Vol. 26, No. 3, August 2001, pp. 387-410.

compressed PostScript file binary.tree.ps.gz
PDF file

Oswin Aicholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael Soss and Godfried T. Toussaint, "Reconfiguring convex polygons," Computational Geometry: Theory and Applications, Vol. 20, Numbers 1-2, October 2001, pp. 85-95.

compressed PostScript file convex.reconfiguration.ps.gz
PDF file

Greg Aloupis, Carmen Cortes, Francisco Gomez, Michael Soss and Godfried T. Toussaint, "Lower bounds for computing statistical depth," Computational Statistics and Data Analysis, Vol. 40, 2002, pp. 223-229. Also Tech. Report # SOCS-01.1, School of Computer Science, McGill University, February 22, 2001.

compressed PostScript file depth.ps.gz
PDF file

Godfried T. Toussaint, "A new class of stuck unknots in Pol-6," Contributions to Algebra and Geometry, Vol. 42, No. 2, 2001, pp. 301-306. Also: Tech. Report No. SOCS-99.1, School of Computer Science, McGill University, April 10, 1999.

compressed PostScript file unknot.ps.gz
PDF file

Thomas Fevens, Antonio Hernandez, Antonio Mesa, Patrick Morin, Michael Soss and Godfried T. Toussaint, "Simple polygons with an infinite sequence of deflations," Contributions to Algebra and Geometry, Vol. 42, No. 2, 2001, pp. 307-311. Also: manuscript, School of Computer Science, McGill University, June 9, 2000.

compressed PostScript filedeflation.ps.gz
PDF file

Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss and Godfried T. Toussaint, "Convexifying polygons with simple projections," Information Processing Letters, Vol. 80, No. 2, 2001, pp. 81-86. Also Technical Report SOCS-00.4, July 2000.

Compressed PostScript file ipl.ps.gz
PDF file

Francisco Gomez, Ferran Hurtado, Toni Sellares and Godfried Toussaint, "On degeneracies removable by perspective projections," International Journal of Mathematical Algorithms, Vol. 2, 2001, pp. 227-248.

Compressed PostScript file perspective.ps.gz
PDF file

Godfried T. Toussaint, "Advances in computational geometry for document analysis," Proceedings Fourth International Workshop on Document Analysis Systems (DAS'2000), Rio de Janeiro, Brazil, December 10-13, 2000, pp. 25-40.

compressed PostScript filerio.ps.gz
PDF file

Ferran Hurtado, Vera Sacristan and Godfried T. Toussaint, "Some constrained minimax and maximim location problems," Studies in Locational Analysis, Special Issue on Computational Geometry in Locational Analysis, Guest Editor: Juan Mesa, Issue No. 15, December 2000, pp. 17-35.

compressed PostScript filefacility.mesa.ps.gz
PDF file

Prosenjit Bose and Godfried T. Toussaint, "Computing the constrained Euclidean, geodesic and link centers of a simple polygon with applications," Studies in Locational Analysis, Special Issue on Computational Geometry in Locational Analysis, Guest Editor: Juan Mesa, Issue No. 15, December 2000, pp. 37-66.

compressed PostScript filepingate.ps.gz
PDF file

Oswin Aichholzer, Carmen Cortes, Erik Demaine, Vida Dujmovic, Jeff Erickson, Henk Meijer, Mark Overmars, Belen Palop, Suneeta Ramaswami, and Godfried Toussaint, "Flipturning polygons," Proc. of the Japan Conference on Discrete and Computational Geometry (JCDCG 2000), Tokay University, Tokyo, Japan, November 22-25, 2000, pp. 107-108.

Extended Abstract Compressed PostScript
Full Paper Compressed PostScriptflipturn.full.ps.gz
PDF file

Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint and Alain Turki," Experimental results on quadrangulations of sets of fixed points," Computer Aided Geometric Design, accepted for publication April 23, 2002. Also: Techical Report SOCS-00.6, School of Computer Science, McGill University, September 2000.

Compressed PostScript file
PDF file

Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, and Godfried Toussaint, "Reconfiguring convex polygons," Proc. 12th Annual Canadian Conference on Computational Geometry (CCCG 2000), Fredericton, New Brunswick, Canada, August 16-18, 2000, pp. 17-20.

Compressed PostScript file
PDF file

Francisco Gomez, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristan, and Godfried Toussaint, "Implicit convex polygons," Journal of Mathematical Modelling and Algorithms, Vol. 1, 2002, pp. 57-85. Also: Technical Report #SOCS-00.5, School of Computer Science, McGill University, July, 2000.

Compressed PostScript implicit.ps.gz
PDF file

Godfried T. Toussaint, "The complexity of computing nice viewpoints of objects in space," Keynote Address, Vision Geometry IX, Proc. SPIE International Symposium on Optical Science and Technology, 30 July to 4 August 2000, San Diego, California.

compressed PostScript fileviewpoints.ps.gz
PDF file

Michael Soss and Godfried T. Toussaint, "Geometric and computational aspects of polymer reconfiguration," Journal of Mathematical Chemistry, Vol. 27, No. 4, September 2000, pp. 303-318. Also: Technical Report No. SOCS-00.2, School of Computer Science, McGill University, May 4, 2000.

compressed PostScript file
PDF file

Godfried T. Toussaint, "The Erdos-Nagy theorem and its ramifications," Proc. 11th Canadian Conference on Computational Geometry, Vancouver, Canada, August 16-18 1999, pp. 9-12. Long version available at: http://www.cs.ubc.ca/conferences/CCCG. Also: Technical Report No. SOCS-99.2, School of Computer Science, McGill University, June 18, 1999.

compressed PostScript file erdos.ps.gz
PDF file

Godfried T. Toussaint, "Computational polygonal entanglement theory," Proceedings VIII Encuentros de Geometria Computacional, July 7-9, 1999, Castellon, Spain.

compressed PostScript file castellon.ps.gz
PDF file

Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Marc Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint and Sue Whitesides, "Locked and unlocked polygonal chains in 3D, "Proc. Tenth ACM-SIAM Symposium on Discrete Algorithms, (SODA'99), Baltimore, Maryland, USA, January 17-19, 1999. Also Discrete and Computational Geometry, Vol. 26, No. 3, August 2001, pp. 269-281.

2-Page Proceedings version
Full Paper archived by arXiv.org as cs.CG/9910001:locked.archive.ps
PDF version

Francisco Gomez, Suneeta Ramaswami and Godfried T. Toussaint, "On removing non-degeneracy assumptions in computational geometry," Proceedings of the Italian Conference on Algorithms, March 12-14, 1997, Rome, Italy, pp. 52-63. (updated version)

compressed PostScript file nondegeneracy.ps.gz
PDF file

Prosenjit Bose, Marc van Kreveld and Godfried T. Toussaint, "Filling polyhedral molds," Computer Aided Design, Vol. 30, No. 4, 1998, pp. 245-254.

compressed PostScript file casting3D.ps.gz
PDF file

Francisco Gomez, Ferran Hurtado, Toni Sellares and Godfried Toussaint, "Perspective projections and removal of degeneracies," Proc. Tenth Canadian Conference on Computational Geometry, Montreal, Quebec, Canada, August 9-12, 1998.

PostScript file

Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw and Godfried Toussaint, "Hiding disks in folded polygons"Proc. Tenth Canadian Conference on Computational Geometry, Montreal, Quebec, Canada, August 9-12, 1998.

PostScript file

Prosenjit Bose, Ferran Hurtado, Henk Meijer, Suneeta Ramaswami, David Rappaport, Vera Sacristan, Tom Shermer and Godfried Toussaint, "Finding specified sections of arrangements: 2D results," Proc. Tenth Canadian Conference on Computational Geometry, Montreal, Quebec, Canada, August 9-12, 1998.

PostScript file

Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint and Sue Whitesides, "On reconfiguring tree linkages: Trees can lock, "Proc. Tenth Canadian Conference on Computational Geometry, Montreal, Quebec, Canada, August 9-12, 1998.

Proceedings version: PostScript file
Full Paper: locked-tree.ps.gz
Short version: note.ps.gz

Prosenjit Bose, Ferran Hurtado-Diaz, Elsa Omaña-Pulido, Jack Snoeyink and Godfried T. Toussaint, "Some aperture-angle optimization problems," Algorithmica, accepted for publication in June 2001.

compressed PostScript file aperture2D.ps.gz
PDF file aperture2D.pdf

Suneeta Ramaswami, Pedro Ramos and Godfried T. Toussaint, "Converting triangulations to quadrangulations," Computational Geometry: Theory and Applications, Vol. 9, March 1998, pp. 257-276.

compressed PostScript file tri2quad.ps.gz
PDF file tri2quad.pdf

Prosenjit Bose and Godfried T. Toussaint, "Characterizing and efficiently computing quadrangulations of planar point sets," Computer Aided Geometric Design, vol. 14, 1997, pp. 763-785.

compressed PostScript filequad.ps.gz

Boudewijn Asberg, Gregoria Blanco, Prosenjit Bose, Jesus Garcia-Lopez, Mark Overmars, Godfried Toussaint, Gordon Wilfong and Binhai Zhu, "Feasibility of design in stereolithography," Algorithmica, Special Issue on Computational Geometry in Manufacturing, vol. 19, No. 1/2, Sept/Oct, 1997, pp. 61-83.

compressed PostScript filestereo.ps.gz

Prosenjit Bose, Thomas Shermer, Godfried T. Toussaint and Binhai Zhu, "Guarding polyhedral terrains," Computational Geometry: Theory and Applications, vol. 7, No. 3, February 1997, pp. 173-186.

compressed PostScript file terrain.ps.gz
PDF file

Prosenjit Bose and Godfried T. Toussaint, "Computing the constrained Euclidean, geodesic and link centers of a simple polygon with applications," Proceedings of Computer Graphics International (CGI'96), Pohang, Korea, June 24-28, 1996.

compressed PostScript file pingate.ps.gz

Gregoria Blanco, Hazel Everett, Jesus Garcia-Lopez and Godfried T. Toussaint, "Illuminating the free space between quadrilaterals with point light sources," Computer Graphics, Eds., M. Gigante and T. L. Kunii, Proc. Computer Graphics International 1994, Melbourne, Australia, 27 June- 1 July, 1994, World Scientific, 1996.

compressed PostScript file illumination.ps.gz

David Avis, Prosenjit Bose, Thomas Shermer, Jack Snoeyink, Godfried T. Toussaint and Binhai Zhu, "On the sectionsl area of convex polytopes," short version appeared in Proc. 12th ACM Symposium on Computational Geometry, Philadelphia, May 24-26, 1996, pp. C11-C12.

compressed PostScript file section.ps.gz
PDF file

Prosenjit Bose, David Bremner and Godfried T. Toussaint, "All convex polyhedra can be clamped with parallel jaw grippers," Computational Geometry: Theory and Applications, vol. 6, 1996, pp. 291-302.

compressed PostScript file clamp.ps.gz
PDF file

David Eu, Eric Guevremont and Godfried T. Toussaint, "On envelopes of arrangements of lines," Journal of Algorithms, vol. 21, 1996, pp. 111-148.

compressed PostScript file envelope.ps.gz

Prosenjit Bose, Francisco Gomez, Pedro Ramos and Godfried T. Toussaint, "Drawing nice projections of objects in space," Proceedings of Graph Drawing'95, Passau, Germany, September 1995, pp. 52-63. (This is an expanded version of the paper that appeared in the conference proceedings)

compressed PostScript file regular.ps.gz

Godfried T. Toussaint, "Quadrangulations of planar sets," Proceedings of 4th International Workshop on Algorithms and Data Structures (WADS'95), invited paper, August 16-18, 1995, pp. 218-227.

compressed PostScript file quad.wads.ps.gz

Prosenjit Bose and Godfried T. Toussaint, "Geometric and computational aspects of gravity casting," Computer-Aided Design, vol. 27, No. 6, June 1995, pp. 455-464.

compressed PostScript file casting2D.ps.gz

Prosenjit Bose and Godfried T. Toussaint, "Growing a tree from its branches," Journal of Algorithms, vol. 19, 1995, pp. 86-103.

compressed PostScript file growing.tree.ps.gz

Prosenjit Bose and Godfried T. Toussaint, "Computational geometry for CAD/CAM," Proceedings of the Pacific Conference on Computer Graphics and Applications, Beijing, China, August 26-29, 1994, pp. 279-291.

compressed PostScript file beijing-94.ps.gz
PDF file

Godfried T. Toussaint, "A counter-example to a fast algorithm for finding the convex hull of a simple polygon," Computer Aided Drafting, Design and Manufacturing, vol. 4, No. 2, December 1994, pp. 1-4.

compressed PostScript file convex.hull.deng.ps.gz
PDF file convex.hull.deng.pdf

Godfried T. Toussaint, "A counter-example to Tomek's consistency theorem for a condensed nearest neighbor decision rule," Pattern Recognition Letters, vol. 15, August 1994, pp. 797-801.

compressed PostScript file condensed.nn.ps.gz
PDF file condensed.nn.pdf

Chuzo Iwamoto and Godfried T. Toussaint, "Finding Hamiltonian circuits in arrangements of Jordan curves is NP-Complete," Information Processing Letters, vol. 52, 1994, pp. 183-189.

compressed PostScript file jordan.ps.gz
PDF file jordan.pdf

Godfried T. Toussaint, "Computational geometry for document analysis," Third Annual Symposium on Document Analysis and Information Retrieval, Alexis Park Hotel, Las Vegas, Nevada, April 11-13, 1994, pp. 23-42.

compressed PostScript file document.analysis.ps.gz
PDF file document.analysis.pdf

Hossam ElGindy, Hazel Everett and Godfried T. Toussaint, "Slicing an ear in linear time," Pattern Recognition Letters, vol. 14, September 1993, pp. 719-722.

compressed PostScript file ear.ps.gz
PDF file ear.pdf

Godfried T. Toussaint, "A new look at Euclid's second proposition," The Mathematical Intelligencer, vol. 15, No. 3, 1993, pp. 12-23.

compressed PostScript file euclid.ps.gz
PDF file
In Spanish - compressed PostScript fileeuclid.spanish.ps.gz
PDF file

Luc Devroye and Godfried T. Toussaint, "Convex hulls for random lines," Journal of Algorithms, vol. 14, 1993, pp. 381-394.

compressed PostScript filerandom.lines.text.ps.gz
compressed PostScript figsrandom.lines.figs.ps.gz

Godfried T. Toussaint, "What is computational geometry," Proc. IEEE, vol. 80, No. 9, September, 1992, pp. 1347-1363.

compressed PostScript file cg.basics.ps.gz
PDF file cg.basics.pdf

Jerzy W. Jaromczyk and Godfried T. Toussaint, "Relative neighborhood graphs and their relatives," Proc. IEEE, vol. 80, No. 9, September, 1992, pp. 1502-1517.

compressed PostScript file proximity.survey.ps.gz
PDF file proximity.survey.pdf

Binay K. Bhattacharya and Godfried T. Toussaint, "Computing shortest transversals," Computing, vol. 46, 1991, pp. 93-119.

compressed PostScript file shortest.transversals.ps.gz
PDF file shortest.transversals.pdf

Binay K. Bhattacharya Hazel Everett and Godfried T. Toussaint, "A counterexample to a dynamic algorithm for convex hulls of line arrangements," Pattern Recognition Letters, vol. 12, March 1991, pp. 145-147.

compressed PostScript file arrangements.counterexample.ps.gz
PDF file arrangements.counterexample.pdf

Godfried T. Toussaint, "Efficient triangulation of simple polygons," The Visual Computer, vol. 7, 1991, pp. 280-295.

compressed PostScript file triangulation.ps.gz
PDF file triangulation.pdf

Godfried T. Toussaint, "Computing morphological properties of arrangements of lines," Proc. 2nd Japan International Symposium of the Society for the Advancement of Materials and Process Engineering, Chiba, Japan, December 11-14, 1991, pp. 1406-1411.

compressed PostScript file sampe.ps
PDF file sampe.pdf

Godfried T. Toussaint, "Computational geometry and computer vision," in Vision Geometry, Contemporary Mathematics, vol. 119, American Mathematical Society, 1991, pp. 213-224.

compressed PostScript file cg.vision.ps
PDF file cg.vision.pdf

Godfried T. Toussaint, "Anthropomorphic polygons," American Mathematical Monthly, January, 1991, pp. 31-35.

compressed PostScript file mouth.ps
PDF file mouth.pdf

Thomas M. Shermer and Godfried T. Toussaint, "Characterizations of convex and star-shaped polygons," Tech. Report No. SOCS-92.18, December 1992, McGill University.

compressed PostScript file constar.ps.gz
PDF file

David Rappaport, Hiroshi Imai and Godfried T. Toussaint, "Computing simple circuits from a set of line segments," Discrete and Computational Geometry, vol. 5, 1990, pp. 289-304.

compressed PostScript file circuits.ps.gz
PDF file circuits.pdf

Jean-Marc Robert and Godfried T. Toussaint, "Computational geometry and facility location," Proc. International Conf. on Operations Research and Management Science," Manila, The Philippines, Dec. 11-15, 1990, pp. B-1 to B-19.

compressed PostScript file facility.survey.ps.gz
PDF file facility.survey.pdf

Xianshu Kong, Hazel Everett and Godfried T. Toussaint, "The Graham scan triangulates simple polygons," Pattern Recognition Letters, vol. 11, November 1990, pp. 713-716.

compressed PostScript file tri.scan.ps.gz
PDF file tri.scan.pdf

Godfried T. Toussaint, "On separating two simple polygons by a single translation," Discrete and Computational Geometry, vol. 4, 1989, pp. 265-278.

compressed PostScript file separate.simple.ps.gz
PDF file separate.simple.pdf

Godfried T. Toussaint, "Computing geodesic properties inside a simple polygon," Invited Paper, Revue D'Intelligence Artificielle, vol. 3, No. 2, 1989, pp. 9-42.

compressed PostScript file geodesic.ps.gz
PDF file geodesic.pdf

Binay K. Bhattacharya, David G. Kirkpatrick and Godfried T. Toussaint, "Determining sector visibility of a polygon," Proceedings Fifth Annual ACM Symposium on Computational Geometry, Saarbrucken, Germany, June 5-7, 1989, pp. 247-253.

compressed PostScript file secvis.ps.gz
PDF file secvis.pdf

Godfried T. Toussaint, "Some unsolved problems on proximity graphs," First Workshop on Proximity Graphs, Las Cruces, New Mexico, December, 1989.

compressed PostScript file openprox.ps.gz
PDF file openprox.pdf

Michael E. Houle and Godfried T. Toussaint, "Computing the width of a set," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, No. 5, September, 1988, pp. 761-765.

compressed PostScript file width.ps.gz
PDF file width.pdf

Thomas Shermer and Godfried T. Toussaint, "A new characterization of L-convex polygons," in Snapshots of Computational and Discrete Geometry, Ed., G. T. Toussaint, Tech. Report SOCS-88.11, June, 1988, pp. 37-41.

compressed PostScript file L-convex.ps.gz
PDF file L-convex.pdf

Godfried T. Toussaint, "Computational geometry and morphology," Science on Form: Proceedings of the First International Symposium for Science on Form, Editors: S. Ishizaka, Y. Kato, R. Takaki, and J. I. Toriwaki, KTK Scientific Publishers, Tokyo, 1986, pp. 395-403.

PDF file Computational-Geometry-and-Morphology.pdf

Godfried T. Toussaint, "Movable separability of sets," in Computational Geometry, Ed., G. T. Toussaint, North-Holland, 1985, pp. 335-375. This paper is a tutorial survey of research results obtained before 1985 related to disassembly and interlocking puzzles in two and three dimensions. This area is sometimes called local motion planning.

compressed PostScript file separability.survey.ps.gz
PDF file separability.survey.pdf

Godfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons," The Visual Computer, vol. 1, 1985, pp. 118-123.

compressed PostScript file convex.intersection.ps.gz
PDF file convex.intersection.pdf

Mary M. McQueen and Godfried T. Toussaint, "On the ultimate convex hull algorithm in practice," Pattern Recognition Letters, vol. 3, January, 1985, pp. 29-34.

PDF file ultimate.convex.hull.mcqueen.pdf

Godfried T. Toussaint, "On the role of logical, visual and kinesthetic thinking in geometry," a preliminary version of this paper was presented at the Conference on Thinking, Harvard University, August 1984.

compressed PostScript file thinking.ps.gz

Godfried T. Toussaint and Hossam A. ElGindy, "Separation of two monotone polygons in linear time," Robotica, vol. 2, 1984, pp. 215-220.

compressed PostScript file separate.monotone.ps.gz
PDF file separate.monotone.pdf

Godfried T. Toussaint, Binay K. Bhattacharya and Ronald S. Poulsen, "The application of Voronoi diagrams to non-parametric decision rules," Proc. 16th Symposium on Computer Science and Statistics: The Interface, Atlanta, Georgia, March 14-16, 1984, pp. 97-108.

compressed PostScript file nnedit.ps.gz
PDF file nnedit.pdf

Godfried T. Toussaint, "An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons," Computing, vol. 32, 1984, pp. 357-364.

compressed PostScript file minvertexdist.ps.gz
PDF file minvertexdist.pdf

Binay K. Bhattacharya and Godfried T. Toussaint, "Efficient algorithms for computing the maximum distance between two finite planar sets," Journal of Algorithms, vol. 4, 1983, pp. 121-136.

compressed PostScript file maxdist.ps.gz
PDFfile maxdist.pdf

Godfried T. Toussaint, Book Review of "Progress in Pattern Recognition", Eds. L. Kanal and A. Rozenfeld, North-Holland, 1981, in IEEE Transactions on Information Theory, Vol. IT-29, No. 5, September 1983, pp. 779-780.

PDF file kanal.review.pdf

Godfried T. Toussaint, "Solving geometric problems with the rotating calipers," Proceedings of IEEE MELECON'83, Athens, Greece, May 1983, pp. A10.02/1-4.

compressed PostScript file calipers.ps.gz
PDF file calipers.pdf

Godfried T. Toussaint, "The symmetric all-furthest-neighbor problem," Computers and Mathematics with Applications, Vol. 9, No. 6, 1983, pp. 747-754.

PDF file symmetric.all.furthest.neighbor.pdf

Godfried T. Toussaint and Jim A. McAlear, "A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets," Pattern Recognition Letters, vol. 1, October 1982, pp. 21-24.

compressed PostScript file maxdist2.ps.gz
PDF file maxdist2.pdf

Godfried T. Toussaint and Binay K. Bhattacharya, "Optimal algorithms for computing the minimum distance between two finite planar sets," Proc. Fifth International Congress of Cybernetics and Systems, Mexico City, August 1981.

compressed PostScript file mindist.ps.gz
PDF file mindist.pdf

Luc Devroye and Godfried T. Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, vol. 26, 1981, pp. 361-366.

compressed PostScript file chull.ps.gz
PDF file chull.pdf

David Avis and Godfried T. Toussaint, "An optimal algorithm for determining the visibility of a polygon from an edge," IEEE Transactions on Computers, vol. C-30, No. 12, December 1981, pp. 910-914.

compressed PostScript file edge.visibility.ps.gz
PDF file edge.visibility.pdf

David Avis and Godfried T. Toussaint, "An efficient algorithm for decomposing a polygon into star-shaped polygons," Pattern Recognition, vol. 13, No. 6, 1981, pp. 395-398.

compressed PostScript file star.ps.gz
PDF file star.pdf

Godfried T. Toussaint, "The relative neighbourhood graph of a finite planar set," Pattern Recognition, Vol. 12, 1980, pp. 261-268. Winner of an Outstanding Paper Award given by the Pattern Recognition Society.

compressed PostScript file relng.ps.gz
PDF file relng.pdf

Selim G. Akl and Godfried T. Toussaint, "A fast convex hull algorithm," Information Processing Letters, vol. 7, No. 5, 1978, pp. 219-222.

PDF file fast.convex.hull.algorithm.pdf

Godfried T. Toussaint, "The use of context in pattern recognition," Pattern Recognition, Vol. 10, 1978, pp. 189-204. Winner of the Best Paper of the Year Award given by the Pattern Recognition Society.

PDF file context.pdf

Melvin Cohen and Godfried T. Toussaint, "On the detection of structures in noisy pictures," Pattern Recognition, Vol. 9, 1977, pp. 95-98. (line and circle detection with the Hough transform to optimally compensate for random noise)

compressed PostScript file line.detection.ps.gz
PDF file line.detection.pdf

Jack Koplowitz and Godfried T. Toussaint, "A unified theory of coding schemes for the efficient transmission of line drawings," Extended version of: Proceedings of the 1976 IEEE Conference on Communications and Power, Montreal, October 1976, pp. 205-208.

compressed PostScript file line.drawings.ps.gz
PDF file line.drawings.pdf

Godfried T. Toussaint, "Sharper lower bounds for discrimination information in terms of variation," IEEE Transactions on Information Theory, January 1975, pp. 99-100.

PDF file discrimination.information.pdf

Godfried T. Toussaint, "Bibliography on estimation of misclassification," IEEE Transactions on Information Theory, Vol. IT-20, July 1974, pp. 472-479.

PDF file bibliography.pdf

Godfried T. Toussaint, "On the divergence between two distributions and the probability of misclassification of several decision rules," Proceedings Second International Joint Conference on Pattern Recognition, August 13-15, 1974, Copenhagen, Denmark, pp. 27-35.

PDF file (warning: 14 Megs)divergence.pdf
Compressed PostScript file (warning: 15.5 Megs)divergence.ps.gz

Godfried T. Toussaint, "Comments on a modified figure of merit for feature selection in pattern recognition," IEEE Transactions on Information Theory, Vol. IT-17, September 1971, pp. 618-620.

PDF file figureofmerit.pdf

Godfried T. Toussaint, "Note on optimal selection of independent binary-valued features for pattern recognition," IEEE Transactions on Information Theory, Vol. IT-17, September 1971, p. 618.

PDF file best.two.pdf