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
      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

      • , , , , , und im Druck. „Worst-Case Optimal Squares Packing into Disks.“ In Proceedings of the 37th International Symposium on Computational Geometry (SoCG)
      • , , , und . im Druck. „Particle-Based Assembly Using Precise Global Control.“ In Proceedings of 17th International Symposium on Algorithms and Data Structures (WADS)

      Forschungsartikel (Zeitschriften)
      • , , , , , und . im Druck. „CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata.“ Algorithmica, Nr. 2020
      Forschungsartikel in Sammelbänden (Konferenzen)
      published
      • , , , , , , und . . „Hard Instances of the Minimum-Weight Triangulation Problem.“ In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG)
      • , , , und . . „Connected Coordinated Motion Planning.“ In Proceedings of the 36th European Workshop on Computational Geometry (Euro{CG})
      • , , , , , und . . „Packing Squares into a Disk with Optimal Worst-Case Density.“ In Proceedings of the 36th European Workshop on Computational Geometry (EuroCG)
      • . . „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.
      • , , , , , , , , , und . . „Recognition and Reconfiguration of Lattice-Based Cellular Structures by Simple Robots.“ In Proceedings of the International Conference on Robotics and Automation (ICRA)
      • , , , , und . . „Worst-Case Optimal Covering of Rectangles by Disks.“ In Proceedings of the 36th International Symposium on Computational Geometry (SoCG)
      • , , , , , , , , , , , , , und . . „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)
      • . im Druck. „Scheduling Three Trains is NP-Complete.“ Beitrag präsentiert auf der The 32nd Canadian Conference on Computational Geometry, Saskatoon, Saskatchewan, Canada
      • , , , und . 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
      • , , und . im Druck. „Covering Rectangles by Disks: The Video.“ In Proceedings of the 36th International Symposium on Computational Geometry (SoCG)

      Artikel
      Forschungsartikel (Zeitschriften)
      • , , und . . „Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density.“ Discrete & Computational Geometry, Nr. 61 (3): 562–594. doi: 10.1007/s00454-018-0020-2.
      • , , , , und . . „Coordinated Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch.“ SIAM Journal on Computing, Nr. 48 (6): 1727–1762. doi: 10.1137/18M1194341.
      Forschungsartikel in Sammelbänden (Konferenzen)
      • , , und . . „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.
      • . . „The Prefix Fréchet Similarity.“ In Proceedings of the 13th International Conference and Workshops on Algorithms and Computation (WALCOM)
      • , , , und . . „Packing Geometric Objects with Optimal Worst-Case Density.“ In Proceedings of the 35th International Symposium on Computational Geometry, (SoCG)
      • , , und . . „Packing Disks into Disks with Optimal Worst-Case Density.“ In Proceedings of the 35th International Symposium on Computational Geometry (SoCG)
      Qualifikationsschriften (Dissertationen, Habilitationsschriften)
      • . im Druck. „Continuously Coordinating Geometric Degrees of Freedom: New Aspects and Approaches.“ Habilitationsschrift, Technische Universität Braunschweig.

      Forschungsartikel (Zeitschriften)
      • , , , und . . „Universal Guard Problems.“ Int. J. Comput. Geometry Appl., Nr. 28 (2): 129–160. doi: 10.1142/S0218195918600038.
      • , , und . . „Approximating the Integral Fréchet Distance.“ Comput. Geom., Nr. 70: 13–30.
      • , , , , , , und . . „Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces.“ Algorithmica, Nr. 2018 doi: 10.1007/s00453-018-0483-9.
      • , , , und . . „Path Refinement in Weighted Regions.“ Algorithmica, Nr. 80 (12): 3766–3802. doi: 10.1007/s00453-018-0414-9.
      • , , , , , , , und . . „Conflict-Free Coloring of Graphs.“ SIAM J. Discrete Math., Nr. 32 (4): 2675–2702. doi: 10.1137/17M1146579.
      Forschungsartikel in Sammelbänden (Konferenzen)
      • , , , , , , und . . „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.
      • , , , , und . . „Coordinated Motion Planning: The Video.“ In Proceedings of the 34th International Symposium on Computational Geometry (SoCG)
      • , , , , und . . „Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch.“ In Proceedings of the 34th International Symposium on Computational Geometry, (SoCG)
      • , , , , , und . . „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)
      • , , und . . „An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration.“ Journal of Systems Architecture - Embedded Systems Design, Nr. 75: 15–25.
      • , , , und . . „New Geometric Algorithms for Fully Connected Staged Self-Assembly.“ Theor. Comput. Sci., Nr. 671: 4–18. doi: 10.1016/j.tcs.2016.11.020.
      Forschungsartikel in Sammelbänden (Konferenzen)
      • , , und . . „On the Traveling Salesman Problem in Solid Grid Graphs.“ In Proceedings of the 33rd European Workshop on Computational Geometry (Euro{CG})
      • , , , , , und . . „Resource-Efficient Dynamic Partial Reconfiguration on FPGAs for Space Instruments.“ In Proceedings of NASA/ESA Conference on Adaptive Hardware and Systems (AHS)
      • , , , , , , und . . „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)
      • , , und . . „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.
      • , , , , , , , und . . „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)
      • . . „More Flexible Curve Matching via the Partial Fréchet Similarity.“ Int. J. Comput. Geometry Appl., Nr. 26 (1): 33–52.
      • . . „Near-Linear Time Medial Axis Approximation of Smooth Curves in R^3.“ JoCG, Nr. 7 (1): 360–429.
      Forschungsartikel in Sammelbänden (Konferenzen)
      • , , , und . . „Universal Guards: Guarding All Polygonalizations of a Point Set in the Plane.“ In Proceedings of the fifth Young Researchers Forum ({YRF})
      • , , und . . „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.
      • , , und . . „Approximating the Integral Fréchet Distance.“ In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)
      • , , , und . . „Universal Guard Problems.“ In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC)

      Forschungsartikel (Zeitschriften)
      • , und . . „Subquadratic Medial-Axis Approximation in R^3.“ Journal of Computational Geometry, Nr. 6 (1): 249–287. doi: 10.20382/jocg.v6i1a11.
      Forschungsartikel in Sammelbänden (Konferenzen)
      • , , , und . . „New Geometric Algorithms for Fully Connected Staged Self-Assembly.“ In Proceedings of 21st International Conference on Computing and Molecular Programming (DNA)

      Artikel
      Forschungsartikel (Zeitschriften)
      published
      • , und . . „Approximating Geodesic Distances on 2-Manifolds in R^3: The Weighted Case.“ Computational Geometry: Theory & Applications, Nr. 47 (8): 789–808. doi: 10.1016/j.comgeo.2014.04.003.
      • , und . . „Approximating Geodesic Distances on 2-Manifolds in R^3.“ Computational Geometry: Theory & Applications, Nr. 47 (2): 125–140. doi: 10.1016/j.comgeo.2012.05.001.
      online first
      • , , , , und . . „Similarity of polygonal curves in the presence of outliers.“ Computational Geometry: Theory & Applications, Nr. 47 doi: 10.1016/j.comgeo.2014.01.002.
      Forschungsartikel in Sammelbänden (Konferenzen)
      • , , , und . . „Minimum Backward Fréchet Distance.“ In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
      Qualifikationsschriften (Dissertationen, Habilitationsschriften)
      • . . „Approximation algorithms for geometrical distance problems that are not solvable exactly.“ Dissertationsschrift, Universität Münster.

      • , und . . „Approximating Weighted Geodesic Distances in R^3.“ In Proceedings of the 29th European Workshop on Computational Geometry, herausgegeben von S Fekete.

      • , und . . „Simplified Medial-Axis Approximation with Guarantees.“ In 28th European Workshop on Computational Geometry, Booklet of Abstracts, herausgegeben von W Didimo und G Liotta.
      • , und . . „Simplied Medial-Axis Approximation with Guarantees.“ In Proceedings of the first Young Researchers Forum (YRF)

      • , und . . „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.
      • , und . . „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.