header photo

Christian Scheffer

Dr. rer nat.

In a Nutshell

Currently, I am a faculty member (akad. Rat) at the Department of Computer Science at the Technische Universtät Braunschweig (TU Braunschweig), as a research associate in the Algorithms Group headed by Prof. Dr. Sándor Fekete.

My main research interests are Computational Geometry, Approximation Algorithms, and Graph Algorithms. Take a look at our current video accepted as multimedia contribution to SoCG2018 and illustrating our results of a full paper, also accepted to SoCG2018:
Furthermore, here you can find most of my talks of my conference papers including slides.

I started studying computer science at the Technische Universtät Dortmund (TU Dortmund) where I also obtained my diploma (sehr gut). My diploma thesis was supervised by Prof. Dr. Jan Vahrenhold and was titled Rekonstruktions Algorithmen für zwei-dimensionale Flächen in 3D.

After that, I started working as a research associate at the Algorithmische Grundlagen und Vermittlung der Informatik group headed by Prof. Dr. Jan Vahrenhold at the Technische Universität Dortmund. After moving with the group of Prof. Dr. Jan Vahrenhold to the Westfälische Wilhelms-Universität Münster (WWU Münster), I obtained my Ph.D. from the WWU Münster at the seventh of July in 2014, graded by summa cum Laude and awarded by the Ph.D. award of the WWU Münster 2014.

In November 2014, I changed to the Algorithms group at the TU Braunschweig, headed by Prof. Dr. Sándor Fekete. Currently I am holding a factulty position (Akademischer Rat) in this group.


  • 2010-2014: Ph.D in Computer Science (Dr. rer nat., summa cum laude) at the TU Dortmund (2010-2013) and at the WWU Münster (2013-2014)
  • 2005-2010: Diploma in Computer Science (Dipl.-Inform., sehr gut) at the TU Dortmund

Selected List of Publications

Corresponding to the policy of the community of Computational Geometry, authors are listed in alphabetical order.

  • SoCG 2019: Sándor P. Fekete, Philipp Keldenich, and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. In proceedings of the 35th International Symposium on Computational Geometry, Portland, Oregon, June 18-21, 2019, accepted for publication.
  • SoCG 2018: Erik D. Demaine, Sándor P. Fekete, Henk Meijer, Philipp Keldenich, and Christian Scheffer. Coordinated Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch. In proceedings of the 34th International Symposium on Computational Geometry, Budapest, Hungary, June 11-14, 2018, accepted for publication.
  • DCG: Sándor P. Fekete, Sebastian Morr, and Christian Scheffer. Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density, accepted for publication.
  • SODA 2017: Zachary Abel, Victor Alvarez, Aman Gour, Adam Hesterberg, Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Three Colors Suffice: Conflict-Free Coloring of Planar Graphs. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, January 16-19, 2017, pages 1951–1963.
  • JoCG: Christian Scheffer. Near-linear time medial axis approximation of smooth curves in R^3., 7(1):360-429, 2016.
  • SWAT 2016: Anil Maheshwari, Jörg-Rüdiger-Sack, and Christian Scheffer. Approximating the Integral Fréchet Distance. In 15th Scandinavian Symposium and Workshops on Algorithm Theory, June 22-24, Reykjavik, Iceland, pages 26:1-16-14, 2016.

For a full list, see here.

Other Professional Activities

I have been a reviewer for the following conferences and journals: Algorithmica, CGTA, CVIU, ESA, EuroCG ICALP, ISAAC, JMIV, JoCG, Pattern Recognition, SoCG, STACS, STACS, STOC, SWAT

My Coauthors by Name

Zachary Abel, Victor Alvarez, Aaron T. Becker, Erik D. Demaine, Alexander Dörflinger, Utkarsh Gupta, Sándor P. Fekete, Björn Fiethe, Amin Gheibi, Robert Gmyr, Aman Gour, Adam Hesterberg, Sven von Höveling, Sabrina Hugo, Phillip Keldenich, Matthias Konitzny, Dominik Krupke, Qian Li, Lillian Lin, Anil Maheshwari, Harald Michalik, Joseph S. B. Mitchell, Henk Meijer, Sebastian Morr, Jan-Marc Reinhardt, Christian Rieck, Jörg-Rüdiger Sack, Sahil Shah, Arne Schmidt, Jan Vahrenhold, James Zuber.