Christian Scheffer

Publications

Corresponding to the policy of the community of Computational Geometry, authors are listed in alphabetical order.

Peer-Reviewed Publications

2020

Christian Scheffer. Train Scheduling Hardness and Algorithms. The 13th International Conference and Workshops on Algorithms and Computation WALCOM 2020, Singapore, March 31 - April 2, 2020, accepted for publication.

2019

Erik D. Demaine, Sándor P. Fekete, Henk Meijer, Philipp Keldenich, and Christian Scheffer. Coordinated Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch. SIAM J. Computing SICOMP, 48(6): 1727-1762.

Sándor P. Fekete, Sebastian Morr, and Christian Scheffer. Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density. Discrete and Computational Geometry DCG, 61(3): 562-594.

Christian Scheffer and Jan Vahrenhold. Approximate Shortest Distances Among Smooth Obstacles in 3D. Journal on Computational Geometry JoCG, accepted for publication.

Sándor P. Fekete, Philipp Keldenich, and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. International Symposium on Computational Geometry, SoCG 2019, Portland, Oregon, June 18-21, 2019, 35:1-35:19.

Aaron T. Becker, Sándor P. Fekete, Philipp Keldenich, Sebastian Morr, and Christian Scheffer. Packing Geometric Objects with Optimal Worst-Case Density. International Symposium on Computational Geometry, SoCG 2019, Portland, Oregon, June 18-21, 2019, 63:1-63:6.

Sándor P. Fekete, Sven von Höveling, and Christian Scheffer. Online Circle Packing. 16th International Symposium on Algorithms and Data Structures WADS 2019, Canada, Edmonton, August 5-7, 2019, 366-379.

Christian Scheffer. The Prefix Fréchet Similarity and its Profile. The 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019, Guwahati, India, February 27 - March 02, 2019, accepted for publication.

Christian Scheffer. Continuously Coordinating Geometric Degrees of Freedom: New Aspects and Approaches. Habilitation thesis. TU Braunschweig.

2018

Zachary Abel, Victor Alvarez, Erik D. Demaine, Sándor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, and Christian Scheffer. Conflict-Free Coloring of Graphs. SIAM J. Discrete Math SIDMA, 32(4): 2675-2702.

Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Path Refinement in Weighted Regions. Algorithmica, 80(12): 3766-3802.

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, Arne Schmidt. Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces Algorithmica, accepted for publication.

Anil Maheswari, Jörg-Rüdiger Sack, and Christian Scheffer. Approximating the Integral Fréchet Distance. Computational Geometry: Theory and Applications Comput. Geom., 70-71: 13-30

Sándor P. Fekete, Joseph S. B. Mitchell, Christian Scheffer, and Qian Li. Universal Guard Problems. International Journal on Computational Geometry and Applications IJCGA, 28(2).

Erik D. Demaine, Sándor P. Fekete, Henk Meijer, Philipp Keldenich, and Christian Scheffer. Coordinated Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch. International Symposium on Computational Geometry, SoCG 2018, Budapest, Hungary, June 11-14, 2018, pages 29:1-29:15.

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin and Christian Scheffer. Coordinated Motion Planning: The Video. International Symposium on Computational Geometry, SoCG 2018, Budapest, Hungary, June 11-14, 2018, 74:1-74:6.

Sándor P. Fekete, Sven von Höveling, Joseph S. B. Mitchell, Christian Scheffer, Christian Rieck, Arne Schmidt, and James Zuber. Don’t Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading. Latin American Theoretical INformatics Symposium LATIN2018, Buenos Aires, Argentina, April 16-19, 2018, pages 448-460.

Sándor P. Fekete, Robert Gmyr, Sabrina Hugo, Phillip Keldenich, Christian Scheffer, and Arne Schmidt. Cadbots: Algorithmic aspects of manipulating programmable matter with finite automata. The 13th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2018, Mérida, Mexico, 9-11 December 2018, 2018, accepted for publication.

2017

