Program

SUNDAY, MARCH 17:
Reception Haus der Wissenschaft/House of Science 18:00 - 20:00
MONDAY, MARCH 18:
Opening: 9:00-9:15
Fast Forward: 1A, 1B, 2A, 2B 9:15-9:30
Session 1A: Visibility and Guarding 9:40-11:00 1A1 (17) Sándor P. Fekete, Stephan Friedrichs, Alexander Kröller and Christiane Schmidt. Facets for Art Gallery Problems
Chair: Bettina Speckmann 1A2 (21) Adrian Dumitrescu, Joseph Mitchell and Paweł Żyliński. The Minimum Guarding Tree Problem
1A3 (54) Leonidas Palios and Petros Tzimas. Covering Class-3 Orthogonal Polygons with the Minimum Number of r-Stars
1A4 (55) Arash Vaezi and Mohammad Ghodsi. Extending Visibility Polygons by Mirrors to Cover Specific Targets
Session 1B: Topology 9:40-11:00 1B1 (44) Fatma Şengüler-Çiftçi and Gert Vegter. Rotation Minimizing Frames on Monotone-helical Quintics: Approximation and Applications to Modeling Problems
Chair: Christian Knauer 1B2 (45) Birgit Strodthoff and Bert Jüttler. Layered Reeb Graphs of a Spatial Domain
1B3 (52) David Salinas, Dominique Attali and André Lieutier. Collapsing Rips Complexes
1B4 (53) Mimi Tsuruga and Frank H. Lutz. Constructing Complicated Spheres
Coffee Break: 11:00-11:30
Session 2A: Packing and Covering 11:30-12:30 2A1 (15) Peter Brass. Selecting a Small Covering from a Double Covering
Chair: Alejandro López-Ortiz 2A2 (16) Soroush Alamdari, Therese Biedl, Timothy M. Chan, Elyot Grant, Krishnam Raju Jampani, S. Keshav, Anna Lubiw and Vinayak Pathak. Smart-grid Electricity Allocation via Strip Packing with Slicing
2A3 (27) Ning Xu. Packing Identical Simple Polygons of Constant Complexity is NP-hard
Session 2B: Fréchet and Hausdorff 11:30-12:30 2B1 (2) Maike Buchin, Anne Driemel and Bettina Speckmann. Computing the Fréchet Distance with Shortcuts is NP-hard
Chair: Marc van Kreveld 2B2 (49) Helmut Alt and Ludmila Scharf. Parallel Computation of the Hausdorff Sistance between Shapes
2B3 (66) Paul Accisano and Alper Üngör. Hardness Results on Curve/Point Set Matching with Fréchet Distance
Lunch: 12:30-14:00
Session 3: Invited Talk 14:00-15:00 Konrad Polthier. Differential-Based Geometry Modeling
Fast Forward: 4A, 4B 15:00-15:10
Coffee Break: 15:10-15:40
Session 4A: Convexity 15:40-17:00 4A1 (5) Lena Schlipf. New Results on Convex Stabbers
Chair: Marc van Kreveld 4A2 (35) Maarten Löffler and Wolfgang Mulzer. Unions of Onions
4A3 (57) Panos Giannopoulos and Christian Knauer. Finding a Largest Empty Convex Subset in Space is W[1]-hard
4A4 (61) Günter Rote. The Degree of Convexity
Session 4B: Distance Problems 15:40-16:40 4B1 (23) Daniela Maftuleac. Algorithms for Distance Problems in Planar Complexes of Global Nonpositive Curvature
Chair: Bettina Speckmann 4B2 (30) Mikael Nilsson. On the Complexity of Finding Spanner Paths
4B3 (47) Aparna Das, Krzysztof Fleszar, Stephen Kobourov, Joachim Spoerhase, Sankar Veeramoni and Alexander Wolff. Polylogarithmic Approximation for Generalized Minimum Manhattan Networks
Business Meeting: 17:15-18:15
Open House at CS Center, dinner on your own
TUESDAY, MARCH 19:
Session 5: Invited Talk 09:00-10:00 James McLurkin. Distributed Computational Geometry and Multi-Robot Systems: Twins Separated at Birth?
Fast Forward: 6A, 6B, 7A, 7B, 8A, 8B 10:00-10:20
Coffee Break: 10:20-10:50
Session 6A: Representation and Reconstruction 11:10-12:10 6A2 (18) Arthur van Goethem, Herman Haverkort, Wouter Meulemans, Andreas Reimer and Bettina Speckmann. Topologically Safe Curved Schematization
Chair: Ferran Hurtado 6A3 (19) Nieke Aerts and Stefan Felsner. Straight-Line Triangle Representations
6A4 (22) Therese Biedl, Martin Held and Stefan Huber. Reconstructing Polygons from Embedded Straight Skeletons
Session 6B: Higher-Dimensional Problems 10:50-12:10 6B1 (1) Mathijs Wintraecken and Gert Vegter. A Conceptual Take on Invariants of Low-Dimensional Manifolds Found by Integration
6B2 (7) Andrei Asinowski, Gill Barequet, Toufik Mansour and Ron Pinter. Cut Equivalence of d-Dimensional Guillotine Partitions
Chair: Alejandro López-Ortiz 6B3 (12) Christian Scheffer and Jan Vahrenhold. Approximating Weighted Geodesic Distances on 2-Manifolds in R^3
6B4 (59) Ioannis Emiris, Vissarion Fisikopoulos and Bernd Gaertner. Efficient Volume and Edge-Skeleton Computation for Polytopes Given by Oracles
Lunch: 12:10-13:30
Session 7A: Triangulations 13:30-14:30 7A1 (3) Oswin Aichholzer, Wolfgang Mulzer and Alexander Pilz. Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
Chair: Christiane Schmidt 7A2 (38) Martin Fink, Jan-Henrik Haunert, Joachim Spoerhase and Alexander Wolff. Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation
7A3 (51) Wolfgang Mulzer and Paul Seiferth. Computational Aspects of Triangulations with Bounded Dilation
Session 7B: Drawing and Embedding 13:30-14:30 7B1 (6) Stefan Felsner. Exploiting Air Pressure to Map Floorplans on Point Sets
Chair: Ferran Hurtado 7B2 (34) Toru Hasunuma. Book Embeddings of Iterated Subdivided-Line Graphs
7B3 (41) Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta and Fabrizio Montecchiani. Area Requirement of Graph Drawings with Few Crossings per Edge
Coffee Break: 14:30-15:00
Session 8A: Reconfiguration 15:00-16:00 8A1 (14) Ferran Hurtado, Enrique Molina, Suneeta Ramaswami and Vera Sacristan. Distributed Universal Reconguration of 2D Lattice-Based Modular Robots
Chair: Alexander Kröller 8A2 (65) Takashi Horiyama and Wataru Shoji. The Number of Different Unfoldings of Polyhedra
8A3 (68) Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama and Ryuhei Uehara. Computational Complexity of Piano-Hinged Dissections
Session 8B: Combinatorics 15:00-16:00 8B1 (9) Tomoki Aiuchi, Katsuhisa Yamanaka, Takashi Hirayama and Yasuaki Nishitani. Coding Ladder Lotteries
Chair: Maarten Löffler 8B2 (70) Sergey Bereg and Kira Vyatkina. On Counting Triangles, Quadrilaterals and Pentagons in a Point Set
8B3 (36) Panagiotis Cheilaris, Elena Khramtcova and Evanthia Papadopoulou. Randomized Incremental Construction of the Hausdorff Voronoi Diagram of Non-Crossing Clusters
Social Event: 16:00-19:00
Conference Banquet: 19:30-
WEDNESDAY, MARCH 20:
Session 9: Invited Talk 09:00-10:00 Marcus Magnor. Geometry and Images
Fast Forward: 9A, 9B, 10A, 10B, 11A, 11B, 12A, 12B 10:00-10:20
Coffee Break: 10:20-10:50
Session 10A: Clustering 10:50-12:10 10A1 (4) Sergey Bereg, Ferran Hurtado, Mikio Kano, Matias Korman, Dolores Lara, Carlos Seara, Rodrigo Silveira, Jorge Urrutia and Kevin Verbeek. Balanced Partitions of 3-colored Geometric Sets in the Plane
Chair: Maarten Löffler 10A2 (8) Sergio Cabello and Panos Giannopoulos. The Complexity of Separating Points in the Plane
10A3 (42) Mark de Berg, Marcel Roeloffzen and Bettina Speckmann. Kinetic Euclidean 2-centers in the Black-Box Model
10A4 (11) Farhad Shahrokhi. New Representation Results for Planar Graphs
Session 10B: Voronoi and Relatives 10:50-12:10 10B1 (31) Gabriela Majewska and Mirosław Kowaluk. New Sequential and Parallel Algorithms for Computing Beta-spectrum
Chair: Henk Meijer 10B2 (37) Mario Kapl, Franz Aurenhammer and Bert Jüttler. Voronoi Diagrams from Distance Graphs
10B3 (39) Evanthia Papadopoulou and Maksym Zavershynskyi. A Sweepline Algorithm for Higher Order Voronoi Diagrams
10B4 (69) Matthias Henze, Rafel Jaume and Balazs Keszegh. On the Complexity of the Partial Least-Squares Matching Voronoi Diagram
Lunch: 12:10-13:30
Session 11A: Optimal Motion 13:30-14:30 11A1 (28) Rolf Klein, David Kriesel and Elmar Langetepe. A Truly Local Strategy for Ant Robots Cleaning Expanding Domains
Chair: Christiane Schmidt 11A2 (29) Yeganeh Bahoo Torudi, Ali Mohades, Marzieh Eskandari and Mahsa Sorouri. 2-Modem Pursuit-Evasion Problem
11A3 (60) Pegah Kamousi and Subhash Suri. Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
Session 11B: Integer Distance 13:30-14:30 11B1 (10) Sascha Kurz and Valery Mishkin. Large-Volume Open Sets in Normed Spaces without Integral Distances
Chair: Christian Knauer 11B2 (43) Marc van Kreveld, Maarten Löffler and Frank Staals. Clear Unit-Distance Graphs
11B3 (50) Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell and Tomas Vyskocil. Extending Partial Representations of Proper and Unit Interval Graphs
Coffee Break: 14:30-15:00
Session 12A: Matching 15:00-16:00 12A1 (56) Tillmann Miltzow. Augmentability of Geometric Matching and Needlework
Chair: Alexander Kröller 12A2 (58) Andrei Asinowski, Tillmann Miltzow and Günter Rote. Quasi-Parallel Segments and Characterization of Unique Bichromatic Matchings
12A3 (64) Stefan Funke and Sabine Storandt. Hierarchical Flows with an Application to Image Matching
Session 12B: Labeling 15:00-16:00 12B1 (25) Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz and Alexander Wolff. Two-Sided Boundary Labeling with Adjacent Sides
Chair: Bettina Speckmann 12B2 (48) Andreas Gemsa, Benjamin Niedermann and Martin Nöllenburg. Trajectory-Based Dynamic Map Labeling
12B3 (62) Kevin Buchin and Dirk H.P. Gerrits. Dynamic Point Labeling is Strongly PSPACE-hard
Closing Remarks

