Abstract Chapter 51 The Aquarium Keeper’s Problem* (2009)
Jurek Czyzowiczt, Peter Egyed, Hazel Everew, Thomas Sherrnert, Diane Souvainell, Godfried Toussaint, ...
We solve the problem of computing the shortest closed path inside a given polygon which visits every edge at least once (Aquarium Z{eeper’s Tour). For convex polygons, we present a linear-time...
Cauchy's Arm Lemma on a Growing Sphere (2008)
Abel, Zachary, Charlton, David, Collette, Sebastien, Demaine, Erik D., Demaine, Martin L., Langerman, Stefan, ...
We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases....
Efficient Many-To-Many Point Matching in One Dimension (2008)
Justin Colannino, Mirela Damian, Ferran Hurtado, Stefan Langerman, Suneeta Ramaswami, Diane Souvaine, ...
Abstract. Let S and T be two sets of points with total cardinality n. The minimum-cost many-to-many matching problem matches each point in S to at least one point in T and each point in T to at least...
Aloupis, G., and others 1 Algorithms for Computing Geometric Measures of Melodic Similarity (2008)
Greg Aloupis, Thomas Fevens, Antonio Mesa, Yurai Nuñez, Stefan Langerman, Tomomi Matsui, ...
We have all heard numerous melodies, whether they come from commercial jingles, jazz ballads, operatic aria, or any of a variety of different sources. How a human detects similarities in melodies has...
Justin Colannino, Mirela Damian, Ferran Hurtado, John Iacono, Henk Meijer, Suneeta Ramaswami, ...
∗ Partially supported by MCYT-FEDER BFM2003-00368, Gen. Cat 2001SGR00224 and Gen. Cat 2005SGR00692
Justin Colannino, Ferran Hurtado, Henk Meijer, Godfried Toussaint, Mirela Damian, John Iacono, ...
The restriction scaffold assignment problem takes as input two finite point sets S and T (with S containing more points than T) and establishes a correspondence between points in S and points in T,...
Abstract. We consider embedding classes of hexagonal unknots with edges of fixed length. Cantarella and Johnston [3] recently showed that there exist “stuck” hexagonal unknots which cannot be...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
Abstract Space-Efficient Planar Convex Hull Algorithms 1 (2008)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Experimental Results on Quadrangulations of Sets of Fixed Points (2008)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining “nice ” quadrangulations of planar sets of points. For many applications “nice ” means that the quadrilaterals obtained are convex if possible and as...
Experimental Results on Quadrangulations of Sets of Fixed Points (2008)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
Efficient Many-To-Many Point Matching in One Dimension (2008)
Justin Colannino, Mirela Damian, Ferran Hurtado, Stefan Langerman, Henk Meijer, Diane Souvaine, ...
Appears in Graphs and Combinatorics, vol. 23 (2007), supplement, Computational Geometry and Graph Theory. The Akiyama-Chvatal Festschrift. The original publication is available at...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
OUTPUT-SENSITIVE ALGORITHMS FOR COMPUTING NEAREST-NEIGHBOUR DECISION BOUNDARIES ∗ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
ABSTRACT. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment Problem (2008)
Justin Colannino, Mirela Damian, Ferran Hurtado, John Iacono, Henk Meijer, Suneeta Ramaswami, ...
The restriction sca#old assignment problem takes as input two finite point sets S and T (with S containing more points than T ) and establishes a correspondence between points in S and points in T ,...
Geometric Decision Rules for Instance-based Learning Problems (2008)
Binay Bhattacharya, Kaustav Mukherjee, Godfried Toussaint
In the typical nonparametric approach to classification in instance-based learning and data mining, random data (the training set of patterns) are collected and used to design a decision rule...
Geometric Decision Rules for High Dimensions (2008)
Binay Bhattacharya, Godfried Toussaint, Kaustav Mukherjee
In this paper we report on a new approach to the instance-based learning problem.
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
What is Computational Geometry? (2008)
Voronoi Diagrams, Springer-Verlag, 1989. [Ko86] Kostovskii, A., Geometrical Constructions with Compasses Only, Mir Publishers, Moscow, 1986. [Kr92] Kreveld, M. van, New Results on Data Structures in...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R [ B comes from R...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes from...
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
Experimental Results on Quadrangulations of Sets of Points (2007)
Prosenjit Bose, Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining "nice" quadrangulations of planar sets of points. For many applications "nice" means that the quadrilaterals obtained are convex if possible...
Processing Line Drawings (2007)
Godfried Toussai Nt, Godfried Toussaint
This paper introduces the basic ideas behind Freeman coding of curves for the efficient representation and processing of line drawings. Along the way Bertrand's paradox in probability theory is...
On Removing Extrinsic Degeneracies in Computational Geometry (2007)
Francisco Gómez, Suneeta Ramaswami, Godfried Toussaint
Existing methods for removing degeneracies in computational geometry can be classified as either approximation or perturbation methods. These methods give the implementer two rather unsatisfactory...
Prunning Can Solve From Facility Location to Visibility Problems (2007)
Ferran Hurtado, Vera Sacristán, Godfried Toussaint
We present several results concerning minimax facility location, geometric problems with convex polygons defined by intersection of halfplanes, and optimization visibility problems, both in two and...
This chapter introduces the basic ideas behind the computation of skeletons and illustrates them with two popular algorithms: Hilditch's algorithm and Rosenfeld's algorithm. 1. Introduction...
A New Characterization of L-Convex Polygons (2007)
Thomas Shermer, Godfried Toussaint
In 1949 Horn and Valentine [HV] showed that if each pair of points a,b in a simple polygon P could be connected by a polygonal path of length two lying in P (such polygons are termed L-convex...
Polygons are Anthropomorphic (2007)
al [x i-1 ,x i+1 ] that bridges x i lies entirely in P. We say that two ears x i and x j are non-overlapping if int[x i-1 ,x i ,x i+1 ] Ç int[x j-1 ,x j ,x j+1 ] = Æ. The following Two-Ears Theorem...
This chapter introduces the basic ideas behind smoothing images. We begin with regularization of one dimensional functions. For two dimensional images we consider four widely used methods: spatial...
This chapter introduces the basic principles behind the use of moments in various aspects of the pattern recognition problem. 1. Introduction A graduate student named Sigfried in the 1970's was...
Grids, Connectivity And Contour Tracing (2007)
This chapter introduces the three basic types of grids used to represent a digital pattern: triangular, hexagonal and square. The notions of 4-connectedness and 8-connectedness are defined and their...
Sharpening Godfried, Godfried Toussaint
This chapter introduces the basic ideas behind image enhancement. Our goal here is in one sense the opposite of the one we had in smoothing. We are interested in suppressing areas of the picture...
Processing Line Drawings (2007)
This chapter introduces the basic ideas behind Freeman coding of curves for the efficient representation and processing of line drawings. Along the way Bertrand's paradox in probability theory...
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Godfried Toussaint
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle . We wish to rigidly move one chain so that the total area between the two chains is minimized....
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
Guarding Polyhedral Terrains Prosenjit Bose (2007)
Thomas Shermer, Godfried Toussaint, Binhai Zhu
We prove that b n
Drawing Nice Projections of Objects in Space y Prosenjit Bose z (2007)
Pedro Ramos, Godfried Toussaint
Given a polygonal object (simple polygon, geometric graph, wire-frame, skeleton or more generally a set of line segments) in three dimensional Euclidean space, we consider the problem of computing a...
Prosenjit Bose, Godfried Toussaint
Abstract--- In the manufacturing industry, finding a suitable location for the pin gate (the pin gate is the point from which liquid is poured or injected into a mold) is a difficult problem when...
Marc Van Kreveld, Godfried Toussaint
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and ensures a complete fill after termination of the gravity casting process, is an important and...
Geometric and Computational Aspects of Injection (2007)
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after the injection process is an important and difficult problem which...
Ferran Hurtado-diaz, Godfried Toussaint
Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P, the aperture angle of x with respect to Q is defined as the angle subtended by the...
No Quadrangulation is Extremely Odd Prosenjit Bose 1 (2007)
Abstract. Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the...
Marc Van Kreveld, Godfried Toussaint
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and ensures a complete fill after termination of the gravity casting process, is an important and...
No Quadrangulation is Extremely Odd Prosenjit Bose (2007)
Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision...
Boudewijn Asberg, Gregoria Blanco, Jesus Garcia-lopez, Mark Overmars, Godfried Toussaint, Gordon Wilfong, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Every set of disjoint line segments admits a binary tree, Discrete Comput Geom (2007)
Prosenjit Bose, Michael E. Houle, Godfried Toussaint
Given a set of n disjoint line segments in the plane, we show that it is always possible to form a tree with the endpoints of the segments such that each line segment is an edge of the tree, the tree...
Experimental Results on Quadrangulations of Sets of Fixed Points Prosenjit Bose (2007)
Suneeta Ramaswami, Godfried Toussaint, Alain Turki
We consider the problem of obtaining "nice " quadrangulations of planar sets of points. For many applications "nice " means that the quadrilaterals obtained are...
Boudewijn Asberg, Gregoria Blanco, Jesus Garcia-lopez, Mark Overmars, Godfried Toussaint, Gordon Wilfong, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Simple proofs of a geometric property of fourbar linkages (2007)
We consider the relationship between the lengths of the two diagonals in the four-bar planar linkage. For convex and crossing linkages one diagonal increases if, and only if, the other decreases. On...
Greg Aloupis, Michael Soss, Godfried Toussaint
Given a nite set of points S, two measures of the depth of a query point with respect to S are the Simplicial depth of Liu and the Halfspace depth of Tukey (also known as Location depth). We show...
David Avis, Thomas C. Shermer, Jack Snoeyink, Godfried Toussaint, Binhai Zhu
Let K be a convex polytope in R d, let h(x) be the hyperplane consisting of all points with first coordinate equal to x, and let A(x) be the area (or volume, if d? 3) of the section K "...
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexied when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
Greg Aloupis, Michael Soss, Godfried Toussaint
Given a nite set of points S, two measures of the depth of a query point with respect to S are the Simplicial depth of Liu and the Halfspace depth of Tukey (also known as Location depth). We show...
Algorithms for Bivariate Medians and a Fermat-Torricelli Problem (2007)
For Lines, Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint
Given a set S of n points in R 2, the Oja depth of a point ` is the sum of the areas of all triangles formed by ` and two elements of S. A point in R 2 with minimum depth is an Oja median. We show...
Unfolding Polyhedral Bands (2007)
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, ...
A band is de ned as the intersection of the surface of a convex polyhedron with the space between two parallel planes, as long as this space does not contain any vertices of the polyhedron. An...
Constructing Convex 3-Polytopes from Two Triangulations of a Polygon (2007)
Benjamin Marlin, Godfried Toussaint
Guibas conjectured that given a convex polygon P in the xy-plane along with two triangulations of it, T 1 and T 2 that share no diagonals, it is always possible to assign height values to the...
On the Role of Kinesthetic Thinking in Computational Geometry (2007)
J. Antoni Sellares, Godfried Toussaint
Computational geometry is a new (about 30 years) and rapidly growing branch of knowledge in computer science that deals with the analysis and design of algorithms for solving geometric problems....
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2007)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
On the Role of Kinesthetic Thinking in Computational Geometry (2007)
J. Antoni Sellares, Godfried Toussaint
Computational geometry is a new (about 30 years) and rapidly growing branch of knowledge in computer science that deals with the analysis and design of algorithms for solving geometric problems....
In-Place Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
Constructing Convex 3-Polytopes from Two Triangulations of a Polygon (2007)
Benjamin Marlin, Godfried Toussaint
Guibas conjectured that given a convex polygon P in the xy-plane along with two triangulations of it, T 1 and T 2 that share no diagonals, it is always possible to assign height values to the...
Space-Efficient Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Prunning Can Solve From Facility Location to Visibility Problems (2007)
Ferran Hurtado Vera, Godfried Toussaint
We present several results concerning minimax facility location, geometric problems with convex polygons defined by intersection of halfplanes, and optimization visibility problems, both in two and...
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
A proposal for designing an interactive software system for teaching geometry using musical rhythm is described.
An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment (2005)
Colannino, Justin, Damian, Mirela, Hurtado, Ferran, Iacono, John, Meijer, Henk, Ramaswami, Suneeta, ...
The assignment problem takes as input two finite point sets S and T and establishes a correspondence between points in S and points in T, such that each point in S maps to exactly one point in T, and...
A Faster Algorithm for Computing the Link Distance between Two Point Sets on the Real Line (2005)
Justin Colannino, Godfried Toussaint
Let S and T be point sets with |S| # |T | and total cardinality n. A linking between S and T is a matching, L, between the sets where every element of S and T is matched to at least one element of...
The heart of an African rhythm is the timeline, a beat that cyclically repeats thoughout a piece, and is often performed with an iron bell that all performers can hear. Such rhythms can be...
Faster Algorithms for Computing Distances between One-Dimensional Point Sets (2005)
Justin Colannino, Godfried Toussaint
Let S and T be two finite sets of points on the real line with |S| + |T | = n and |S| > |T |. We consider two distance measures between S and T that have applications in music information...
RHYTHMOS: An Interactive System for Exploring Notated Musical Rhythm (2005)
Jakob Teitelbaum And, Jakob Teitelbaum, Godfried Toussaint, Miguel Díaz-bañez, Giovanna Farigu, Francisco Gómez, ...
RHYTHMOS is an interactive software system designed as a tool for the analysis, exploration, and composition of musical notated (symbolic) rhythms. It has a graphical user interface (GUI) that allows...
The Euclidean Algorithm Generates Traditional Musical Rhythms (2005)
Godfried Toussaint School, Godfried Toussaint
The Euclidean algorithm (which comes down to us from Euclid's Elements) computes the greatest common divisor of two given integers. It is shown here that the structure of the Euclidean algorithm...
Justin Colannino, Godfried Toussaint
Let S and T be two finite sets of points on the real line with |S| + |T | = n and |S| > |T |. The restriction scaffold assignment problem in computational biology assigns each point of S to a...
The Euclidean algorithm generates traditional musical rhythms (2005)
The Euclidean algorithm (which comes down to us from Euclid’s Elements) computes the greatest common divisor of two given integers. It is shown here that the structure of the Euclidean algorithm...
A Comparison of Rhythmic Dissimilarity Measures (2005)
Abstract. Measuring the dissimilarity between musical rhythms is a fundamental problem with many applications ranging from music information retrieval and copyright infringement resolution to...
Algorithms for Computing Geometric Measures of Melodic Similarity ∗ (2004)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, ...
Consider two orthogonal closed chains on a cylinder. These chains are monotone with respect to the tangential Θ direction. We wish to rigidly move one chain so that the total area between the two is...
Computational Geometric Aspects of Musical Rhythm (2004)
e points are the vertices of a regular n-gon. One may also examine the spectrum of the frequencies with which all the durations are present in a rhythm. In music theory this spectrum is called the...
A Comparison of Rhythmic Similarity (2004)
Measures Godfried Toussaint, Godfried Toussaint
Measuring the similarity between rhythms is a fundamental problem in computational music theory, with many applications such as music information retrieval and copyright infringement resolution. A...
The Geometry of Musical Rhythm (2004)
Musical rhythm is considered from the point of view of geometry.
Computing a geometric measure of the similarity between two melodies (2003)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, ...
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle Θ. We wish to rigidly move one chain so that the total area between the two chains is...
More Classes of Stuck Unknotted Hexagons (2003)
Greg Aloupis, Günter Ewald, Godfried Toussaint
Consider a hexagonal unknot with edges of xed length, for which we allow universal joint motions but do not allow edge crossings. We consider the maximum number of embedding classes that any such...
Computing a Geometric Measure of the Similarity between two Melodies (2003)
Greg Aloupis, Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nunez, ...
Consider two orthogonal closed chains on a cylinder. The chains are monotone with respect to the angle . We wish to rigidly move one chain so that the total area between the two chains is minimized....
Classification and Phylogenetic Analysis of African Ternary Rhythm Timelines (2003)
A combinatorial classi cation and a phylogenetic analysis of the ten 12/8 time, seven-stroke bell rhythm timelines in African and Afro-American music are presented. New methods for rhythm classi...
On flat-state connectivity of chains with fixed acute angles (2002)
Greg Aloupis, Erik D. Demaine, Henk Meijer, Ileana Streinu, Godfried Toussaint
We prove that two classes of fixed-angle, open chains with acute angles are “flat-state connected. ” A chain is flatstate connected if it can be reconfigured between any two of its planar...
Space-efficient planar convex hull algorithms (2002)
Herve Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Proximity Graphs for Nearest Neighbor Decision Rules: Recent Progress (2002)
In the typical nonparametric approach to pattern classification, random data (the training set of patterns) are collected and used to design a decision rule (classifier). One of the most well known...
On flat-state connectivity of chains with fixed acute angles (2002)
Greg Aloupis, Erik D. Demaine, Henk Meijer, Ileana Streinu, Godfried Toussaint
We prove that two classes of fixed-angle, open chains with acute angles are “flat-state connected. ” A chain is flatstate connected if it can be reconfigured between any two of its planar...
Optimal in-place planar convex hull algorithms (2002)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Godfried Toussaint
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
On Flat-State Connectivity of Chains with Fixed Acute Angles (2002)
Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana Streinu, Godfried Toussaint
We prove that two classes of fixed-angle, open chains with acute angles are "flat-state connected." A chain is flatstate connected if it can be reconfigured between any two of its planar...
A mathematical analysis of African, Brazilian, and Cuban clave rhythms (2002)
The resulting pattern rings out a seductive rhythm which in a short span of fifty years during the last half of the 20th century has managed to conquer the planet. It is known
Algorithms for Bivariate Medians and a Fermat-Torricelli Problem for Lines (2002)
Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint
Given a set S of n points in R , the Oja depth of a point is the sum of the areas of all triangles formed by and two elements of S. A point in R with minimum depth is an Oja median. We show how an...
On the computation of the bivariate median and a Fermat-Torricelli problem (2001)
Greg Aloupis, Stefan Langerman, Michael Soss, Godfried Toussaint
Given a set S of n points in R 2, the Oja depth of a point ` is the sum of the areas of all triangles formed by ` and two elements of S. A point in R 2 with minimum depth is an Oja median. We show...
On the computation of the bivariate median and a Fermat-Torricelli problem (2001)
Greg Aloupis, Michael Soss, Godfried Toussaint
Two denitions for the median of a set of points S in R 2 are the simplicial median and the Oja median. Both may be used as robust estimators of location. The fastest algorithms to date for computing...
On the computation of the bivariate median and a Fermat-Torricelli problem (2001)
Greg Aloupis, Michael Soss, Godfried Toussaint
Two denitions for the median of a set of points S in R 2 are the simplicial median and the Oja median. Both may be used as robust estimators of location. The fastest algorithms to date for computing...
Lower Bounds for Computing Statistical Depth (2001)
Greg Aloupis, Carmen Cortes, Francisco Gomez, Michael Soss, Godfried Toussaint
Given a finite set of points S, two measures of the depth of a query point ` with respect to S are the Simplicial depth of Liu and the Halfspace depth of Tukey (also known as Location depth). We show...
Constrained facility location (2000)
Ferran Hurtado, Godfried Toussaint
In a classical facility location problem we are given a set of n points C in the plane representing n customers, plants to be serviced, schools, markets, distribution
Convexifying Polygons with Simple Projections (2000)
Jorge Alberto Calvo, Danny Krizanc, Pat Morin, Michael Soss, Godfried Toussaint
It is known that not all polygons in 3D can be convexified when crossing edges are not permitted during any motion. In this paper we prove that if a 3D polygon admits a non-crossing orthogonal...
Implicit Convex Polygons (2000)
Francisco Gomez, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán, Godfried Toussaint
Convex polygons in the plane can be de ned explicitly as an ordered list of vertices, or given implicitly, for example by a list of linear constraints. The latter representation has been considered...
On Reconfiguring Tree Linkages: Trees can Lock (2000)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, ...
It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. In this paper we propose a related question: whether a...
Implicit Convex Polygons (2000)
Francisco Gómez, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán, Godfried Toussaint
this paper we study the case, that appears to be very natural, in which the polygons are given by a set of linear restrictions, i.e. by a possibly redundant intersection of halfplanes. There is not...
Constrained Facility Location (2000)
Ferran Hurtado, Vera Sacristán, Godfried Toussaint
In this paper we consider constrained versions of the minimax facility location problem. We provide an O(n +m) time algorithm for the problem of constructing the minimum enclosing circle of a set of...
Some constrained minimax and maximin location problems (2000)
Ferran Hurtado, Vera Sacristan, Departament Matematica, Aplicada Ii, Godfried Toussaint
In this paper we consider constrained versions of the Euclidean minimax facility location problem. We provide an O(n+m) time algorithm for the problem of constructing the minimum enclosing circle of...
On Reconfiguring Tree Linkages: Trees can Lock (1999)
Biedl, Therese, Demaine, Erik, Demaine, Martin, Lazard, Sylvain, Lubiw, Anna, O'Rourke, Joseph, ...
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex....
The Erdös-Nagy Theorem and its Ramifications (1999)
Given a simple polygon in the plane, a flip is defined as follows: consider the convex hull of the polygon. If there are no pockets do not perform a flip. If there are pockets then reflect one pocket...
Computational Polygonal Entanglement Theory (1999)
In this paper we are concerned with motions for untangling polygonal linkages (chains, polygons and trees) in 2 and 3 dimensions. We say that an open, simple polygonal chain can be straightened if it...
A New Class of Stuck Unknots in Pol_6 (1999)
We consider embedding classes of hexagonal unknots with edges of fixed length. Cantarella and Johnston [3] recently showed that there exist "stuck" hexagonal unknots which cannot be...
Perspective Projections and Removal of Degeneracies (1998)
Francisco Gomez, Ferran Hurtado, Toni Sellares, Godfried Toussaint
In this paper we consider the following problems: (1) computing projections with distinct x-coordinates, (2) computing non-collinear projections, (3) computing noncocircular projections, and (4)...
On Reconfiguring Tree Linkages: Trees can Lock (1998)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. This problem been raised independently by several...
Prosenjit Bose, Francisco Gómez, Pedro Ramos, Godfried Toussaint
Given a polygonal object (simple polygon, geometric graph, wire-frame, skeleton or more generally a set of line segments) in three-dimensional Euclidean space, we consider the problem of computing a...
Characterizing and efficiently computing quadrangulations of planar point sets (1997)
Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision...
On Removing Non-degeneracy Assumptions in Computational Geometry (Extended Abstract) (1997)
Francisco Gómez, Suneeta Ramaswami, Godfried Toussaint
) Francisco G'omez 1 , Suneeta Ramaswami 2 and Godfried Toussaint 2 1 Dept. of Applied Mathematics, Universidad Politecnica de Madrid, Madrid, Spain 2 School of Computer Science, McGill...
Characterizing and Efficiently Computing Quadrangulations of Planar Point Sets (1997)
Prosenjit Bose, Godfried Toussaint
Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision...
Drawing Nice Projections of Objects in Space (1996)
Bose, Prosenjit, Gomez, Francisco, Ramos, Pedro, Toussaint, Godfried
Drawing Nice Projections of Objects in Space (1996)
Bose, Prosenjit, Gomez, Francisco, Ramos, Pedro, Toussaint, Godfried
Drawing Nice Projections of Objects in Space (1996)
Bose, Prosenjit, Gomez, Francisco, Ramos, Pedro, Toussaint, Godfried
All Convex Polyhedra can be Clamped with Parallel Jaw Grippers (1996)
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped usingparallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding a suitable location for the pin gate (the pin gate is the point from which liquid is poured or injected into a mold) is a difficult problem when viewed from the...
Prosenjit Bose, Godfried Toussaint
Given an n vertex simple polygon M , we show how to compute the Euclidean center of M constrained to lie in the interior of M , in a polygonal region inside M or on the boundary of M in O(n log n +...
Growing a tree from its branches (1995)
Prosenjit Bose, Godfried Toussaint, Ha A
Given a set of n disjoint line segments in the plane, we show that it is always possible to form a spanning tree of the endpoints of the segments, such that each line segment is an edge of the tree...
Growing a tree from its branches (1995)
Prosenjit Bose, Godfried Toussaint, Ha A
Given a set L of n disjoint line segments in the plane, we show that it is always possible to form a spanning tree of the endpoints of the segments, such that each line segment is an edge of the tree...
Geometric and computational aspects of gravity casting (1995)
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after the termination of the gravity casting process is an important and...
No Quadrangulation is Extremely Odd (1995)
Prosenjit Bose, Godfried Toussaint
Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision...
Drawing Nice Projections of Objects in Space (1995)
Prosenjit K. Bose, Franciso Gomez-Martin, Pedro Ramos, Godfried Toussaint
Given a polygonal object (simple polygon, geometric graph, wire-frame, skeleton or more generally a set of line segments) in three dimensional euclidean space, we consider the problem of computing a...
Converting Triangulations to Quadrangulations (1995)
Suneeta Ramaswami, Pedro Ramos, Godfried Toussaint
We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such...
Converting Triangulations to Quadrangulations (1995)
Suneeta Ramaswami, Pedro Ramos, Godfried Toussaint
We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
Prosenjit Bose, David Bremner, Godfried Toussaint
Abstract We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n+k)...
Computational geometry for document analysis (1994)
Many problems in document image analysis can be couched in geometric terms. We outline recent advances in computational geometry that contribute to many aspects of the document analysis process and...
A Counter-Example to a Fast Algorithm for Finding the Convex Hull of a Simple Polygon (1994)
A linear-time algorithm was recently published (International Conference Proceedings of Pacific Graphics'94 / CADDM'94, August 26-29, 1994, Beijing, China) for computing the convex hull of...
Illuminating The Free Space Between Quadrilaterals With Point Light Sources (1994)
Gregoria Blanco, Hazel Everett, Jesus Garcia Lopez, Godfried Toussaint
Let S be a set of n pairwise-disjoint, possibly non-convex, quadrilaterals in the plane. We consider the problem of illuminating the "free" space, i.e., the region of the plane excluding...
Feasibility of Design in Stereolithography (1993)
Boudewijn Asberg, Gregoria Blanco, Prosenjit Bose, Jesus Garcia-lopez, Mark Overmars, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Filling Polyhedral Molds (1993)
Prosenjit Bose, Marc Van Kreveld, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after termination of the gravity casting process, is an important and...
A New Look At Euclid's Second Proposition (1993)
There has been considerable interest during the past 2300 years in comparing different models of geometric computation in terms of their computing power. One of the most well known results is...
Convex hulls for random lines (1993)
Luc Devroye, Godfried Toussaint
Consider n i.i.d. random lines in the plane defined by their slope and distance from the origin. The slope is uniformly distributed on (0, 27r] and independent of the distance R from the origin....
Guarding Polyhedral Terrains (1992)
Prosenjit Bose, Thomas Shermer, Godfried Toussaint, Binhai Zhu
We prove that b n 2 c vertex guards are always sufficient and sometimes necessary to guard the surface of an n-vertex polyhedral terrain. We also show that b (4n\Gamma4) 13 c edge guards are...
Computing Morphological Properties of Arrangements of Lines (1991)
An arrangement of n lines in the plane is a partition of the plane into O(n²) faces, edges, and vertices (intersection points). Such line processes play a fundamental role in modeling spatial...
A Counter-example to a Dynamic Algorithm for Convex Hulls of Line Arrangements (1991)
Binay Bhattacharya, Hazel Everett, Godfried Toussaint
An algorithm was recently published to maintain dynamically the convex hull of the set I of intersection points of a set L of n lines in the plane [Bo90]. In other words, given the convex hull of I...
A Counter-example to a Dynamic Algorithm for Convex Hulls of Line Arrangements (1991)
Binay Bhattacharya, Hazel Everett, Godfried Toussaint
An algorithm was recently published to maintain dynamically the convex hull of the set I of intersection points of a set L of n lines in the plane [Bo90]. In other words, given the convex hull of I...
Computing Shortest Transversals (1991)
Binay K. Bhattacharya, G. Toussaint, Godfried Toussaint
We present an O(n log 2 n) time and O(n) space algorithm for computing the shortest line segment that intersects a set of n given line segments or lines in the plane. If the line segments do not...
Efficient Triangulation of Simple Polygons (1991)
This paper considers the topic of efficiently triangulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a new adaptive algorithm for triangulating...
The Graham Scan Triangulates Simple Polygons (1991)
Xianshu Kong, Hazel Everett, Godfried Toussaint
The Graham scan is a fundamental backtracking technique in computational geometry which was originally designed to compute the convex hull of a set of points in the plane and has since found...
Computational Geometry and Facility Location (1990)
Jean-Marc Robert, Godfried Toussaint
this paper we briefly survey the most recent results in the area of facility location, concentrating on versions of the problem that are likely to be unfamiliar to the transportation and management...
Slicing an Ear in Linear Time (1989)
Hossam ElGindy, Hazel Everett, Godfried Toussaint
It remains as one of the major open problems in computational geometry, whether there exists a linear-time algorithm for triangulating a simple polygon P. Yet it is well known that a diagonal of P...
Characterizations of Convex and Star-Shaped Polygons (1988)
Thomas Shermer, Godfried Toussaint
A chord of a simple polygon P is a line segment [x,y] that intersects the boundary of P only at both endpoints x and y. A chord of P is called an interior chord provided the interior of [x,y] lies in...
Quadrangulations of Planar Sets (1985)
Given a set S such as a polygon or a set of points, a quadrangulation of S is a partition of the interior of S, if S is a polygon, or the interior of the convex hull of S, if S is a set of points,...
Movable Separability of Sets (1985)
Spurred by developments in spatial planning in robotics, computer graphics, and VLSI layout, considerable attention has been devoted recently to the problem of moving sets of objects, such as line...
Let P = {p 1 , p 2 ,..., p m } and Q = {q 1 , q 2 ,..., q n } be two intersecting polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m+n) algorithm is...
On the Role of Logical, Visual and Kinesthetic Thinking in Geometry (1984)
Computational geometry is a new branch of knowledge in computer science that deals with the analysis and design of algorithms for solving geometric problems. These problems typically arise in...
Solving Geometric Problems with the Rotating Calipers (1983)
Shamos [1] recently showed that the diameter of a convex n-sided polygon could be computed in O(n) time using a very elegant and simple procedure which resembles rotating a set of calipers around the...
An Efficient Algorithm for Decomposing a Polygon into Star-Shaped Polygons (1981)
David Avis, Godfried Toussaint
In this paper we show how a theorem in plane geometry can be converted into an O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency or this new...
An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge (1981)
David Avis, Godfried Toussaint
In many computer applications areas such as graphics, automated cartography, image processing, and robotics the notion of visibility among objects modeled as polygons is a recurring theme. This paper...
An efficient algorithm for decomposing a polygon into star-shaped pieces (1981)
David Avis, Godfried Toussaint
In this paper we show how a theorem in plane geometry can be converted into an O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency or this new...
On the Detection of Structures in Noisy Pictures (1977)
Melvin Cohen, Godfried Toussaint
Hough proposed an algorithm for detecting lines in pictures. His algorithm, based on a slope-intercept parameterization of lines, was improved by Duda and Hart through the use of angle-radius...
Lower bounds for computing statistical depth
Aloupis, Greg, Cortes, Carmen, Gomez, Francisco, Soss, Michael, Toussaint, Godfried
All Convex Polyhedra can be Clamped with Parallel Jaw Grippers
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
Geometric and Computational Aspects of Gravity Casting
Prosenjit Bose, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after the termination of the gravity casting process is an important and...