Zachary Abel, Victor Alvarez, Aman Gour, Erik D. Demaine, Sándor P. Fekete, Adam Hesterberg, Phillip Keldenich, and Christian Scheffer. Three Colors Suffice: Conflict-Free Coloring of Planar Graphs. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, January 16-19, 2017, pages 1951–1963.

Sándor P. Fekete, Sebastian Morr, and Christian Scheffer. Split Packing: Packing Circles into Triangles with Optimal Worst-Case Density. Proceedings of the 15th Workshop on Algorithms and Datastructures, WADS 2017, St. John’s, Canada, July 31 - August 2, 2017, pages 373–384.

Aeron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Scheffer, and Arne Schmidt. Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces. Proceedins of the 28th International Symposium on Algorithms and Computation ISAAC2017, Phuket, Thailand, December 9-12, 2017, pages 11:1-11:13.

Alexander Dörflinger, Sándor P. Fekete, Björn Fiethe, Phillip Keldenich, Harald Michalik, Christian Scheffer. Resource-Efficient Dynamic Partial Reconfiguration on FPGAs for Space Instruments. 2017 NASA/ESA Conference on Adaptive Hardware and Systems AHS 2017, Pasadena, CA, USA, July 24-27, 2017, pages 24-31.

Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, and Arne Schmidt. New Geometric Algorithms for Fully Connected Staged Self-Assembly. Theoretical Computer Science TCS, 671:4–18, 2017.

Sándor P. Fekete, Jan-Marc Reinhardt, and Christian Scheffer. An Efficient Data Structure for Two-Dimensional Reconfiguration. Journal of Systems Architecture JSA, 75:15–25, 2017.

2016

Christian Scheffer. Near-linear Time Medial Maxis Approximation of Smooth Curves in R^3. Journal on Computational Geometry JoCG, 7(1):360-429, 2016.

Christian Scheffer. More Flexible Curve Matching via the Partial Fréchet Similarity. International Journal on Computational Geometry and Applications IJCGA, 26(1):33-52, 2016

Sándor P. Fekete, Joseph S. B. Mitchell, Christian Scheffer, and Qian Li. Universal Guard Problems. In Algorithms and Computation - 27th International Symposium, ISAAC 2016, Sydney, Australia, December 12-14, 2016, Proceedings.

Christian Scheffer and Jan Vahrenhold. Approximate Shortest Distances Among Smooth Obstacles in 3D. In Algorithms and Computation - 27th International Symposium, ISAAC 2016, Sydney, Australia, December 12-14, 2016, Proceedings

Sándor P. Fekete, Jan-Marc Reinhardt, and Christian Scheffer. An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration. In Architecture of Computing Systems - ARCS 2016 - 29th International Conference, Nuremberg, Germany, April 4-7, 2016, Proceedings, pages 306-318, 2016.

Anil Maheshwari, Jörg-Rüdiger-Sack, and Christian Scheffer. Approximating the Integral Fréchet Distance. In 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, June 22-24, Reykjavik, Iceland, pages 26:1-16-14, 2016.

2015

Erik D. Demaine, Sándor P. Fekete, Christian Scheffer, and Arne Schmidt. New Geometric Algorithms for Fully Connected Staged Self-Assembly. In DNA Computing and Molecular Programming - 21st International Conference, DNA 21, Boston and Cambridge, MA, USA, August 17-21, 2015. Proceedings, pages 104-116, 2015.

Christian Scheffer and Jan Vahrenhold. Subquadratic Medial-Axis Approximation in R^3. Journal on Computational Geometry JoCG, 6(1):249-287, 2015.

2014

Christian Scheffer. Approximation algorithms for geometrical distance problems that are not solvable exactly. PhD thesis, Universität Münster.

Jean-Lou De Carufel, Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Similarity of Polygonal Curves in the Presence of Outliers. Computational Geometry: Theory and Applications CGTA, 47(5):625-641, 2014.

Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Minimum Backward Fréchet Distance. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Dallas/Fort Worth, TX, USA, November 4-7, 2014, pages 381-388, 2014.