Accepted Papers:

Mathijs Wintraecken and Gert Vegter. A conceptual take on invariants of low-dimensional manifolds found by integration
Maike Buchin, Anne Driemel and Bettina Speckmann. Computing the Fréchet Distance with Shortcuts Is NP-hard
Oswin Aichholzer, Wolfgang Mulzer and Alexander Pilz. Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
Sergey Bereg, Ferran Hurtado, Mikio Kano, Matias Korman, Dolores Lara, Carlos Seara, Rodrigo Silveira, Jorge Urrutia and Kevin Verbeek. Balanced partitions of 3-colored geometric sets in the plane
Lena Schlipf. New Results on Convex Stabbers
Stefan Felsner. Exploiting Air-Pressure to Map Floorplans on Point Sets
Andrei Asinowski, Gill Barequet, Toufik Mansour and Ron Pinter. Cut Equivalence of d-Dimensional Guillotine Partitions
Sergio Cabello and Panos Giannopoulos. The Complexity of Separating Points in the Plane
Tomoki Aiuchi, Katsuhisa Yamanaka, Takashi Hirayama and Yasuaki Nishitani. Coding Ladder Lotteries
Sascha Kurz and Valery Mishkin. Large-Volume Open Sets in Normed Spaces without Integral Distances
Farhad Shahrokhi. New  representation  results for   planar  graphs
Christian Scheffer and Jan Vahrenhold. Approximating Weighted Geodesic Distances on 2-Manifolds in R^3
Ferran Hurtado, Enrique Molina, Suneeta Ramaswami and Vera Sacristan. Distributed universal reconguration of 2D lattice-based modular robots
Peter Brass. Selecting a small covering from a double covering
Soroush Alamdari, Therese Biedl, Timothy M. Chan, Elyot Grant, Krishnam Raju Jampani, S. Keshav, Anna Lubiw and Vinayak Pathak. Smart-grid Electricity Allocation via Strip Packing with Slicing
Arthur van Goethem, Herman Haverkort, Wouter Meulemans, Andreas Reimer and Bettina Speckmann. Topologically Safe Curved Schematization
Nieke Aerts and Stefan Felsner. Straight Line Triangle Representations
Adrian Dumitrescu, Joseph Mitchell and Pawe¿ ¿yli¿ski. The Minimum Guarding Tree Problem
Therese Biedl, Martin Held and Stefan Huber. Reconstructing Polygons from Embedded Straight Skeletons
Daniela Maftuleac. Algorithms for Distance Problems in Planar Complexes of Global Nonpositive Curvature
Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz and Alexander Wolff. Two-Sided Boundary Labeling with Adjacent Sides
Ning Xu. Packing Identical Simple Polygons of Constant Complexity is NP-hard
Rolf Klein, David Kriesel and Elmar Langetepe. A Truly Local Strategy for Ant Robots Cleaning Expanding Domains
Yeganeh Bahoo Torudi, Ali Mohades, Marzieh Eskandari and Mahsa Sorouri. 2-modem Pursuit-Evasion Problem
Mikael Nilsson. On the Complexity of Finding Spanner Paths
Gabriela Majewska and Miros¿aw Kowaluk. New sequential and parallel algorithms for computing beta-spectrum
Toru Hasunuma. Book-Embeddings of Iterated Subdivided-Line Graphs
Maarten Löffler and Wolfgang Mulzer. Unions of Onions
Panagiotis Cheilaris, Elena Khramtcova and Evanthia Papadopoulou. Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters
Mario Kapl, Franz Aurenhammer and Bert Jüttler. Voronoi Diagrams from Distance Graphs
Martin Fink, Jan-Henrik Haunert, Joachim Spoerhase and Alexander Wolff. Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation
Evanthia Papadopoulou and Maksym Zavershynskyi. A Sweepline Algorithm for Higher Order Voronoi Diagrams
Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta and Fabrizio Montecchiani. Area Requirement of Graph Drawings with Few Crossings per Edge
Mark de Berg, Marcel Roeloffzen and Bettina Speckmann. Kinetic Euclidean 2-centers in the Black-Box Model
Marc van Kreveld, Maarten Löffler and Frank Staals. Clear Unit-Distance Graphs
Fatma Șengüler-Çiftçi and Gert Vegter. Rotation minimizing frames on monotone-helical quintics: approximation and applications to modeling problems
Birgit Strodthoff and Bert Jüttler. Layered Reeb Graphs of a Spatial Domain
Aparna Das, Krzysztof Fleszar, Stephen Kobourov, Joachim Spoerhase, Sankar Veeramoni and Alexander Wolff. Polylogarithmic Approximation for Generalized Minimum Manhattan Networks
Andreas Gemsa, Benjamin Niedermann and Martin Nöllenburg. Trajectory-Based Dynamic Map Labeling
Helmut Alt and Ludmila Scharf. Parallel Computation of the Hausdorff Distance Between Shapes
Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell and Tomáš Vyskočil. Extending partial representations of proper and unit interval graphs
Wolfgang Mulzer and Paul Seiferth. Computational Aspects of Triangulations with Bounded Dilation
David Salinas, Dominique Attali and André Lieutier. Collapsing Rips Complexes
Mimi Tsuruga and Frank H. Lutz. Constructing Complicated Spheres
Leonidas Palios and Petros Tzimas. Covering Class-3 Orthogonal Polygons with the Minimum Number of $r$-Stars
Arash Vaezi and Mohammad Ghodsi. Extending Visibility Polygons by Mirrors to Cover Specific Targets
Tillmann Miltzow. Augmentability of Geometric Matching and Needlework
Panos Giannopoulos and Christian Knauer. Finding a largest empty convex subset in space is W[1]-hard
Andrei Asinowski, Tillmann Miltzow and Günter Rote. Quasi-Parallel Segments and Characterization of Unique Bichromatic Matchings
Ioannis Emiris, Vissarion Fisikopoulos and Bernd Gaertner. Efficient volume and edge-skeleton computation for polytopes given by oracles
Pegah Kamousi and Subhash Suri. Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
Günter Rote. The Degree of Convexity
Kevin Buchin and Dirk H.P. Gerrits. Dynamic point labeling is strongly PSPACE-hard
Hao-Hsiang Hung. Improved Time Complexity of Bandwidth Approximation in Dense Graphs
Stefan Funke and Sabine Storandt. Hierarchical Flows with an Application to Image Matching
Takashi Horiyama and Wataru Shoji. The Number of Different Unfoldings of Polyhedra
Paul Accisano and Alper Üngör. Hardness Results on Curve/Point Set Matching with Fréchet Distance
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama and Ryuhei Uehara. Computational Complexity of Piano-Hinged Dissections
Matthias Henze, Rafel Jaume and Balazs Keszegh. On the complexity of the partial least-squares matching Voronoi diagram
Sergey Bereg and Kira Vyatkina. On Counting Triangles, Quadrilaterals and Pentagons in a Point Set