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:
A conceptual take on invariants of low-dimensional manifolds found by integration
Computing the Fréchet Distance with Shortcuts Is NP-hard
Flip Distance Between Triangulations of a Simple Polygon is NP-Complete
Balanced partitions of 3-colored geometric sets in the plane
New Results on Convex Stabbers
Exploiting Air-Pressure to Map Floorplans on Point Sets
Cut Equivalence of d-Dimensional Guillotine Partitions
The Complexity of Separating Points in the Plane
Coding Ladder Lotteries
Large-Volume Open Sets in Normed Spaces without Integral Distances
New representation results for planar graphs
Approximating Weighted Geodesic Distances on 2-Manifolds in R^3
Distributed universal reconguration of 2D lattice-based modular robots
Selecting a small covering from a double covering
Smart-grid Electricity Allocation via Strip Packing with Slicing
Facets for Art Gallery Problems
Topologically Safe Curved Schematization
Straight Line Triangle Representations
The Minimum Guarding Tree Problem
Reconstructing Polygons from Embedded Straight Skeletons
Algorithms for Distance Problems in Planar Complexes of Global Nonpositive Curvature
Two-Sided Boundary Labeling with Adjacent Sides
Packing Identical Simple Polygons of Constant Complexity is NP-hard
A Truly Local Strategy for Ant Robots Cleaning Expanding Domains
2-modem Pursuit-Evasion Problem
On the Complexity of Finding Spanner Paths
New sequential and parallel algorithms for computing beta-spectrum
Book-Embeddings of Iterated Subdivided-Line Graphs
Unions of Onions
Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters
Voronoi Diagrams from Distance Graphs
Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation
A Sweepline Algorithm for Higher Order Voronoi Diagrams
Area Requirement of Graph Drawings with Few Crossings per Edge
Kinetic Euclidean 2-centers in the Black-Box Model
Clear Unit-Distance Graphs
Rotation minimizing frames on monotone-helical quintics: approximation and applications to modeling problems
Layered Reeb Graphs of a Spatial Domain
Polylogarithmic Approximation for Generalized Minimum Manhattan Networks
Trajectory-Based Dynamic Map Labeling
Parallel Computation of the Hausdorff Distance Between Shapes
Extending partial representations of proper and unit interval graphs
Computational Aspects of Triangulations with Bounded Dilation
Collapsing Rips Complexes
Constructing Complicated Spheres
Covering Class-3 Orthogonal Polygons with the Minimum Number of $r$-Stars
Extending Visibility Polygons by Mirrors to Cover Specific Targets
Augmentability of Geometric Matching and Needlework
Finding a largest empty convex subset in space is W[1]-hard
Quasi-Parallel Segments and Characterization of Unique Bichromatic Matchings
Efficient volume and edge-skeleton computation for polytopes given by oracles
Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
The Degree of Convexity
Dynamic point labeling is strongly PSPACE-hard
Improved Time Complexity of Bandwidth Approximation in Dense Graphs
Hierarchical Flows with an Application to Image Matching
The Number of Different Unfoldings of Polyhedra
Hardness Results on Curve/Point Set Matching with Fréchet Distance
Computational Complexity of Piano-Hinged Dissections
On the complexity of the partial least-squares matching Voronoi diagram
On Counting Triangles, Quadrilaterals and Pentagons in a Point Set