Sébastien Collette
Algorithms Research Group - Computer Science Department

Chargé de Recherches du F.R.S.-FNRS
Maître de Conférences
(INFO-F-309)
Ph.D. in Computer Science (2006)


Keywords: Computational geometry, data structures.

Office: O8.212, N.O. Building, Campus de la Plaine
Address: CP 212, Bvd. du Triomphe, 1050 Brussels
Tel:
+32 2 650.5606
Fax: +32 2 650.5609
E-mail: Sebastien.Collette@ulb.ac.be

Publications

    Journal Papers

  1. G. Aloupis, J. Cardinal, S. Collette, S. Langerman, D. Orden, and P. Ramos. Decomposition of multiple coverings into more parts. Discrete and Computational Geometry, to appear. 15 pages. [ bib | DOI | Abstract ]
     
  2. 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 ]
     
  3. 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 ]
     
  4. 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 ]
     
  5. 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 ]
     
  6. 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 ]
     
  7. J. Cardinal, S. Collette, and S. Langerman. Empty region graphs. Computational Geometry: Theory and Applications, 42:183-195, 2009. [ bib | DOI | .pdf | Abstract ]
     
  8. 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 ]
     
  9. 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 ]
     
  10. 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 ]
     
  11. 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, submitted. 30 pages. [ bib | Abstract ]
     
  12. 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, submitted. 14 pages. [ bib | Abstract ]
     
  13. S. Collette, E. D. Demaine, M. L. Demaine, and S. Langerman. Narrow misere dots-and-boxes. Games of No Chance IV, submitted. 6 pages. [ bib ]
     
  14. S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin. Entropy, triangulation, and point location in planar subdivisions. ACM Transactions on Algorithms, submitted. 19 pages. [ bib | Abstract ]
     
  15. P. Bose, P. Carmi, S. Collette, and M. Smid. On the stretch factor of convex delaunay graphs. Journal of Computational Geometry, submitted. 16 pages. [ bib | Abstract ]
     
  16. Refereed Conference Papers

  17. 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 ]
     
  18. 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 ]
     
  19. 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 ]
     
  20. 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 ]
     
  21. 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 ]
     
  22. 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 ]
     
  23. 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 ]
     
  24. 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 ]
     
  25. 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 ]
     
  26. 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 ]
     
  27. 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 ]
     
  28. 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 ]
     
  29. Local or Unrefereed Conference Papers

  30. 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 ]
     
  31. 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 ]
     
  32. 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 ]
     
  33. 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 ]
     
  34. 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 ]
     
  35. 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 ]
     
  36. 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 ]
     
  37. 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 ]
     
  38. 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 ]
     
  39. 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 ]
     
  40. 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 ]
     
  41. 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 ]
     
  42. 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 ]
     
  43. 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 ]
     
  44. 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 ]
     
  45. 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), submitted. 4 pages. [ bib ]
     
  46. PhD Thesis

  47. 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 ]
     
  48. Technical Reports

  49. 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 ]
     
  50. 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 ]
     
  51. 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 ]
     
  52. 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 ]
     
  53. 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 ]
     
  54. 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 ]
     
  55. 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 ]
     
  56. 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 ]
     
  57. 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 ]
     
  58. 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 ]
     
  59. 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 ]
     
  60. 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 ]
     

My Co-authors

