Nicolas Grelier


I am a PhD student at ETH Zürich, in the Theory of Combinatorial Algorithm Group. My supervisors are Dr. Michael Hoffmann and Prof. Emo Welzl.

I did my master in Brest at IMT Atlantique, where I had the opportunity to work on several research projects under the supervision of Prof. Vincent Gripon. During an academic exchange at Hong Kong University, I had the pleasure to work with Prof. Zhiyi Huang. I completed my end-of-studies internship at Radboud University Nijmegen under the supervision of Prof. Ross J. Kang.


Institute of Theoretical Computer Science Department of Computer Science
ETH Zürich, CAB G19.2
8092 Zürich

Phone: +41 44 632 42 86
E-mail: firstname.lastname{at}

Publications and Manuscripts

  • "Minimum Convex Partition of Point Sets is NP-Hard"

  • "On the VC-dimension of convex sets and half-spaces"
    with Saeed Gh. Ilchi, Tillmann Miltzow and Shakhar Smorodinsky.

  • "Approximate strong edge-colouring of unit disk graphs"
    with Rémi de Joannis de Verclos, Ross J. Kang and François Pirot.
    In WAOA 2019, to appear.
    Preliminary results appeared in Abstracts 35th European Workshop on Computational Geometry (EuroCG '19), Utrecht, Netherlands, 2019 (pdf)

  • "Graph-Projected Signal Processing"
    with Carlos R. K. Lassance, Elsa Dupraz and Vincent Gripon.
    In IEEE GlobalSIP 2018, to appear.

  • "Neighborhood-preserving translations on graphs"
    with Bastien Pasdeloup, Jean-Charles Vialatte and Vincent Gripon.
    In Proceedings of GlobalSIP, pp. 410--414, October 2016.
  • Talks and Poster Sessions

    On the VC-dimension of convex sets and half-spaces, Mittagsseminar, ETH Zürich, Switzerland, September 2019

    Approximate strong edge-colouring of unit disk graphs, Mittagsseminar, ETH Zürich, Switzerland, April 2019

    Approximate strong edge-colouring of unit disk graphs, EuroCG 2019, Utrecht, The Netherlands, March 2019

    Graph-Projected Signal Processing GSP18, EPFL, Switzerland, June 2018

    Neighborhood-preserving translations on graphs GlobalSIP 2016, Washington D.C., USA, December 2016