Prof. Dr. Christian Scheffer

Einsteinstraße 62
48149 Münster

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

  • Promotion

    Approximation Algorithms for Geometrical Distance Problems that are not Solvable Exactly

    Betreuer
    Professor Dr. Jan Vahrenhold
    Promotionsfach
    Informatik
    Abschlussgrad
    Dr. rer. nat.
    Verleihender Fachbereich
    Fachbereich 10 – Mathematik und Informatik

  • Vita

    Akademische Ausbildung

    Diplomstudiengang Informatik an der TU Dortmund

    Beruflicher Werdegang

    Wissenschaftlicher Mitarbeiter am Institut für Informatik der WWU Münster (Arbeitsgruppe Effiziente Algorithmen und Algorithm Engineering)
    Wissenschaftlicher Mitarbeiter am Lehrstuhl 11 der Fakultät für Informatik der TU Dortmund

  • Publikationen

    • 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). [akzeptiert / in Druck (unveröffentlicht)]
    • 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). [akzeptiert / in Druck (unveröffentlicht)]
    • 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).
    • Fekete S P, Keldenich P, Scheffer C. . ‘Covering Rectangles by Disks: The Video.’ In Proceedings of the 36th International Symposium on Computational Geometry (SoCG). [akzeptiert / in Druck (unveröffentlicht)]
    • Fekete S, Gmyr R, Hugo S, Keldenich P, Scheffer C, Schmidt A. . ‘CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata.’ Algorithmica 2020. [akzeptiert / in Druck (unveröffentlicht)]
    • Scheffer C. . ‘Scheduling Three Trains is NP-Complete.’ Contributed to the The 32nd Canadian Conference on Computational Geometry, Saskatoon, Saskatchewan, Canada. [akzeptiert / in Druck (unveröffentlicht)]
    • 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. [akzeptiert / in Druck (unveröffentlicht)]
    • Scheffer C. . Continuously Coordinating Geometric Degrees of Freedom: New Aspects and Approaches Habilitationsschrift, Technische Universität Braunschweig. [akzeptiert / in Druck (unveröffentlicht)]
    • Fekete S P, Morr S, Scheffer C. . ‘Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density.’ Discrete & Computational Geometry 61, Nr. 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, Nr. 6: 1727–1762. doi: 10.1137/18M1194341.
    • 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.
    • Fekete S P, Li Q, Mitchell J S B, Scheffer C. . ‘Universal Guard Problems.’ Int. J. Comput. Geometry Appl. 28, Nr. 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, Nr. 12: 3766–3802. doi: 10.1007/s00453-018-0414-9.
    • 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.
    • 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, Nr. 4: 2675–2702. doi: 10.1137/17M1146579.
    • 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.
    • 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.
    • 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.
    • 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.
    • Scheffer C. . ‘More Flexible Curve Matching via the Partial Fréchet Similarity.’ Int. J. Comput. Geometry Appl. 26, Nr. 1: 33–52.
    • Scheffer C. . ‘Near-Linear Time Medial Axis Approximation of Smooth Curves in R^3.’ JoCG 7, Nr. 1: 360–429.
    • Scheffer C, Vahrenhold J. . ‘Subquadratic Medial-Axis Approximation in R^3.’ Journal of Computational Geometry 6, Nr. 1: 249–287. doi: 10.20382/jocg.v6i1a11.
    • 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.
    • Scheffer C, Vahrenhold J. . ‘Approximating Geodesic Distances on 2-Manifolds in R^3: The Weighted Case.’ Computational Geometry: Theory & Applications 47, Nr. 8: 789–808. doi: 10.1016/j.comgeo.2014.04.003.
    • 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. [online first]
    • Scheffer C, Vahrenhold J. . ‘Approximating Geodesic Distances on 2-Manifolds in R^3.’ Computational Geometry: Theory & Applications 47, Nr. 2: 125–140. doi: 10.1016/j.comgeo.2012.05.001.
    • Scheffer C. . Approximation algorithms for geometrical distance problems that are not solvable exactly Dissertationsschrift, Universität Münster.
    • 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.
    • 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.