Last updated May 2015
Results are separated by topic.
Journal and conference versions are mentioned together.
The indication JC ( or -C or J- ) refers to the presence of a journal and/or conference
paper. A "S" means the work is submitted.
In each category, results are listed in descending order of when they
See also the full list (in reverse chronological order)
Reconfigurations of polygonal objects
All of these papers are about moving polygonal things around to change one shape to another.
The first two results were done during my PhD but were left out of the thesis.
The stuff from fixed acute angles down to polyhedral bands is in the thesis.
Computing Signed Permutations of Polygons
with Prosenjit Bose, Erik D. Demaine,
Stefan Langerman, Henk Meijer, Mark Overmars and Godfried Toussaint,
International Journal of Computational Geometry and
Applications (IJCGA), vol.21, no.1, 2011. Also appeared at CCCG 2002.
Flat-State Connectivity of Linkages Under
with Erik D. Demaine, Vida Dujmovic, Jeff
Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars,
Michael Soss, Ileana Streinu and Godfried Toussaint,
in Proceedings of the
13th Annual International Symposium on Algorithms and Computation
Vancouver, B.C., Canada. November 2002:
Lecture Notes in Computer Science, vol.2518, p.369-380.
On Flat-State Connectivity of Chains with
Fixed Acute Angles,
with Erik D. Demaine, Henk Meijer, Joseph O'Rourke,
Ileana Streinu and Godfried Toussaint,
in Proceedings of the
14th Canadian Conference on Computational Geometry
, University of
Lethbridge, Alberta, Canada. August 12-14, 2002
16.ps NOTE: the paper below improves these results.
Reconfiguring planar dihedral chains
22nd European Workshop on Computational
, Delphi, Greece, March 27-29, 2006.
Algorithms for Computing Geometric Measures of Melodic Similarity
with Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa,
Yurai Nuñez, David Rappaport and Godfried Toussaint,
Computer Music Journal (CMJ), 30 (3), Fall 2006, pp.67-76.
Also appeared as
Computing a Geometric Measure of the Similarity Between two Melodies
at CCCG 2003.
More classes of stuck unknotted hexagons
Günter Ewald and Godfried Toussaint
Beiträge zur Algebra und Geometrie - Contributions to Algebra and
, Vol. 45, No. 2, pp. 429-434 (2004)
PostScript file (final submitted revision, Nov
Reconfiguring Triangulations with Edge Flips and Point Moves
Prosenjit Bose and Pat Morin
, Algorithmica, vol.47, issue 4 (May 2007), p.367-378. Also in the LNCS
proceedings of Graph Drawing 2004 (vol.3383, p.1-11).
Edge-Unfolding Nested Polyhedral Bands
Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana
Streinu and Godfried Toussaint,
Computational Geometry: Theory and Applications (CGTA), 39,
2008. Also appeared as
Unfolding Polyhedral Bands at CCCG 2004.
Vertex pops and popturns
, with Brad Ballinger, Prosenjit Bose, Mirela Damian, Erik
Demaine, Martin Demaine, Robin
Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz
Taslakian and Godfried Toussaint
, 19th Canadian Conference on Computational Geometry
Ottawa, Canada, August 2007
Common Unfoldings of Polyominoes and Polycubes
, with Prosenjit Bose, Sebastien Collette, Erik
Demaine, Martin Demaine, Karim Douieb, Vida Dujmovic, John Iacono,
Stefan Langerman and Pat Morin.
LNCS proceedings for selected papers of the China-Japan Joint Conference on Computational Geometry, Graphs and
Dalian, China, 2010.
Convexifying polygons without losing visibilities
with Oswin Aichholzer, Erik Demaine, Martin Demaine, Vida Dujmovic,
Ferran Hurtado, Anna Lubiw, Gunter Rote, Andre Schulz, Diane Souvaine and
I never did marry a modular robot, but I still like them very much
The first paper is the first linear-time algorithm for
reconfiguring Crystalline robots. The second paper does the same thing but
with many additional physics-minded constraints on how to do so. Way cooler.
The third paper goes in the other direction, getting faster reconfiguration
but assuming cartoon physics (i.e. none).
The fourth paper shows
how to transfer all of the above results
to other types of modular robots.
Coloring and covering things (with applications to sensor networks, naturally). Update: see the DCG paper for spicy coloring.
Linear Reconfiguration of Cube-Style Modular Robots
, with Sebastien Collette, Mirela Damian, Erik Demaine, Robin
Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera
Sacristan and Stefanie Wuhrer.
Accepted at: Computational Geometry: Theory and Applications (CGTA).
Also appeared at EGC and ISAAC in 2007.
Efficient Constant-Velocity Reconfiguration of Crystalline
, with Sebastien Collette, Mirela Damian, Erik Demaine, Dania
Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta
Sacristan and Stefanie Wuhrer. Robotica, vol.29, issue 1, pp. 59-91,
Also appeared as
Realistic Reconfiguration of Crystalline (and Telecube) Robots
El-Khechen as well, at the
Eighth International Workshop on
the Algorithmic Foundations of Robotics (WAFR'08), pp.433-447
Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves
, with Sebastien Collette, Erik Demaine, Stefan Langerman, Vera
Sacristan and Stefanie Wuhrer.
Efficient Reconfiguration for Lattice-Based Modular Robots
with Nadia Benbernou, Mirela Damian, Erik Demaine, Robin Flatland, John
Iacono and Stefanie Wuhrer.
Proc. European Conference on Mobile Robotics, p.81-86, 2009.
Here's what you get by sitting quietly in the corner and mumbling
``Tukey Depth" as the answer to any question posed in the room.
Coloring Geometric Range Spaces
, with Jean Cardinal, Sebastien Collette, Stefan Langerman and
Discrete & Computational Geometry (DCG) 41, issue 2, 2009,
p.348-362. Also appeared at LATIN and EuroCG in 2008.
Decomposition of Multiple Coverings into More Parts
Jean Cardinal, Sebastien Collette, Stefan Langerman,
David Orden and Pedro Ramos.
Discrete and Computational Geometry (DCG) 44: p.706-723, 2010.
Also appeared at SODA'09
SODA09-034.pdf. Springer DCG
Fun fact: Springer thinks ``apices" is not a word and should be replaced with ``spices". Look for it in the official version!
Jean Cardinal, Sebastien Collette, Shiniji Imahori, Matias Korman, Stefan Langerman,
Oded Schwartz, Shakhar Smorodinsky and Perouz Taslakian.
Journal of Graphs and Combinatorics (special issue).
p.1-13, 2011. Also appeared at LATIN 2010.
colorful-strips.pdf (copy of April'11 arxiv version identical to journal submission).
Or, see Springer
Establishing strong connectivity using optimal radius half-disk antennas
Mirela Damian, Robin Flatland, Matias Korman, Ozgur Ozkan, David Rappaport
and Stefanie Wuhrer.
Covering Points with Disjoint Unit Disks ,
with Robert Hearn, Hirokazu Iwasawa and Ryuhei Uehara.
Fitting Voronoi diagrams to planar tesselations,
with Hebert Perez-Roses, Guillermo Pineda-Villavicencio, Perouz Taslakian and Dannier Trinchet-Almaguer.
Combinatorial Algorithms (IWOCA) LNCS vol.8288, p.349--351, 2013.
Covering folded shapes,
with Oswin Aichholzer, Erik Demaine, Martin Demaine, Sandor Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink and Andrew Winslow.
Journal of Computational Geometry, 5:150--168, 2014. Also appeared at CCCG 2013.
Basically, my M.Sc. thesis plus some improvements. I started with the tech
report, which quickly improved to the CCCG and CGTA paper. Meanwhile,
I helped to
write about some lower bounds in CSDA,
and a couple years later got that nagging Oja lower bound (IPL).
Finally, I put together some survey information for DIMACS and COMAL.
On Computing the Bivariate Median and
the Fermat-Torricelli Problem
for Lines. With
Michael Soss and Godfried
Tech. Report # SOCS-01.2, School of Computer Science, McGill University,
* This was my first result ever. Quickly improved when Stefan came to town. See CGTA paper below *
Algorithms for Bivariate Medians and
a Fermat-Torricelli Problem
with Stefan Langerman, Michael Soss and Godfried
Computational Geometry: Theory and Applications (CGTA), Vol. 26,
August 2003, pp 69-79. Also appeared at CCCG 2001.
Lower bounds for computing statistical depth
Carmen Cortes, Francisco Gomez, Michael Soss and Godfried T. Toussaint,
Computational Statistics and Data Analysis
40 (2002) 223-229.
A Lower Bound for Computing Oja Depth
Information Processing Letters 96 (4), November 2005, p.151-153.
Geometric Measures of Data Depth
DIMACS Series in Discrete Mathematics and Theoretical
Computer Science (vol.72 Data Depth: Robust Multivariate Analysis,
Geometry and Applications), R.Liu, R.Serfling, D.Souvaine eds,
American Mathematical Society, (2006) pp.147-158.
Geometric and combinatorial issues in data depth. Short abstract contributed
to the Franco-Canadian Workshop on Combinatorial Algorithms
, McMaster University, Hamilton.
Non-crossing matchings of points with geometric objects
with Jean Cardinal, Sebastien Collette, Erik Demaine, Martin Demaine,
Muriel Dulieu, Ruy Fabila-Monroy, Vi Hart, Ferran Hurtado, Stefan
Langerman, Maria Saumell, Carlos Seara and Perouz Taslakian.
Accepted at CGTA, 2011.
Also appeared at LATIN2010 and at the Japan Conference on
Computational Geometry and Graphs, 2009, as Matching points with things
Bichromatic compatible matchings,
with Luis Barba, Stefan Langerman and Diane Souvaine.
CGTA (special issue of SoCG 2014).
Compatible Connectivity-Augmentation of Disconnected Graphs
with Luis Barba, Paz Carmi, Vida Dujmovic, Fabrizio Frati and Pat Morin.
DCG (accepted 2015). Also in SODA 2015
Matching regions in the plane using non-crossing segments
with Esther Arkin, David Bremner, Erik Demaine, Sandor Fekete,
Bahram Kouhestani and Joseph Mitchell.
Triangulating and Guarding Realistic Polygons
, with Prosenjit Bose, Vida Dujmovic, Chris Gray, Stefan Langerman
and Bettina Speckmann
, Accepted at CGTA special issue for best papers of
. CCCG 2008.
CCCG version: paper26full.pdf
. Journal version temporarily unavailable.
Meshes preserving minimum feature size, with
Erik Demaine, Martin Demaine, Vida Dujmovic and John
Proceedings of XIV Encuentros de Geometria Computacional, p.205-208, 2011
Submitted to special LNCS volume for papers of the XIV EGC.
, with Jean Cardinal, Sebastien Collette and Stefan Langerman
, LNCS Proceedings of the 5th International Conference on Computers and
Games (CG 2006) ,
Torino, Italy. vol. 4630, p.190-199, 2007.
Classic Nintendo games are (NP)-hard
with Erik Demaine and Alan Guo.
Theoretical Computer Science (accepted 2015). Also in
LNCS Notes in Computer Science, vol.8496, p.40-51, 2014.
(Proceedings of FUN'14).
Where to build a temple, and where to dig to find one
Jean Cardinal, Sebastien Collette, John Iacono and Stefan Langerman.
22nd European Workshop on Computational Geometry
, Delphi, Greece, March 27-29, 2006.
On nudism at multi-gender alien beaches (don't ask) :
Blocking Coloured Point Sets
, with Brad Ballinger, Prosejnit Bose, Sebastien Collette, Stefan
Langerman, Attila Por and David Wood.
Springer Volume on Geometric Graph Theory, 2011 (accepted).
Also at EuroCG, 2010.
What to do when you drop your polygon in the bath tub :
Draining a Polygon -or- Rolling a Ball out of a Polygon
, with Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan
Langerman and Joseph O'Rourke.
Accepted in Computational Geometry: Theory and Applications (CGTA)
. Also appeared at CCCG 2008.
What to do when you're lost at sea, with a friend:
Locating a Line at Unit Distance with Multiple Agents
with John Iacono, Jonathan Lenchner and Ozgur Ozkan.
City planning for theorists:
Highway Hull Revisited
Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman,
Joseph O'Rourke and Belen Palop.
Computational Geometry: Theory and Applications
(CGTA), vol.43, Issue 2, p.115-130, 2009.
What to do when you lose your labels:
The complexity of order type isomorphism
with John Iacono, Stefan Langerman, Ozgur Ozkan, and Stefanie Wuhrer.
SODA 2014. Earlier version appeared in EuroCG 2012, with Muriel Dulieu and Suneeta Ramaswami.
How to generate a low-energy force field that keeps enemy submarines out:
Circle separability queries in logarithmic time
with Luis Barba and Stefan Langerman.
Just what the title says:
Sum of squared edges for MST of a point set in a unit square,
with Oswin Aichholzer, Sarah Allen, Luis Barba, Prosenjit Bose, Jean-Lou de Carufel, John Iacono, Stefan Langerman and Diane Souvaine.
Continuing where Dido left off:
with Luis Barba, Jean-Lou de Carufel, Stefan Langerman and Diane Souvaine.
Graphs and Combinatorics, 31:361-392 (special issue of MCCG'13), 2015.