GREG's PAGE on ACADEMICS

This is a somewhat chronologically ordered full list. Last updated July 2015.
See also the list by topic.

Journal papers (published or accepted)

Compatible Connectivity-Augmentation of Disconnected Graphs , with Luis Barba, Paz Carmi, Vida Dujmovic, Fabrizio Frati and Pat Morin. DCG (accepted 2015)

pdf file arXiv

Classic Nintendo games are (computationally) hard , with Erik Demaine, Alan Guo, and Giovanni Viglietta. Theoretical Computer Science (accepted 2015).

pdf file arXiv

Isoperimetric enclosures, with Luis Barba, Jean-Lou de Carufel, Stefan Langerman and Diane Souvaine. Graphs and Combinatorics, 31:361-392, 2015. (special issue of MCCG'13).

pdf file temporarily unavailable

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.

pdf file JoCG link

Bichromatic compatible matchings, with Luis Barba, Stefan Langerman and Diane Souvaine. CGTA (special issue of SoCG), 2014.

pdf file arXiv

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. CGTA 46:78--92, 2013

pdf file link

Blocking Coloured Point Sets , with Brad Ballinger, Prosejnit Bose, Sebastien Collette, Stefan Langerman, Attila Por and David Wood. Algorithms and Combinatorics, 29:31--48, 2013. (Special Springer collection: Thirty Essays on Geometric Graph Theory).

pdf file link to arXiv version

Efficient Reconfiguration for Lattice-Based Modular Robots , with Nadia Benbernou, Mirela Damian, Erik Demaine, Robin Flatland, John Iacono and Stefanie Wuhrer. CGTA, accepted 2012.

pdf file Temporarily Unavailable

Triangulating and Guarding Realistic Polygons , with Prosenjit Bose, Vida Dujmovic, Chris Gray, Stefan Langerman and Bettina Speckmann , CGTA special issue for 20th CCCG, 2011 (accepted)

pdf file temporarily unavailable

Efficient Constant-Velocity Reconfiguration of Crystalline Robots , with Sebastien Collette, Mirela Damian, Erik Demaine, Dania El-Khechen, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristan and Stefanie Wuhrer. Robotica, vol.29, issue 1, pp. 59-91, 2011.

pdf file robotica.pdf Direct link: cambridge.org copyright Cambridge University Press.

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.

pdf file permutations-ijcga.pdf

Colorful Strips , with 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.

pdf file colorful-strips.pdf (copy of April'11 arxiv version identical to journal submission). Or, see Springer link.

Decomposition of Multiple Coverings into More Parts , with Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos. Discrete and Computational Geometry (DCG) 44: p.706-723, 2010.

pdf file Springer DCG link.
Fun fact: Springer thinks ``apices" is not a word and should be replaced with ``spices". Look for it in the official version!

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)

pdf file draining-sept2008.pdf

Highway Hull Revisited , with 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.

pdf file highwayhull-CGTA.pdf

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)

pdf file linear-modular-CGTA.pdf

Coloring Geometric Range Spaces , with Jean Cardinal, Sebastien Collette, Stefan Langerman and Shakhar Smorodinsky. Discrete & Computational Geometry (DCG) 41, issue 2, 2009, p.348-362

pdf file ACCLS07b.pdf

Edge-Unfolding Nested Polyhedral Bands , with Erik D. Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu and Godfried Toussaint, Computational Geometry: Theory and Applications (CGTA), 39, p.30-42, 2008.

pdf file band-unfolding.pdf

Reconfiguring Triangulations with Edge Flips and Point Moves , with Prosenjit Bose and Pat Morin , Algorithmica, vol.47, issue 4 (May 2007), p.367-378.

pdf file triangulations-algorithmica.pdf

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.

pdf file melody.pdf

A Lower Bound for Computing Oja Depth , with Erin McLeish. Information Processing Letters 96 (4), November 2005, p.151-153.

pdf file of submitted version, September 2004: oja-depth-IPL.pdf

More classes of stuck unknotted hexagons , with Günter Ewald and Godfried Toussaint , Beiträge zur Algebra und Geometrie - Contributions to Algebra and Geometry , Vol. 45, No. 2, pp. 429-434 (2004)

PostScript file (final submitted revision, Nov 2003) locked.ps

Lower bounds for computing statistical depth , with Carmen Cortes, Francisco Gomez, Michael Soss and Godfried T. Toussaint, Computational Statistics and Data Analysis 40 (2002) 223-229.

PostScript file (final submitted revision, October 2001) StatDepth_Oct01.ps

Algorithms for Bivariate Medians and a Fermat-Torricelli Problem for Lines, with Stefan Langerman, Michael Soss and Godfried Toussaint, Computational Geometry: Theory and Applications (CGTA), Vol. 26, No. 1, August 2003, pp 69-79.

