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
were obtained.
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.
- JC
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.
- -C
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.
- -C
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 NOTE: the paper below improves these results.
- -C
Reconfiguring planar dihedral chains
, with
Henk Meijer.
22nd European Workshop on Computational
Geometry
(EWCG'06)
, Delphi, Greece, March 27-29, 2006.
- JC
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.
- J-
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
- JC
Reconfiguring Triangulations with Edge Flips and Point Moves
, with
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).
- JC
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. Also appeared as
Unfolding Polyhedral Bands at CCCG 2004.
- -C
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
- -C
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.
- -C
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
Modular robots
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.
- JC
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.
- JC
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.
Also appeared as
Realistic Reconfiguration of Crystalline (and Telecube) Robots
with Dania
El-Khechen as well, at the
Eighth International Workshop on
the Algorithmic Foundations of Robotics (WAFR'08), pp.433-447
- -C
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
- -C
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.
Coloring and covering things (with applications to sensor networks, naturally). Update: see the DCG paper for spicy coloring.
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.
- JC
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. Also appeared at LATIN and EuroCG in 2008.
- JC
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.
Also appeared at SODA'09
-
pdf file
SODA09-034.pdf. 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!
- JC
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. Also appeared at LATIN 2010.
-
pdf file
colorful-strips.pdf (copy of April'11 arxiv version identical to journal submission).
Or, see Springer
link.
- -C
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
- -C
Covering Points with Disjoint Unit Disks ,
with Robert Hearn, Hirokazu Iwasawa and Ryuhei Uehara.
CCCG 2012
- -C
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.
- JC
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.
Data depth
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.
- [tech]
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.
* This was my first result ever. Quickly improved when Stefan came to town. See CGTA paper below *
- JC
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. Also appeared at CCCG 2001.
- J-
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.
- J-
A Lower Bound for Computing Oja Depth
, with
Erin McLeish.
Information Processing Letters 96 (4), November 2005, p.151-153.
- -C
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.
- -c
Geometric and combinatorial issues in data depth. Short abstract contributed
to the Franco-Canadian Workshop on Combinatorial Algorithms
(COMAL 2005)
, McMaster University, Hamilton.
Matchings
- JC
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
- JC
Bichromatic compatible matchings,
with Luis Barba, Stefan Langerman and Diane Souvaine.
CGTA (special issue of SoCG 2014).
- JC
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
- -C
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.
Realistic input/output
- JC
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.
-
pdf file
CCCG version: paper26full.pdf
. Journal version temporarily unavailable.
- -C
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.
Computer games
- -C
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.
- JC
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).
Other
Computational archaeology:
- -C
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.
On nudism at multi-gender alien beaches (don't ask) :
- JC
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 :
- JC
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.
TJJCCGG 2012
City planning for theorists:
- J-
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.
What to do when you lose your labels:
- -C
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:
- -C
Circle separability queries in logarithmic time
,
with Luis Barba and Stefan Langerman.
CCCG 2012
Just what the title says:
- -C
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.
Continuing where Dido left off:
- JC
Isoperimetric enclosures,
with Luis Barba, Jean-Lou de Carufel, Stefan Langerman and Diane Souvaine.
Graphs and Combinatorics, 31:361-392 (special issue of MCCG'13), 2015.