Conferences, Workshops, Talks and Visits

  • RTSS 09, 01/12/2009 - 04/12/2009, Washington DC, USA
    Paper: Feasibility test for multi-phase parallel real-time jobs
  • JCCGG 09, 11/11/2009 - 13/11/2009, Kanazawa, Japan
    Paper: Colorful strips
    Paper: Matching points with things
  • Dagstuhl Seminar 09451, 01/11/2009 - 06/11/2009, Saarbrücken, Germany
  • Canada-Japan Workshop on Discrete and Computational Geometry 09, 13/07/2009 - 15/07/2009, Tokyo, Japan
    Talk:
    Decomposition of multiple coverings into more parts
  • Carleton Workshop on Computational Geometry 09, 04/05/2009 - 08/05/2009, Ottawa, Canada
    Talk: Proximity Graphs and their Properties
  • UPC-ULB Workshop on Computational Geometry 09, 01/04/2009 - 03/04/2009, Barcelona (UPC), Spain
  • WAFOL 09, 19/03/2009 - 21/03/2009, Brussels (ULB), Belgium
  • EuroCG 09, 16/03/2009 - 18/03/2009, Brussels (ULB), Belgium
    Member of the Organizing Committee
    Member of the Program Committee
  • Winter Workshop on Computational Geometry 09, 06/02/2009 - 13/02/2009, Holetown (McGill U.), Barbados
  • SODA 09, 04/01/2009 - 06/01/2009, New York, USA
    Paper: Decomposition of multiple coverings into more parts
  • Assembly of the European Academy of Sciences, 07/09/2008, Brussels, Belgium
  • Carleton Computational Geometry Lab Seminars, 20/08/2008, Ottawa, Canada
    Talk: Highway Hull Revisited
  • CCCG 08, 13/08/2008 - 15/08/2008, Montreal (McGill), Canada
    Member of the Program Committee
    Paper:  Draining a polygon - or - rolling a ball out of a polygon
  • Visiting researcher at Carleton University, August 2008, Ottawa, Canada
  • BWAR 08, 14/04/2008 - 18/04/2008, Brussels (ULB), Belgium
  • Winter Workshop on Computational Geometry 08, 01/02/2008 - 08/02/2008, Holetown (McGill U.), Barbados
  • Visiting researcher at MIT, January 2008, Cambridge, USA
  • SODA 08, 20/01/2008 - 22/01/2008, San Francisco, USA
    Talk: Distribution-sensitive point location in convex subdivisions
  • CCCG 07, 20/08/2007 - 22/08/2007, Ottawa (Carleton), Canada
    Member of the Program Committee
  • Visiting researcher at Carleton University, August 2007, Ottawa, Canada
  • EGC 07, 25/06/2007 - 27/06/2007, Valladolid, Spain
    Talk: Moving walkways, escalators, and elevators
    Paper: Linear reconfiguration of cube-style modular robots
  • KyotoCGGT07, 11/06/2007 - 15/06/2007, Kyoto, Japan
    Paper: Moving walkways, escalators, and elevators
  • Visiting researcher at Roosevelt Academy, May 2007, Middelburg, The Netherlands
  • EuroCG 07, 19/03/2007 - 21/03/2007, Graz, Austria
  • Winter Workshop on Computational Geometry 07, 2/02/2007 - 9/02/2007, Holetown (McGill U.), Barbados
  • Dagstuhl Seminar 06481, 26/11/2006 - 01/12/2006, Saarbrücken, Germany
  • Algo 06, 11/09/2006 - 15/09/2006, Zurich (ETHZ), Switzerland
  • CCCG 06, 14/08/2006 - 16/08/2006, Kingston (Queen's U), Canada
  • Carleton Computational Geometry Lab Seminars, 08/08/2006, Ottawa, Canada
    Talk: Where to dig for a temple: finding regular polygons in sets of points
  • Visiting researcher at Carleton University, July-August 2006, Ottawa, Canada
  • Computer and Games 2006, 29/05/2006 - 31/05/2006, Torino, Italy
    Talk: Lumines Strategies
    Paper: On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game
  • EuroCG 06, 27/03/2006 - 29/03/2006, Delphi, Greece
    Paper: Where to build a temple, and where to dig to find one
  • WADS 05, 15/08/2005 - 17/08/2005, Waterloo, Canada
  • CCCG 05, 10/08/2005 - 12/08/2005, Windsor, Canada
    Talk: Region Counting Circle
  • Carleton Computational Geometry Lab Seminars, 26/7/2005, Ottawa, Canada
    Talk: Empty Region Graphs
  • Carleton-Eindhoven Workshop on Computational Geometry 05, 18/07/2005 - 22/07/2005, Ottawa, Canada
  • Visiting researcher at Carleton University, July-August 2005, Ottawa, Canada
  • BeneluxIT, 19/05/2005 - 20/05/2005, Brussels (ULB), Belgium
  • BWAR 05, 03/05/2005 - 08/05/2005, Brussels (ULB), Belgium
  • EuroCG 05, 09/03/2005 - 11/03/2005, Eindhoven (TU/e), The Netherlands
    Talk: Region Counting Graphs
  • Spring School, 07/03/2005 - 08/03/2005, Eindhoven (TU/e), The Netherlands
  • 2nd Dutch Computational Geometry Day 05, 18/01/2005, Utrecht, The Netherlands
  • CCCG 04, 09/08/2004 - 11/08/2004, Montreal (Concordia), Canada
    Talk: Local Properties of Geometric Graphs
  • Journées de Géométrie Algorithmique 03, Presqu'ile de Giens (INRIA Sophia), France

Teaching

  • INFO-F-309: Administration des Systèmes. Additional informations for students can be found here.