PostScript file (revised November 2002 version) mediansCGTA.ps

Conference papers (published or accepted)

Matching regions in the plane using non-crossing segments , with Esther Arkin, David Bremner, Erik Demaine, Sandor Fekete, Bahram Kouhestani and Joseph Mitchell. EGC, 2015.
- pdf file temporarily unavailable
Compatible Connectivity-Augmentation of Disconnected Graphs , with Luis Barba, Paz Carmi, Vida Dujmovic, Fabrizio Frati and Pat Morin. SODA 2015

pdf file arXiv

The complexity of order type isomorphism , with John Iacono, Stefan Langerman, Ozgur Ozkan, and Stefanie Wuhrer. SODA 2014

pdf file arXiv

Isoperimetric enclosures, with Luis Barba, Jean-Lou de Carufel, Stefan Langerman and Diane Souvaine. MCCG 2013

pdf file temporarily unavailable

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. JCDCG 2013.

pdf file temporarily unavailable

Covering folded shapes, with Oswin Aichholzer, Erik Demaine, Martin Demaine, Sandor Fekete, Michael Hoffmann, Anna Lubiw, Jack Snoeyink and Andrew Winslow. CCCG 2013.

pdf file JoCG link

Bichromatic compatible matchings, with Luis Barba, Stefan Langerman and Diane Souvaine. SoCG, 2013

pdf file arXiv

