Promotion
Approximation Algorithms for Geometrical Distance Problems that are not Solvable Exactly
- Betreuer
- Prof. 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
Preise
- Dissertationspreis der Mathematisch-Naturwissenschaftlichen Fakultät – Universität Münster
Publikationen
- Fekete, S.P., Juneja, K., Keldenich, P., Kleist, L., Krishna, V., und Scheffer, C. im Druck. „Worst-Case Optimal Squares Packing into Disks.“ In Proceedings of the 37th International Symposium on Computational Geometry (SoCG)
- Jakob, Keller, Christian, Rieck, Christian, Scheffer, und Arne, Schmidt. im Druck. „Particle-Based Assembly Using Precise Global Control.“ In Proceedings of 17th International Symposium on Algorithms and Data Structures (WADS)
Forschungsartikel (Zeitschrift)
- Fekete, S, Gmyr, R, Hugo, S, Keldenich, P, Scheffer, C, und Schmidt, A. im Druck. „CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata.“ Algorithmica 2020.
Forschungsartikel in Sammelbänden (Konferenzen)
Veröffentlicht
- Fekete, SP, Haas, A, Lieder, Y, Niehs, E, Perk, M, Sack, V, und 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, und 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, und 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, und 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, und 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, und 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, und Scheffer, C. im Druck. „Covering Rectangles by Disks: The Video.“ In Proceedings of the 36th International Symposium on Computational Geometry (SoCG)
- Scheffer, C. im Druck. „Scheduling Three Trains is NP-Complete.“ Beitrag präsentiert auf der The 32nd Canadian Conference on Computational Geometry, Saskatoon, Saskatchewan, Canada
- Fekete, S, Niehs, E, Scheffer, C, und Schmidt, A. im Druck. „Connected reconfiguration of lattice-based cellular structures by finite-memory robots.“ Beitrag präsentiert auf der 16th International Symposium on Algorithms for Sensor Systems and Experiments for Wireless Sensor Networks (ALGOSENSORS), Pisa, Italy
Artikel
Forschungsartikel (Zeitschriften)
- Fekete, SP, Morr, S, und 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, und 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.
Forschungsartikel in Sammelbänden (Konferenzen)
- Fekete, SP, Höveling, S, und 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, und 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, und Scheffer, C. . „Packing Disks into Disks with Optimal Worst-Case Density.“ In Proceedings of the 35th International Symposium on Computational Geometry (SoCG)
Qualifikationsschrift (Dissertation oder Habilitationsschrift)
- Scheffer, C. im Druck. „Continuously Coordinating Geometric Degrees of Freedom: New Aspects and Approaches.“ Habilitationsschrift, Technische Universität Braunschweig.
Forschungsartikel (Zeitschriften)
- Fekete, SP, Li, Q, Mitchell, JS B, und Scheffer, C. . „Universal Guard Problems.“ Int. J. Comput. Geometry Appl. 28 (2): 129–160. doi: 10.1142/S0218195918600038.
- Maheshwari, A, Sack, J, und 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, und 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, und 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, und Scheffer, C. . „Conflict-Free Coloring of Graphs.“ SIAM J. Discrete Math. 32 (4): 2675–2702. doi: 10.1137/17M1146579.
Forschungsartikel in Sammelbänden (Konferenzen)
- Fekete, SP, Höveling, S, Mitchell, JS B, Rieck, C, Scheffer, C, Schmidt, A, und 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, und 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, und 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, und Schmidt, A. . „Cadbots: Algorithmic aspects of manipulating programmable matter with finite automata.“ Beitrag präsentiert auf der In Proceedings of the 13th International Workshop on the Algorithmic Foundations of Robotics (WAFR), Mérida, Mexiko
Forschungsartikel (Zeitschriften)
- Fekete, SP, Reinhardt, J, und 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, und 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.
Forschungsartikel in Sammelbänden (Konferenzen)
- Fekete, SP, Rieck, C, und 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, und 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, und 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, und 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, und 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.
Forschungsartikel (Zeitschriften)
- 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.
Forschungsartikel in Sammelbänden (Konferenzen)
- Fekete, S, Mitchell, JSB, Li, Q, und 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, und 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, und 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, und Scheffer, C. . „Universal Guard Problems.“ In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC)
Forschungsartikel (Zeitschrift)
- Scheffer, Christian, und Vahrenhold, Jan. . „Subquadratic Medial-Axis Approximation in R^3.“ Journal of Computational Geometry 6 (1): 249–287. doi: 10.20382/jocg.v6i1a11.
Forschungsartikel in einem Sammelband (Konferenz)
- Demaine, ED, Fekete, S, Scheffer, C, und Schmidt, A. . „New Geometric Algorithms for Fully Connected Staged Self-Assembly.“ In Proceedings of 21st International Conference on Computing and Molecular Programming (DNA)
Artikel
Forschungsartikel (Zeitschriften)
Veröffentlicht
- Scheffer, Christian, und 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, und 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, und Scheffer, Christian. . „Similarity of polygonal curves in the presence of outliers.“ Computational Geometry: Theory & Applications 47. doi: 10.1016/j.comgeo.2014.01.002.
Forschungsartikel in einem Sammelband (Konferenz)
- Gheibi, A, Maheshwari, A, Sack, J, und Scheffer, C. . „Minimum Backward Fréchet Distance.“ In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
Qualifikationsschrift (Dissertation oder Habilitationsschrift)
- Scheffer, C. . „Approximation algorithms for geometrical distance problems that are not solvable exactly.“ Dissertationsschrift, Universität Münster.
- Scheffer, C, und Vahrenhold, J. . „Approximating Weighted Geodesic Distances in R^3.“ In Proceedings of the 29th European Workshop on Computational Geometry, herausgegeben von S Fekete.
- Scheffer, C, und Vahrenhold, J. . „Simplified Medial-Axis Approximation with Guarantees.“ In 28th European Workshop on Computational Geometry, Booklet of Abstracts, herausgegeben von W Didimo und G Liotta.
- Scheffer, C, und Vahrenhold, J. . „Simplied Medial-Axis Approximation with Guarantees.“ In Proceedings of the first Young Researchers Forum (YRF)
- Scheffer, C, und Vahrenhold, J. . „Learning a 2-Manifold with a Boundary in R^3.“ In Abstracts from EuroCG 2011, 27th European Workshop on Computational Geometry, herausgegeben von M Hoffmann.
- Scheffer, C, und Vahrenhold, J. . „Approximating Geodesic Distances on 2-Manifolds in R^3.“ In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), herausgegeben von G Aloupis und D Bremner.