Sébastien Collette

I studied at Université Libre de Bruxelles, and got a Ph.D. in Computer Science, in the field of algorithms and data structures. Up to now, I acted as a researcher, as a university professor, as a consultant, as a scientific expert and as a developer. I try to never miss an opportunity to learn new stuff, whatever that means.

E-mail:

Experience

Synapsis Logo Synapsis - since 2011

Consulting, development and training agency.

ULB Logo Université Libre de Bruxelles - since 2008

Visiting professor (Maître de Conférence).

FNRS Logo F.R.S.-FNRS - 2003-2011

Full-time researcher in the field of algorithms and data-structures.

ULG Logo Université de Liège - 2010-2011

Visiting professor (Maître de Conférence).

Scientific Publications

    Journal Papers

  1. P. Bose, P. Carmi, L. Chaitman, S. Collette, M. Katz, and S. Langerman. Stable roommates spanner. Computational Geometry: Theory and Applications, to appear. Special issue of selected papers from the 22nd Canadian Conference on Computational Geometry (CCCG'10). [ bib | Abstract ]
     
  2. P. Bose, S. Collette, F. Hurtado, M. Korman, S. Langerman, V. Sacristán, and M. Saumell. Some properties of k-delaunay and k-gabriel graphs. Computational Geometry: Theory and Applications, to appear. Special issue of selected papers from the 22nd Canadian Conference on Computational Geometry (CCCG'10). 19 pages. [ bib ]
     
  3. G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman, O. Schwartz, S. Smorodinsky, and P. Taslakian. Colorful strips. Graphs and Combinatorics, to appear. Special issue of selected papers from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG09). 12 pages. [ bib | DOI ]
     
  4. G. Aloupis, J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and J. O'Rourke. Draining a polygon - or - rolling a ball out of a polygon. Computational Geometry: Theory and Applications, to appear. Special issue of selected papers from the 20th Canadian Conference on Computational Geometry (CCCG'08). 18 pages. [ bib | Abstract ]
     
  5. S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin. Entropy, triangulation, and point location in planar subdivisions. ACM Transactions on Algorithms, accepted. 19 pages. [ bib | Abstract ]
     
  6. G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu, R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara, and P. Taslakian. Non-crossing matchings of points with geometric objects. Computational Geometry: Theory and Applications, accepted. 12 pages. [ bib | Abstract ]
     
  7. G. Aloupis, S. Collette, M. Damian, E. Demaine, D. El-Khechen, R. Flatland, S. Langerman, J. O'Rourke, V. Pinciu, S. Ramaswami, V. Sacristan, and S. Wuhrer. Efficient constant-velocity reconfiguration of crystalline robots. Robotica, 29(1):59 - 71, 2011. [ bib | DOI | Abstract ]
     
  8. Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmović, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, and D. R. Wood. Every large point set contains many collinear points or an empty pentagon. Graphs and Combinatorics, 27(1):47-60, 2011. [ bib | DOI | Abstract ]
     
  9. P. Bose, P. Carmi, S. Collette, and M. Smid. On the stretch factor of convex delaunay graphs. Journal of Computational Geometry, 1(1):41 - 56, 2010. [ bib | http | Abstract ]
     
  10. G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, and P. Ramos. Decomposition of multiple coverings into more parts. Discrete and Computational Geometry, 44:706-723, 2010. [ bib | DOI | Abstract ]
     
  11. G. Aloupis, J. Cardinal, S. Collette, F. Hurtado, S. Langerman, J. O'Rourke, and B. Palop. Highway hull revisited. Computational Geometry: Theory and Applications, 43:115-130, 2010. [ bib | DOI | Abstract ]
     
  12. P. Bose, S. Collette, S. Langerman, A. Maheshwari, P. Morin, and M. Smid. Sigma-local graphs. Journal of Discrete Algorithms, 8(1):15-23, 2010. [ bib | DOI | .pdf | Abstract ]
     
  13. G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langerman, J. O'Rourke, S. Ramaswami, V. Sacristan, and S. Wuhrer. Linear reconfiguration of cube-style modular robots. Computational Geometry: Theory and Applications, 42:652-663, 2009. [ bib | DOI | .pdf | Abstract ]
     
  14. G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky. Coloring geometric range spaces. Discrete and Computational Geometry, 41:348-362, 2009. [ bib | DOI | .pdf | Abstract ]
     
  15. J. Cardinal, S. Collette, and S. Langerman. Empty region graphs. Computational Geometry: Theory and Applications, 42:183-195, 2009. [ bib | DOI | .pdf | Abstract ]
     
  16. J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and B. Palop. Optimal location of transportation devices. Computational Geometry: Theory and Applications, 41:219-229, 2008. [ bib | DOI | .pdf | Abstract ]
     
  17. S. Collette, L. Cucu, and J. Goossens. Integrating job parallelism in real-time scheduling theory. Information Processing Letters, 106:180-187, 2008. [ bib | DOI | .pdf | Abstract ]
     
  18. J. Cardinal, S. Collette, and S. Langerman. Local properties of geometric graphs. Computational Geometry: Theory and Applications, 39(1):55-64, 2008. Special issue of selected papers from the 16th Canadian Conference on Computational Geometry (CCCG'04). [ bib | DOI | .pdf | Abstract ]
     
  19. J. Cardinal, S. Collette, H. Ito, M. Korman, S. Langerman, H. Sakaidani, and P. Taslakian. Cannibal animal games: a new variant of tic-tac-toe. Journal of Recreational Mathematics, submitted. 14 pages. [ bib ]
     
  20. Refereed Conference Papers

  21. P. Bose, S. Collette, R. Fagerberg, and S. Langerman. De-amortizing binary search trees. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS, 2012. [ bib ]
     
  22. S. Collette, J. Iacono, and S. Langerman. Confluent persistence revisited. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'12), pages 593-601, 2012. [ bib | Abstract ]
     
  23. G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu, R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara, and P. Taslakian. Matching points with things. In Proceedings of the 8th Latin American Theoretical Informatics (LATIN'10), LNCS, 2010. 12 pages. [ bib ]
     
  24. G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman, O. Schwartz, S. Smorodinsky, and P. Taslakian. Colorful strips. In Proceedings of the 8th Latin American Theoretical Informatics (LATIN'10), LNCS, 2010. 12 pages. [ bib ]
     
  25. G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, and P. Ramos. Decomposition of multiple coverings into more parts. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'09), 2009. 9 pages. [ bib | Abstract ]
     
  26. G. Aloupis, S. Collette, M. Damian, E. Demaine, D. El-Khechen, R. Flatland, S. Langerman, J. O'Rourke, V. Pinciu, S. Ramaswami, V. Sacristan, and S. Wuhrer. Realistic reconfiguration of crystalline (and telecube) robots. In Proceedings of the Workshop on the Algorithmic Foundations of Robotics (WAFR'08), 2008. 18 pages. [ bib | Abstract ]
     
  27. P. Bose, P. Carmi, S. Collette, and M. Smid. On the stretch factor of convex delaunay graphs. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2008), volume 5369 of LNCS, 2008. 12 pages. [ bib | .pdf | Abstract ]
     
  28. G. Aloupis, S. Collette, E. D. Demaine, S. Langerman, V. Sacristan, and S. Wuhrer. Reconfiguration of cube-style modular robots using O(log n) parallel moves. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2008), volume 5369 of LNCS, 2008. 12 pages. [ bib | Abstract ]
     
  29. G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky. Coloring geometric range spaces. In Proceedings of the 8th Latin American Theoretical Informatics (LATIN'08), volume 4957 of LNCS, 2008. 12 pages. [ bib | DOI | .pdf | Abstract ]
     
  30. S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin. Distribution-sensitive point location in convex subdivisions. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 2008. 11 pages. [ bib | .pdf | Abstract ]
     
  31. G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langerman, J. O'Rourke, S. Ramaswami, V. Sacristan, and S. Wuhrer. Linear reconfiguration of cube-style modular robots. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC 2007), volume 4835 of LNCS, 2007. 14 pages. [ bib | DOI | .pdf | Abstract ]
     
  32. S. Collette, L. Cucu, and J. Goossens. Algorithm and complexity for the global scheduling of sporadic tasks on multiprocessors with work-limited parallelism. In Proceedings of the 15th International Conference on Real-Time and Network systems (RTNS'2007), 2007. 6 pages. [ bib | Abstract ]
     
  33. G. Aloupis, J. Cardinal, S. Collette, and S. Langerman. Lumines strategies. In Proceedings of the 5th International Conference on Computers and Games (CG 2006), volume 4630 of LNCS, pages 190-199, 2007. [ bib | DOI | .pdf | Abstract ]
     
  34. S. Collette, J.-F. Raskin, and F. Servais. On the symbolic computation of the hardest configurations of the rush hour game. In Proceedings of the 5th International Conference on Computers and Games (CG 2006), volume 4630 of LNCS, pages 220-233, 2007. [ bib | DOI | .pdf | Abstract ]
     
  35. Local or Unrefereed Conference Papers

  36. J. Cardinal, N. Cohen, S. Collette, M. Hoffmann, S. Langerman, and G. Rote. Coloring dynamic point sets on a line. In Proceedings of the 28th European Workshop on Computational Geometry (EuroCG12), 2012. [ bib ]
     
  37. J. Cardinal, S. Collette, H. Ito, M. Korman, S. Langerman, H. Sakaidani, and P. Taslakian. Cannibal animal games: a new variant of tic-tac-toe. In Proceedings of the 27th European Workshop on Computational Geometry (EuroCG11), 2011. 4 pages. [ bib ]
     
  38. J. Cardinal, S. Collette, H. Ito, M. Korman, S. Langerman, H. Sakaidani, and P. Taslakian. Cannibal animal games: a new variant of tic-tac-toe. In Proceedings of the 4th Annual Meeting of AAAC (AAAC11), 2011. 2 pages. [ bib ]
     
  39. G. Aloupis, P. Bose, S. Collette, E. D. Demaine, M. L. Demaine, K. Douieb, V. Dujmovic, J. Iacono, S. Langerman, and P. Morin. Common unfoldings of polyominoes and polycubes. In Proceedings of the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), 2010. 2 pages. [ bib ]
     
  40. G. Aloupis, B. Ballinger, S. Collette, S. Langerman, A. Por, and D. R. Wood. Blocking coloured point sets. In Proceedings of the 26th European Workshop on Computational Geometry (EuroCG10), 2010. 4 pages. [ bib ]
     
  41. P. Bose, S. Collette, F. Hurtado, M. Korman, S. Langerman, V. Sacristan, and M. Saumell. Some Properties of Higher Order Delaunay and Gabriel Graphs. In Proceedings of the Canadian Conference on Computational Geometry (CCCG10), 2010. 4 pages. [ bib | Abstract ]
     
  42. V. Berten, S. Collette, and J. Goossens. Feasibility test for multi-phase parallel real-time jobs. In Proceedings of the Work-in-Progress session of the IEEE Real-Time Systems Symposium 2009, 2009. 4 pages. [ bib ]
     
  43. G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman, O. Schwartz, S. Smorodinsky, and P. Taslakian. Colorful strips. In Proceedings of the 7th Japan Conference on Computational Geometry and Graphs (JCCGG09), 2009. 2 pages. [ bib ]
     
  44. G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu, R. Fabila-Monroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara, and P. Taslakian. Matching points with things. In Proceedings of the 7th Japan Conference on Computational Geometry and Graphs (JCCGG09), 2009. 2 pages. [ bib ]
     
  45. P. Bose, J. Cardinal, S. Collette, E. D. Demaine, B. Palop, P. Taslakian, and N. Zeh. Relaxed Gabriel Graphs. In Proceedings of the Canadian Conference on Computational Geometry (CCCG09), 2009. 4 pages. [ bib | Abstract ]
     
  46. Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmović, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, and D. R. Wood. Every large point set contains many collinear points or an empty pentagon. In Proceedings of the Canadian Conference on Computational Geometry (CCCG09), 2009. 4 pages. [ bib | Abstract ]
     
  47. G. Aloupis, J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and J. O'Rourke. Draining a polygon - or - rolling a ball out of a polygon. In Proceedings of the Canadian Conference on Computational Geometry (CCCG08), 2008. 7 pages. [ bib ]
     
  48. G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky. Coloring geometric range spaces. In Proceedings of the 24th European Workshop on Computational Geometry (EuroCG08), 2008. 4 pages. [ bib ]
     
  49. G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langerman, J. O'Rourke, S. Ramaswami, V. Sacristan, and S. Wuhrer. Linear reconfiguration of cube-style modular robots. In Proceedings of the XII Encuentros de Geometría Computacional (EGC'07), 2007. 8 pages. [ bib ]
     
  50. J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and B. Palop. Moving walkways, escalators, and elevators. In Proceedings of the XII Encuentros de Geometría Computacional (EGC'07), 2007. 8 pages. [ bib ]
     
  51. S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin. Distribution-sensitive point location in convex subdivisions. In Proceedings of the 17th Fall Workshop on Computational and Combinatorial Geometry, 2007. 2 pages. [ bib ]
     
  52. J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and B. Palop. Moving walkways, escalators, and elevators. In Proceedings of the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT2007), 2007. 2 pages. [ bib | http | Abstract ]
     
  53. G. Aloupis, J. Cardinal, S. Collette, J. Iacono, and S. Langerman. Where to build a temple, and where to dig to find one. In Proceedings of the 22nd European Workshop on Computational Geometry (EuroCG06), 2006. 4 pages. [ bib | .pdf | Abstract ]
     
  54. J. Cardinal, S. Collette, and S. Langerman. Region counting circles. In Proceedings of the Canadian Conference on Computational Geometry (CCCG05), pages 278-281, 2005. 4 pages. [ bib | .pdf | Abstract ]
     
  55. J. Cardinal, S. Collette, and S. Langerman. Region counting graphs. In Proceedings of the 21st European Workshop on Computational Geometry (EuroCG05), 2005. 4 pages. [ bib | .pdf | Abstract ]
     
  56. J. Cardinal, S. Collette, and S. Langerman. Local properties of geometric graphs. In Proceedings of the Canadian Conference on Computational Geometry (CCCG04), 2004. 4 pages. [ bib | .pdf | Abstract ]
     
  57. PhD Thesis

  58. S. Collette. Regions, Distances and Graphs. PhD thesis, Université Libre de Bruxelles, 2006. Committee: J. Cardinal, S. Fiorini, S. Langerman, G. Louchard, P. Morin, A. Wolff. [ bib | .pdf ]
     
  59. Technical Reports

  60. P. Bose, J. Cardinal, S. Collette, F. Hurtado, M. Korman, S. Langerman, and P. Taslakian. Coloring and guarding arrangements. Technical Report arXiv:1205.5162, arXiv, Cornell University, 2012. 13 pages. [ bib | http | Abstract ]
     
  61. P. Bose, S. Collette, R. Fagerberg, and S. Langerman. De-amortizing binary search trees. Technical Report arXiv:1111.1665, arXiv, Cornell University, 2011. 14 pages. [ bib | http | Abstract ]
     
  62. S. Collette, J. Iacono, and S. Langerman. Confluent persistence revisited. Technical Report arXiv:1104.3045, arXiv, Cornell University, 2011. 15 pages. [ bib | http | Abstract ]
     
  63. P. Bose, S. Collette, R. Fagerberg, and S. Langerman. De-amortizing binary search trees. Technical Report arXiv:1111.1665, arXiv, Cornell University, 2011. 14 pages. [ bib | http | Abstract ]
     
  64. G. Aloupis, B. Ballinger, S. Collette, S. Langerman, A. Por, and D. R. Wood. Blocking coloured point sets. Technical Report arXiv:1002.0190, arXiv, Cornell University, 2010. 17 pages. [ bib | http | Abstract ]
     
  65. G. Aloupis, S. Collette, E. D. Demaine, S. Langerman, V. Sacristan, and S. Wuhrer. Reconfiguration of 3D crystalline robots using O(log n) parallel moves. Technical Report arXiv:0908.2440, arXiv, Cornell University, 2009. 21 pages. [ bib | http | Abstract ]
     
  66. G. Aloupis, J. Cardinal, S. Collette, J. Iacono, and S. Langerman. Detecting all regular polygons in a point set. Technical Report arXiv:0908.2442, arXiv, Cornell University, 2009. 11 pages. [ bib | http | Abstract ]
     
  67. G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman, O. Schwartz, S. Smorodinsky, and P. Taslakian. Colorful strips. Technical Report arXiv:0904.2115, arXiv, Cornell University, 2009. 11 pages. [ bib | http | Abstract ]
     
  68. Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmović, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, and D. R. Wood. Every large point set contains many collinear points or an empty pentagon. Technical Report arXiv:0904.0262, arXiv, Cornell University, 2009. 14 pages. [ bib | http | Abstract ]
     
  69. S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin. Entropy, triangulation, and point location in planar subdivisions. Technical Report arXiv:0901.1908, arXiv, Cornell University, 2009. 19 pages. [ bib | http ]
     
  70. G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, and P. Ramos. Decomposition of multiple coverings into more parts. Technical Report arXiv:0807.0552, arXiv, Cornell University, 2008. 14 pages. [ bib | http | Abstract ]
     
  71. G. Aloupis, J. Cardinal, S. Collette, F. Hurtado, S. Langerman, J. O'Rourke, and B. Palop. Highway hull revisited. Technical Report arXiv:0806.1416, arXiv, Cornell University, 2008. 18 pages. [ bib | http | Abstract ]
     
  72. S. Collette, L. Cucu, and J. Goossens. Integrating job parallelism in real-time scheduling theory. Technical Report arXiv:0805.3237, arXiv, Cornell University, 2008. 14 pages. [ bib | http | Abstract ]
     
  73. Z. Abel, D. Charlton, S. Collette, E. D. Demaine, M. L. Demaine, S. Langerman, J. O'Rourke, V. Pinciu, and G. Toussaint. Cauchy's arm lemma on a growing sphere. Technical Report arXiv:0804.0986, arXiv, Cornell University, 2008. 10 pages. [ bib | http | Abstract ]
     
  74. P. Bose, P. Carmi, S. Collette, and M. Smid. On the stretch factor of convex delaunay graphs. Technical Report arXiv:0804.1041, arXiv, Cornell University, 2008. 16 pages. [ bib | http | Abstract ]
     
  75. J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and B. Palop. Moving walkways, escalators, and elevators. Technical Report arXiv:0705.0635, arXiv, Cornell University, 2007. 16 pages. [ bib | http | Abstract ]
     
  76. S. Collette, J. Iacono, S. Langerman, and P. Morin. Distribution-sensitive point location in convex subdivisions. Technical Report TR-06-13, Carleton University - School of Computer Science, 2006. 15 pages. [ bib | http ]