Classic Nintendo games are (Computationally) hard , with Erik Demaine, Alan Guo, and Giovanni Viglietta. LNCS Notes in Computer Science, vol.8496, p.40-51, 2014. (Proceedings of FUN'14).

pdf file arXiv

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.

pdf file temporarily unavailable

Locating a Line at Unit Distance with Multiple Agents , with John Iacono, Jonathan Lenchner and Ozgur Ozkan. TJJCCGG 2012

pdf file temporarily unavailable

Circle separability queries in logarithmic time , with Luis Barba and Stefan Langerman. CCCG 2012

pdf file link

Covering Points with Disjoint Unit Disks , with Robert Hearn, Hirokazu Iwasawa and Ryuhei Uehara. CCCG 2012

pdf file link

Order type invariant labeling and comparison of point sets , with Muriel Dulieu, John Iacono, Stefan Langerman, Ozgur Ozkan, Suneeta Ramaswami and Stefanie Wuhrer. EuroCG 2012

pdf file (see arXived SODA version: arXiv)

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 Andrew Winslow. CCCG 2011

pdf file link

Establishing strong connectivity using optimal radius half-disk antennas , with Mirela Damian, Robin Flatland, Matias Korman, Ozgur Ozkan, David Rappaport and Stefanie Wuhrer. CCCG 2011

pdf file link

Meshes preserving minimum feature size, with Erik Demaine, Martin Demaine, Vida Dujmovic and John Iacono. Proceedings of XIV Encuentros de Geometria Computacional, p.205-208, 2011 Submitted to special LNCS volume for papers of the XIV EGC.

pdf file link to entire proceedings

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 Applications (CGGA). Dalian, China, 2010.

pdf file temporarily unavailable

Colorful Strips , with Jean Cardinal, Sebastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky and Perouz Taslakian. LATIN 2010. Also appeared at Japan Conference on Computational Geometry and Graphs, 2009.

pdf file temporarily unavailable

Matching points with things , 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. LATIN 2010. Also appeared at the Japan Conference on Computational Geometry and Graphs, 2009.

pdf file temporarily unavailable

Blocking Coloured Point Sets , with Brad Ballinger, Prosejnit Bose, Sebastien Collette, Stefan Langerman, Attila Por and David Wood. EuroCG, 2010.

pdf file blockers-eurocg.pdf

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.

pdf file ECMR.pdf

Realistic Reconfiguration of Crystalline (and Telecube) Robots , with Sebastien Collette, Mirela Damian, Erik Demaine, Dania El-Khechen, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristan and Stefanie Wuhrer. In the Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR'08)

pdf file robots-wafr.pdf

Decomposition of Multiple Coverings into More Parts , with Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos. SODA'09

pdf file SODA09-034.pdf

Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves , with Sebastien Collette, Erik Demaine, Stefan Langerman, Vera Sacristan and Stefanie Wuhrer. ISAAC'08

pdf file logn-robots-isaac.pdf

Draining a Polygon -or- Rolling a Ball out of a Polygon , with Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman and Joseph O'Rourke. CCCG 2008

pdf file draining-cccg.pdf

Triangulating and Guarding Realistic Polygons , with Prosenjit Bose, Vida Dujmovic, Chris Gray, Stefan Langerman and Bettina Speckmann , CCCG 2008

pdf file paper26full.pdf

Coloring Geometric Range Spaces , with Jean Cardinal, Sebastien Collette, Stefan Langerman and Shakhar Smorodinsky.
- 8th Latin American Theoretical Information Symposium. Buzios, Brazil. April 2008.
  - pdf file ACCLS07c.pdf
- 24th European Workshop on Computational Geometry. Nancy, France. March 2008.
  - pdf file see above
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

pdf file pops-cccg07.pdf

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,
- XII Encuentros de Geometria Computacional (EGC 2007) Valladolid, Spain, June 2007.
  - pdf file cube-robots-EGC07.pdf
- 18th International Symposium on Algorithms and Computation (ISAAC) , Sendai, Japan, December 2007.
  - pdf file cbots_ISAAC.pdf
LUMINES Strategies , 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.

pdf file lumines.pdf

Reconfiguring planar dihedral chains , with Henk Meijer. 22nd European Workshop on Computational Geometry (EWCG'06) , Delphi, Greece, March 27-29, 2006.

PDF file dihedral-ewcg06.pdf

Where to build a temple, and where to dig to find one , with Jean Cardinal, Sebastien Collette, John Iacono and Stefan Langerman. 22nd European Workshop on Computational Geometry (EWCG'06) , Delphi, Greece, March 27-29, 2006.

PDF file temples-ewcg06.pdf

Geometric Measures of Data Depth DIMACS Series in Discrete Mathematics and Theoretical Computer Science (vol.72 Data Depth: Robust Multivariate Analysis, Computational Geometry and Applications), R.Liu, R.Serfling, D.Souvaine eds, American Mathematical Society, (2006) pp.147-158.

pdf file depth.pdf

Reconfiguring Triangulations with Edge Flips and Point Moves with Prosenjit Bose and Pat Morin, 12th International Symposium on Graph Drawing (GD'04), City College, NYC. In Lecture Notes in Computer Science 3383, pages 1-11, 2004. * Invited for submission to Algorithmica (see journal version above)*

PostScript GD-triangulations.ps

PDF

GD-triangulations.pdf

or you can try

Springer official copy (permission may be required)

Unfolding Polyhedral Bands , with Erik Demaine, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu and Godfried Toussaint, In proceedings of the 16th Canadian Conference on Computational Geometry (CCCG'04) , Concordia University, Montreal, August 9-11, 2004, pages 60-63. * Invited for submission to CGTA (see journal version above) *

PostScript file band-cccg.ps

Computing a Geometric Measure of the Similarity Between two Melodies , with Thomas Fevens, Stefan Langerman, Tomomi Matsui, Antonio Mesa, Yurai Nuñez, David Rappaport and Godfried Toussaint, in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG'03) , Dalhousie University, Halifax, August 11-13, 2003, pp. 81-84. * see full paper in journal section above *

PostScript file melody.ps

Computing Signed Permutations of Polygons, with Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars and Godfried Toussaint, in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG'02), p.68-71 , University of Lethbridge, Alberta, Canada. August 12-14, 2002.

PostScript file (short version) 23m.ps (long version) 23l.ps

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 (CCCG'02), p.27-30 , University of Lethbridge, Alberta, Canada. August 12-14, 2002

PostScript file 16.ps

Flat-State Connectivity of Linkages Under Dihedral Motions, with Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan 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 (ISAAC 2002), Vancouver, B.C., Canada. November 2002: Lecture Notes in Computer Science, vol.2518, p.369-380.

PostScript file f2fISAAC.ps

Algorithms for Bivariate Medians and a Fermat-Torricelli Problem for Lines, with Stefan Langerman, Michael Soss and Godfried Toussaint, in Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01) , University of Waterloo, August 13-15, 2001, pp. 21-24. * Invited for submission to CGTA (see journal version above)*

PostScript file ALST_CCCG.ps

Conference abstracts (no more than one page)

Geometric and combinatorial issues in data depth, at the Franco-Canadian Workshop on Combinatorial Algorithms (COMAL 2005) , McMaster University, Hamilton.

Old Technical Reports

On Computing the Bivariate Median and the Fermat-Torricelli Problem for Lines, with Michael Soss and Godfried Toussaint, Tech. Report # SOCS-01.2, School of Computer Science, McGill University, February, 2001.

PostScript file SOCS.01.2.ps compressed: SOCS.

Lower Bounds for Computing Statistical Depth, with Carmen Cortes, Francisco Gomez, Michael Soss and Godfried Toussaint, Tech. Report # SOCS-01.1, School of Computer Science, McGill University, February, 2001.

PostScript file SOCS.01.1.ps compressed: SOCS.