Prof. Dr. Christian Scheffer

Einsteinstraße 62
48149 Münster

T: +49 (0)251/83-38412

     

    • Doctoral Thesis

      Approximation Algorithms for Geometrical Distance Problems that are not Solvable Exactly

      Betreuer
      Professor Dr. Jan Vahrenhold
      Doctoral Subject
      Informatik
      Doctoral Degree
      Dr. rer. nat.
      Awarded by
      Department 10 – Mathematics and Computer Science

    • CV

      Education

      Diploma Study in Computer Science

      Positions

      Research Assistent at the Department of Computer Science at WWU Münster (Working Group Efficient Algorithms and Algorithm Engineering)
      Research Assistant at TU Dortmund

      Honors

      Dissertation prize of the Faculty of Mathematics/Natural Sciences – University of Münster

    • Teaching

    • Publications

      • S. P. Fekete, K. Juneja, P. Keldenich, L. Kleist, V. Krishna, C. Scheffer. . ‘Worst-Case Optimal Squares Packing into Disks.’ In Proceedings of the 37th International Symposium on Computational Geometry (SoCG).
      • Jakob Keller, Christian Rieck, Christian Scheffer, Arne Schmidt. . ‘Particle-Based Assembly Using Precise Global Control.’ In Proceedings of 17th International Symposium on Algorithms and Data Structures (WADS).

      Research Articles (Journals)
      • Fekete S, Gmyr R, Hugo S, Keldenich P, Scheffer C, Schmidt A. . ‘CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata.’ Algorithmica 2020.
      Research Articles in Edited Proceedings (Conferences)
      published
      • Fekete SP, Haas A, Lieder Y, Niehs E, Perk M, Sack V, Scheffer C. . ‘Hard Instances of the Minimum-Weight Triangulation Problem.’ In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG).
      • Fekete SP, Kosfeld RT, Rieck C, Scheffer C. . ‘Connected Coordinated Motion Planning.’ In Proceedings of the 36th European Workshop on Computational Geometry (Euro{CG}).
      • Fekete S P, Gurunathan V, Juneja K, Keldenich P, Kleist L, Scheffer C. . ‘Packing Squares into a Disk with Optimal Worst-Case Density.’ In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG).
      • Scheffer C. . ‘Train Scheduling: Hardness and Algorithms.’ In Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM). doi: 10.1007/978-3-030-39881-1_30.
      • Abdel-Rahman A, Becker A T, Biediger D E, Cheung K C, Fekete S P, Jenett B, Niehs E, Scheffer C, Schmidt A, Yannuzzi M. . ‘Recognition and Reconfiguration of Lattice-Based Cellular Structures by Simple Robots.’ In Proceedings of the International Conference on Robotics and Automation (ICRA).
      • Fekete S P, Gupta U, Keldenich P, Scheffer C, Shah S. . ‘Worst-Case Optimal Covering of Rectangles by Disks.’ In Proceedings of the 36th International Symposium on Computational Geometry (SoCG).
      • Abdel-Rahman A, Becker A T, Biediger D E, Cheung K, Fekete S P, Gershenfeld N, Hugo S, Jenett B, Keldenich P, Niehs E, Rieck C, Schmidt A, Scheffer C, Yannuzzi M. . ‘Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata.’ In Proceedings of the 36th International Symposium on Computational Geometry (SoCG).
      accepted / in Press (not yet published)
      • Fekete S P, Keldenich P, Scheffer C. . ‘Covering Rectangles by Disks: The Video.’ In Proceedings of the 36th International Symposium on Computational Geometry (SoCG).
      • Scheffer C. . ‘Scheduling Three Trains is NP-Complete.’ Contributed to the The 32nd Canadian Conference on Computational Geometry, Saskatoon, Saskatchewan, Canada.
      • Fekete S, Niehs E, Scheffer C, Schmidt A. . ‘Connected reconfiguration of lattice-based cellular structures by finite-memory robots.’ Contributed to the 16th International Symposium on Algorithms for Sensor Systems and Experiments for Wireless Sensor Networks (ALGOSENSORS), Pisa, Italy.

      Articles
      Research Articles (Journals)
      • Fekete S P, Morr S, Scheffer C. . ‘Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density.’ Discrete & Computational Geometry 61, No. 3: 562–594. doi: 10.1007/s00454-018-0020-2.
      • Demaine ED, Fekete SP, Keldenich P, Meijer H, Scheffer C. . ‘Coordinated Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch.’ SIAM Journal on Computing 48, No. 6: 1727–1762. doi: 10.1137/18M1194341.
      Research Articles in Edited Proceedings (Conferences)
      • Fekete S P, Höveling S, Scheffer C. . ‘Online Circle Packing.’ In Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS), 366–379. doi: 10.1007/978-3-030-24766-9_27.
      • Scheffer C. . ‘The Prefix Fréchet Similarity.’ In Proceedings of the 13th International Conference and Workshops on Algorithms and Computation (WALCOM), 96–107.
      • Becker A T, Fekete S P, Keldenich P, Scheffer C. . ‘Packing Geometric Objects with Optimal Worst-Case Density.’ In Proceedings of the 35th International Symposium on Computational Geometry, (SoCG), 63:1–63:6.
      • Fekete S P, Keldenich P, Scheffer C. . ‘Packing Disks into Disks with Optimal Worst-Case Density.’ In Proceedings of the 35th International Symposium on Computational Geometry (SoCG), 35:1–35:19.
      Theses (Doctoral or Postdoctoral)
      • Scheffer C. . Continuously Coordinating Geometric Degrees of Freedom: New Aspects and Approaches Habilitation thesis, Technische Universität Braunschweig.

      Research Articles (Journals)
      • Fekete S P, Li Q, Mitchell J S B, Scheffer C. . ‘Universal Guard Problems.’ Int. J. Comput. Geometry Appl. 28, No. 2: 129–160. doi: 10.1142/S0218195918600038.
      • Maheshwari A, Sack J, Scheffer C. . ‘Approximating the Integral Fréchet Distance.’ Comput. Geom. 70: 13–30.
      • Becker A T, Fekete S P, Keldenich P, Krupke D, Rieck C, Scheffer C, Schmidt A. . ‘Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces.’ Algorithmica 2018. doi: 10.1007/s00453-018-0483-9.
      • Gheibi A, Maheshwari A, Sack J, Scheffer C. . ‘Path Refinement in Weighted Regions.’ Algorithmica 80, No. 12: 3766–3802. doi: 10.1007/s00453-018-0414-9.
      • Abel Z, Alvarez V, Demaine E D, Fekete S P, Gour A, Hesterberg A, Keldenich P, Scheffer C. . ‘Conflict-Free Coloring of Graphs.’ SIAM J. Discrete Math. 32, No. 4: 2675–2702. doi: 10.1137/17M1146579.
      Research Articles in Edited Proceedings (Conferences)
      • Fekete S P, Höveling S, Mitchell J S B, Rieck C, Scheffer C, Schmidt A, Zuber J R. . ‘Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading.’ In Proceedings of the 13th Latin American Symposium on Theoretical Informatics (LATIN), 448–460. doi: 10.1007/978-3-319-77404-6_33.
      • Becker A T, Fekete S P, Keldenich P, Lin L, Scheffer C. . ‘Coordinated Motion Planning: The Video.’ In Proceedings of the 34th International Symposium on Computational Geometry (SoCG), 74:1–74:5.
      • Demaine E D, Fekete S P, Keldenich P, Scheffer C, Meijer H. . ‘Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch.’ In Proceedings of the 34th International Symposium on Computational Geometry, (SoCG), 29:1–29:15.
      • Fekete S P, Gmyr R, Hugo S, Keldenich P, Scheffer C, Schmidt A. . ‘Cadbots: Algorithmic aspects of manipulating programmable matter with finite automata.’ Contributed to the In Proceedings of the 13th International Workshop on the Algorithmic Foundations of Robotics (WAFR), Mérida, Mexiko.

      Research Articles (Journals)
      • Fekete SP, Reinhardt J, Scheffer C. . ‘An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration.’ Journal of Systems Architecture - Embedded Systems Design 75: 15–25.
      • Demaine E D, Fekete S P, Scheffer C, Schmidt A. . ‘New Geometric Algorithms for Fully Connected Staged Self-Assembly.’ Theor. Comput. Sci. 671: 4–18. doi: 10.1016/j.tcs.2016.11.020.
      Research Articles in Edited Proceedings (Conferences)
      • Fekete SP, Rieck C, Scheffer C. . ‘On the Traveling Salesman Problem in Solid Grid Graphs.’ In Proceedings of the 33rd European Workshop on Computational Geometry (Euro{CG}), 53–56.
      • Dörflinger A, Fekete SP, Fiethe B, Keldenich P, Michalik H, Scheffer C. . ‘Resource-Efficient Dynamic Partial Reconfiguration on FPGAs for Space Instruments.’ In Proceedings of NASA/ESA Conference on Adaptive Hardware and Systems (AHS), 24–31.
      • Becker A T, Fekete S P, Keldenich P, Krupke D, Rieck C, Scheffer C, Schmidt A. . ‘Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces.’ In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC), 11:1–11:13.
      • Fekete S P, Morr S, Scheffer C. . ‘Split Packing: Packing Circles into Triangles with Optimal Worst-Case Density.’ In Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS), 373–384. doi: 10.1007/978-3-319-62127-2_32.
      • Abel Z, Alvarez V, Demaine E D, Fekete S P, Gour A, Hesterberg A, Keldenich P, Scheffer C. . ‘Three Colors Suffice: Conflict-Free Coloring of Planar Graphs.’ In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1951–1963. doi: 10.1137/1.9781611974782.127.

      Research Articles (Journals)
      • Scheffer C. . ‘More Flexible Curve Matching via the Partial Fréchet Similarity.’ Int. J. Comput. Geometry Appl. 26, No. 1: 33–52.
      • Scheffer C. . ‘Near-Linear Time Medial Axis Approximation of Smooth Curves in R^3.’ JoCG 7, No. 1: 360–429.
      Research Articles in Edited Proceedings (Conferences)
      • Fekete S, Mitchell JSB, Li Q, Scheffer C. . ‘Universal Guards: Guarding All Polygonalizations of a Point Set in the Plane.’ In Proceedings of the fifth Young Researchers Forum ({YRF}), 7–8.
      • Fekete S, Reinhardt J, Scheffer C. . ‘An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration.’ In Proceedings of 29th International Conference on Architecture of Computing Systems (ARCS), 306–318. doi: 10.1007/978-3-319-30695-7_23.
      • Maheshwari A, Sack J, Scheffer C. . ‘Approximating the Integral Fréchet Distance.’ In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 26:1–26:14.
      • Fekete SP, Li Q, Mitchell JSB, Scheffer C. . ‘Universal Guard Problems.’ In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), 32:1–32:13.

      Research Articles (Journals)
      • Scheffer C, Vahrenhold J. . ‘Subquadratic Medial-Axis Approximation in R^3.’ Journal of Computational Geometry 6, No. 1: 249–287. doi: 10.20382/jocg.v6i1a11.
      Research Articles in Edited Proceedings (Conferences)
      • Demaine E D, Fekete S, Scheffer C, Schmidt A. . ‘New Geometric Algorithms for Fully Connected Staged Self-Assembly.’ In Proceedings of 21st International Conference on Computing and Molecular Programming (DNA), 104–116.

      Articles
      Research Articles (Journals)
      published
      • Scheffer C, Vahrenhold J. . ‘Approximating Geodesic Distances on 2-Manifolds in R^3: The Weighted Case.’ Computational Geometry: Theory & Applications 47, No. 8: 789–808. doi: 10.1016/j.comgeo.2014.04.003.
      • Scheffer C, Vahrenhold J. . ‘Approximating Geodesic Distances on 2-Manifolds in R^3.’ Computational Geometry: Theory & Applications 47, No. 2: 125–140. doi: 10.1016/j.comgeo.2012.05.001.
      online first
      • Jean-Lou De Carufel, Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, Christian Scheffer. . ‘Similarity of polygonal curves in the presence of outliers.’ Computational Geometry: Theory & Applications 47. doi: 10.1016/j.comgeo.2014.01.002.
      Research Articles in Edited Proceedings (Conferences)
      • Gheibi A, Maheshwari A, Sack J, Scheffer C. . ‘Minimum Backward Fréchet Distance.’ In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 381–388.
      Theses (Doctoral or Postdoctoral)
      • Scheffer C. . Approximation algorithms for geometrical distance problems that are not solvable exactly Dissertation thesis, Universität Münster.

      • Scheffer C, Vahrenhold J. . ‘Approximating Weighted Geodesic Distances in R^3.’ In Proceedings of the 29th European Workshop on Computational Geometry, edited by Fekete, S, 107–110.

      • Scheffer C, Vahrenhold J. . ‘Simplified Medial-Axis Approximation with Guarantees.’ In 28th European Workshop on Computational Geometry, Booklet of Abstracts, edited by Didimo W, Liotta G, 161–164.
      • Scheffer C, Vahrenhold J. . ‘Simplied Medial-Axis Approximation with Guarantees.’ In Proceedings of the first Young Researchers Forum (YRF), 9–10.

      • Scheffer C, Vahrenhold J. . ‘Learning a 2-Manifold with a Boundary in R^3.’ In Abstracts from EuroCG 2011, 27th European Workshop on Computational Geometry, edited by Hoffmann M, 213–216.
      • Scheffer C, Vahrenhold J. . ‘Approximating Geodesic Distances on 2-Manifolds in R^3.’ In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), edited by Aloupis G, Bremner D, 325–330.