Doctoral AbstractThesis
Approximation Algorithms for Geometrical Distance Problems that are not Solvable Exactly
- Supervisor
- Prof. Dr. Jan Vahrenhold
- Doctoral Subject
- Informatik
- Doctoral Degree
- Dr. rer. nat.
- Awarded by
- Department 10 – Mathematics and Computer Science
CV
Academic 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
Publications
- Fekete, S.P., Juneja, K., Keldenich, P., Kleist, L., Krishna, V., and Scheffer, C. in Kürze. “Worst-Case Optimal Squares Packing into Disks.” in Proceedings of the 37th International Symposium on Computational Geometry (SoCG)
- Jakob, Keller, Christian, Rieck, Christian, Scheffer, and Arne, Schmidt. in Kürze. “Particle-Based Assembly Using Precise Global Control.” in Proceedings of 17th International Symposium on Algorithms and Data Structures (WADS)
Research Article (Journal)
- Fekete, S, Gmyr, R, Hugo, S, Keldenich, P, Scheffer, C, and Schmidt, A. in Kürze. “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, and 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, and Scheffer, C. . “Connected Coordinated Motion Planning.” in Proceedings of the 36th European Workshop on Computational Geometry (Euro{CG})
- Fekete, SP, Gurunathan, V, Juneja, K, Keldenich, P, Kleist, L, and 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, AT, Biediger, DE, Cheung, KC, Fekete, SP, Jenett, B, Niehs, E, Scheffer, C, Schmidt, A, and 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, SP, Gupta, U, Keldenich, P, Scheffer, C, and 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, AT, Biediger, DE, Cheung, K, Fekete, SP, Gershenfeld, N, Hugo, S, Jenett, B, Keldenich, P, Niehs, E, Rieck, C, Schmidt, A, Scheffer, C, and 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, SP, Keldenich, P, and Scheffer, C. in Kürze. “Covering Rectangles by Disks: The Video.” in Proceedings of the 36th International Symposium on Computational Geometry (SoCG)
- Scheffer, C. in Kürze. “Scheduling Three Trains is NP-Complete.” contribution to the The 32nd Canadian Conference on Computational Geometry, Saskatoon, Saskatchewan, Canada
- Fekete, S, Niehs, E, Scheffer, C, and Schmidt, A. in Kürze. “Connected reconfiguration of lattice-based cellular structures by finite-memory robots.” contribution to the 16th International Symposium on Algorithms for Sensor Systems and Experiments for Wireless Sensor Networks (ALGOSENSORS), Pisa, Italy
Articles
Research Articles (Journals)
- Fekete, SP, Morr, S, and Scheffer, C. . “Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density.” Discrete & Computational Geometry 61 (3): 562–594. doi: 10.1007/s00454-018-0020-2.
- Demaine, ED, Fekete, SP, Keldenich, P, Meijer, H, and Scheffer, C. . “Coordinated Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch.” SIAM Journal on Computing 48 (6): 1727–1762. doi: 10.1137/18M1194341.
Research Articles in Edited Proceedings (Conferences)
- Fekete, SP, Höveling, S, and Scheffer, C. . “Online Circle Packing.” in Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS) 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)
- Becker, AT, Fekete, SP, Keldenich, P, and Scheffer, C. . “Packing Geometric Objects with Optimal Worst-Case Density.” in Proceedings of the 35th International Symposium on Computational Geometry, (SoCG)
- Fekete, SP, Keldenich, P, and Scheffer, C. . “Packing Disks into Disks with Optimal Worst-Case Density.” in Proceedings of the 35th International Symposium on Computational Geometry (SoCG)
AbstractThesis (Doctoral or Postdoctoral)
- Scheffer, C. in Kürze. “Continuously Coordinating Geometric Degrees of Freedom: New Aspects and Approaches.” Habilitation thesis, Technische Universität Braunschweig.
Research Articles (Journals)
- Fekete, SP, Li, Q, Mitchell, JS B, and Scheffer, C. . “Universal Guard Problems.” Int. J. Comput. Geometry Appl. 28 (2): 129–160. doi: 10.1142/S0218195918600038.
- Maheshwari, A, Sack, J, and Scheffer, C. . “Approximating the Integral Fréchet Distance.” Comput. Geom. 70: 13–30.
- Becker, AT, Fekete, SP, Keldenich, P, Krupke, D, Rieck, C, Scheffer, C, and 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, and Scheffer, C. . “Path Refinement in Weighted Regions.” Algorithmica 80 (12): 3766–3802. doi: 10.1007/s00453-018-0414-9.
- Abel, Z, Alvarez, V, Demaine, ED, Fekete, SP, Gour, A, Hesterberg, A, Keldenich, P, and Scheffer, C. . “Conflict-Free Coloring of Graphs.” SIAM J. Discrete Math. 32 (4): 2675–2702. doi: 10.1137/17M1146579.
Research Articles in Edited Proceedings (Conferences)
- Fekete, SP, Höveling, S, Mitchell, JS B, Rieck, C, Scheffer, C, Schmidt, A, and Zuber, JR. . “Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading.” in Proceedings of the 13th Latin American Symposium on Theoretical Informatics (LATIN) doi: 10.1007/978-3-319-77404-6_33.
- Becker, AT, Fekete, SP, Keldenich, P, Lin, L, and Scheffer, C. . “Coordinated Motion Planning: The Video.” in Proceedings of the 34th International Symposium on Computational Geometry (SoCG)
- Demaine, ED, Fekete, SP, Keldenich, P, Scheffer, C, and 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)
- Fekete, SP, Gmyr, R, Hugo, S, Keldenich, P, Scheffer, C, and Schmidt, A. . “Cadbots: Algorithmic aspects of manipulating programmable matter with finite automata.” contribution 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, and Scheffer, C. . “An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration.” Journal of Systems Architecture - Embedded Systems Design 75: 15–25.
- Demaine, ED, Fekete, SP, Scheffer, C, and 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, and Scheffer, C. . “On the Traveling Salesman Problem in Solid Grid Graphs.” in Proceedings of the 33rd European Workshop on Computational Geometry (Euro{CG})
- Dörflinger, A, Fekete, SP, Fiethe, B, Keldenich, P, Michalik, H, and Scheffer, C. . “Resource-Efficient Dynamic Partial Reconfiguration on FPGAs for Space Instruments.” in Proceedings of NASA/ESA Conference on Adaptive Hardware and Systems (AHS)
- Becker, AT, Fekete, SP, Keldenich, P, Krupke, D, Rieck, C, Scheffer, C, and 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)
- Fekete, SP, Morr, S, and 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) doi: 10.1007/978-3-319-62127-2_32.
- Abel, Z, Alvarez, V, Demaine, ED, Fekete, SP, Gour, A, Hesterberg, A, Keldenich, P, and Scheffer, C. . “Three Colors Suffice: Conflict-Free Coloring of Planar Graphs.” in Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA) 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 (1): 33–52.
- Scheffer, C. . “Near-Linear Time Medial Axis Approximation of Smooth Curves in R^3.” JoCG 7 (1): 360–429.
Research Articles in Edited Proceedings (Conferences)
- Fekete, S, Mitchell, JSB, Li, Q, and Scheffer, C. . “Universal Guards: Guarding All Polygonalizations of a Point Set in the Plane.” in Proceedings of the fifth Young Researchers Forum ({YRF})
- Fekete, S, Reinhardt, J, and Scheffer, C. . “An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration.” in Proceedings of 29th International Conference on Architecture of Computing Systems (ARCS) doi: 10.1007/978-3-319-30695-7_23.
- Maheshwari, A, Sack, J, and Scheffer, C. . “Approximating the Integral Fréchet Distance.” in Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)
- Fekete, SP, Li, Q, Mitchell, JSB, and Scheffer, C. . “Universal Guard Problems.” in Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC)
Research Article (Journal)
- Scheffer, Christian, and Vahrenhold, Jan. . “Subquadratic Medial-Axis Approximation in R^3.” Journal of Computational Geometry 6 (1): 249–287. doi: 10.20382/jocg.v6i1a11.
Research Article in Edited Proceeding (Conference)
- Demaine, ED, Fekete, S, Scheffer, C, and Schmidt, A. . “New Geometric Algorithms for Fully Connected Staged Self-Assembly.” in Proceedings of 21st International Conference on Computing and Molecular Programming (DNA)
Articles
Research Articles (Journals)
Published
- Scheffer, Christian, and Vahrenhold, Jan. . “Approximating Geodesic Distances on 2-Manifolds in R^3: The Weighted Case.” Computational Geometry: Theory & Applications 47 (8): 789–808. doi: 10.1016/j.comgeo.2014.04.003.
- Scheffer, Christian, and Vahrenhold, Jan. . “Approximating Geodesic Distances on 2-Manifolds in R^3.” Computational Geometry: Theory & Applications 47 (2): 125–140. doi: 10.1016/j.comgeo.2012.05.001.
Online First
- De Carufel, Jean-Lou, Gheibi, Amin, Maheshwari, Anil, Sack, Jörg-Rüdiger, and Scheffer, Christian. . “Similarity of polygonal curves in the presence of outliers.” Computational Geometry: Theory & Applications 47. doi: 10.1016/j.comgeo.2014.01.002.
Research Article in Edited Proceeding (Conference)
- Gheibi, A, Maheshwari, A, Sack, J, and Scheffer, C. . “Minimum Backward Fréchet Distance.” in Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
AbstractThesis (Doctoral or Postdoctoral)
- Scheffer, C. . “Approximation algorithms for geometrical distance problems that are not solvable exactly.” Dissertation thesis, Universität Münster.
- Scheffer, C, and Vahrenhold, J. . “Approximating Weighted Geodesic Distances in R^3.” in Proceedings of the 29th European Workshop on Computational Geometry, edited by S Fekete.
- Scheffer, C, and Vahrenhold, J. . “Simplified Medial-Axis Approximation with Guarantees.” in 28th European Workshop on Computational Geometry, Booklet of Abstracts, edited by W Didimo and G Liotta.
- Scheffer, C, and Vahrenhold, J. . “Simplied Medial-Axis Approximation with Guarantees.” in Proceedings of the first Young Researchers Forum (YRF)
- Scheffer, C, and 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 M Hoffmann.
- Scheffer, C, and 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 G Aloupis and D Bremner.