Christian Scheffer and Jan Vahrenhold. Approximating Geodesic Distances on 2-Manifolds in R^3: The weighted Case. Computational Geometry: Theory and Applications CGTA, 47(8):789-808, 2014.

Christian Scheffer and Jan Vahrenhold. Approximating Geodesic Distances on 2-Manifolds in R^3. Computational Geometry: Theory and Applications CGTA, 47(2):125-140, 2014.

2011

Christian Scheffer and Jan Vahrenhold. Approximating Geodesic Distances on 2-Manifolds in R^3. In proceedings of the 23rd Annual Cannadian Conference on Computational Geometry, CCCG 2011, Toronto, Ontario, Canada, August 10-12, 2011.

Under Review

Christian Scheffer and Jan Vahrenhold. Learning a 2-Manifold with a Boundary in R^3. International Journal on Computational Geometry and Applications IJCGA

Non Peer-Reviewed Publications

2019

Sándor P. Fekete, Philipp Keldenich, and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. In Proceedings of the 35th European Workshop on Computational Geometry, EuroCG 2019, March 18-20, 2019, Utrecht, Netherlands, pages 49:1-49:8S.

2018

Sándor P. Fekete, Sven von Höveling, Joseph S. B. Mitchell, Christian Scheffer, Christian Rieck, Arne Schmidt, and James Zuber. Don’t Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading. In Proceedings of the 34th European Workshop on Computational Geometry, EuroCG 2018, March 21-23, 2018, Berlin, Germany, pages 18:1-18:6.

2017

Sándor P. Fekete, Christian Rieck, and Christian Scheffer. On the Traveling Salesman Problem in Solid Grid Graphs. In Proceedings of the 33rd European Workshop on Computational Geometry, EuroCG 2017, April 5-7, 2017, Malmö, Sweden, pages 53-56.

Erik D. Demaine, Sándor P. Fekete, Henk Meijer, Philipp Keldenich, and Christian Scheffer. Parallel Motion Planning: Coordinating a Swarm of Labeled Robots with Bounded Stretch. In Proceedings of the 33rd European Workshop on Computational Geometry, EuroCG 2017, April 5-7, 2017, Malmö, Sweden, pages 5-8.

2016

Sándor P. Fekete and Joseph S. B. Mitchell and Qian Li and Christian Scheffer. Universal Guards: Guarding All Polygonalizations of a Point Set in the Plane. In Proceedings of the fifth Computational Geometry: Young Researchers Forum YRF 2016, June 14-18, 2016, Boston, MA, USA, pages 7-8.

2015

Christian Scheffer. Subquadratic Medial-Axis Approximation for Smooth Curves in R^3. In Proceedings of the 31st European Workshop on Computational Geometry, EuroCG 2015, March 15-18, 2015, Ljubljana, Slovenia, pages 101-104.

2013

Christian Scheffer and Jan Vahrenhold. Approximating Weighted Geodesic Distances on 2-Manifolds in R^3. In Proceedings of the 29th European Workshop on Computational Geometry, EuroCG 2013, March 17-20, Braunschweig, Germany, pages 107-110.

2012

Christian Scheffer and Jan Vahrenhold. Simplified Medial-Axis Approximation with Guarantees. In Proceedings of the 28th European Workshop on Computational Geometry, EuroCG 2012, March 19-21, 2012, Assis, Italy, pages 161-164.

Christian Scheffer and Jan Vahrenhold. Simplified Medial-Axis Approximation with Guarantees. In Proceedings of the first Computational Geometry: Young Researchers Forum YRF 2012, June 17-20, 2012, Chapel Hill, NC, USA, pages 9-10.

2011

Christian Scheffer and Jan Vahrenhold. Learning a 2-Manifold with a Boundary in R^3. In Proceedings of the 27th European Workshop on Computational Geometry, EuroCG 211, March 28-30, 2011, Morschach, Switzerland, pages 213-216.