18:00 – 19:00 Welcome reception

08:45 – 09:00

Lecture room P01

official opening and opening remarks

09:00 – 10:00

Lecture room P01

Chair: Andrej Brodnik

Aleš Leonardis: Hierarchical Compositional Representations of Structure for Computer Vision and Robotics

10:00 – 10:30

coffee break

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Marc van Kreveld

Chair: Sándor Fekete

Session 1A

Session 1B

10:30 – 10:50

Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean Lou de Carufel, Matias Korman and Eunjin Oh: A linear-time algorithm for the geodesic center of a simple polygon

Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi and Janos Pach: A lower bound on opaque sets

10:50 – 11:10

Leonidas Palios: Computing the s-kernel of Orthogonal Polygons

2

Wolfgang Mulzer and Yannik Stein: Approximating the Colorful Caratheodory Theorem

11:10 – 11:30

Carlos Alegria Galicia, David Orden, Carlos Seara and Jorge Urrutia: Optimizing an oriented convex hull with two directions

3

Heuna Kim and Tillmann Miltzow: Packing Segments in a Simple Polygon is APX-hard

11:30 – 12:00

coffee break

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Wolfgang Mulzer

Chair: Stefan Felsner

Session 2A

Session 2B

12:00 – 12:20

Mark de Berg and Ali D. Mehrabi: Finding Pairwise Intersections Inside a Query Rectangle

4

Sarah Cannon, Thomas Fai, Justin Iwerks, Undine Leopold and Christiane Schmidt: Combinatorics of edge 2-transmitter art gallery problems

12:20 – 12:40

Mihai-Sorin Stupariu: An algorithm based on local geometry for classifying high density point clouds

5

Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek and Max Willert: Chromatic Guarding of Orthogonal Polygons with Orthogonal Visibility

12:40 – 13:00

Fabian Stehn, Christian Knauer and Luise Sommer: Elastic Shape Matching for Translations under the Manhattan Norm

6

Hamid Hoorfar and Ali Mohades: Special Guards in Chromatic Art Gallery

13:00 – 14:30

lunch

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Maike Buchin

Chair: Leonidas Palios

Session 3A

Session 3B

14:30 – 14:50

Luis Barba, Michael Hoffmann and Vincent Kusters: Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs

7

Akitoshi Kawamura and Makoto Soejima: Simple strategies versus optimal schedules in multi-agent patrolling

14:50 – 15:10

Bernardo Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Thomas Hackl, Jürgen Pammer, Alexander Pilz, Pedro Ramos, Gelasio Salazar and Birgit Vogtenhuber: All Good Drawings of Small Complete Graphs

8

Maximilian Ernestus, Sándor Fekete, Michael Hemmer and Dominik Krupke: Continuous Geometric Algorithms for Robot Swarms with Multiple Leaders

15:10 – 15:30

Toru Hasunuma: A Linear-Time Algorithm for the Queue-Numbers of Proper Triangulated Cacti

9

Azadeh Tabatabaei and Mohammad Ghodsi: Randomized Strategy for Walking in Streets for a Simple Robot‎

15:30 – 16:00

coffee break

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Clemens Huemer

Chair: Maarten Loffler

Session 4A

Session 4B

16:00 – 16:20

Boris Albar, Daniel Gonçalves and Kolja Knauer: Orienting triangulations

10

Erik D. Demaine, Sándor Fekete and Arne Schmidt: New Geometric Algorithms for Staged Self-Assembly

16:20 – 16:40

Monica Blanco and Francisco Santos: Lattice 3-polytopes with six lattice points

11

Bahareh Banyassady, Mansoor Davoodi and Ali Mohades: Caging polygons by a Finger and a Wall

16:40 – 17:00

Gill Barequet and Mira Shalah: Automatic Proofs for Formulae Enumerating Proper Polycubes

12

Christian Scheffer: Subquadratic Medial-Axis Approximation for smooth Curves in R^3

17:00 – 17:20

Colm O Dunlaing: Compact families of Jordan curves and convex hulls in three dimensions

13

Philipp Morgenstern and Daniel Peterseim: Adaptive analysis-suitable T-mesh refinement with linear complexity

09:00 – 10:00

Lecture room P01

Chair: Sergio Cabello

Bojan Mohar: Immersions of graphs and digraphs

10:00 – 10:30

coffee break

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Gill Barequet

Chair: Stefan Funke

Session 5A

Session 5B

10:30 – 10:50

Udo Hoffmann: The Slope Number of Segment Intersection Graphs

14

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Michael Horton and Stef Sijben: Flow Diagrams for Trajectory Analysis

10:50 – 11:10

Boris Klemz, Martin Nöllenburg and Roman Prutkin: Recognizing Weighted Disk Contact Graphs

15

Erin Chambers, Irina Kostitsyna, Maarten Löffler and Frank Staals: Homotopy Measures for Representative Trajectories

11:10 – 11:30

Stefan Felsner, Irina-Mihaela Mustata and Martin Pergel: The Complexity of the Partial Order Dimension Problem - Closing the Gap

16

Marc Van Kreveld, Maarten Löffler and Frank Staals: Central Trajectories

11:30 – 12:00

coffee break

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Oswin Aichholzer

Chair: Sergio Cabello

Session 6A

Session 6B

12:00 – 12:20

Sándor Fekete, Stephan Friedrichs, Michael Hemmer, Melanie Papenberg, Arne Schmidt and Julian Troegel: Area- and Boundary-Optimal Polygonalization of Planar Point Sets

17

Arthur van Goethem, Marc Van Kreveld, Andreas Reimer, Maxim Rylov and Bettina Speckmann: Optimal Straight-line Labels for Island Groups

12:20 – 12:40

Stefan Funke and Sabine Storandt: Pruning Oracles for High-Dimensional Vector Sets

18

Quirijn Bouts and Bettina Speckmann: Clustered Edge Routing

12:40 – 13:00

Toshinori Sakai and Jorge Urrutia: Non-crossing Monotonic Paths in Labeled Point Sets on the Plane.

19

Rafael G. Cano, Kevin Buchin, Thom Castermans, Astrid Pieterse, Willem Sonke and Bettina Speckmann: Mosaic Drawings and Cartograms

13:00 – 14:30

lunch

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Frank Hoffmann

Chair: Kevin Verbeek

Session 7A

Session 7B

14:30 – 14:50

Udo Hoffmann, Linda Kleist and Tillmann Miltzow: Long Paths in Line Arrangements

20

Haim Kaplan, Wolfgang Mulzer, Liam Roditty and Paul Seiferth: Efficient Spanner Construction for Directed Transmission Graphs

14:50 – 15:10

Heuna Kim, Wolfgang Mulzer and Eunjin Oh: The Number of Combinatorially Different Convex Hulls of Points in Lines

21

Prosenjit Bose, Jean-Lou De Carufel and André van Renssen: Constrained Generalized Delaunay Graphs Are Plane Spanners

15:10 – 15:30

Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu and Frank de Zeeuw: Distinct distances between points and lines

22

Stephan Held and Nicolas Kaemmerling: Two-Level Rectilinear Steiner Trees

15:30 – 15:50

Crevel Bautista-Santiago, Javier Cano, Ruy Fabila-Monroy, Carlos Hidalgo Toscano, Clemens Huemer, Jesús Leaños, Toshinori Sakai and Jorge Urrutia: Ramsey numbers for empty convex polygons

23

Sandro Montanari, Matúš Mihalák and Yann Disser: Max Shortest Path for Imprecise Points

16:00 – 17:00

Lecture room P01

business meeting

19:00 – 23:00

conference dinner

09:00 – 10:00

Lecture room P01

Chair: Andrej Brodnik

Kurt Mehlhorn: Computing Real Roots of Real Polynomials and its Application in Computational Geometry

10:00 – 10:30

coffee break

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Matias Korman

Chair: Carlos Seara

Session 8A

Session 8B

10:30 – 10:50

Stefan Funke, Robin Schirrmeister, Simon Skilevic and Sabine Storandt: Fully autonomous Self-Localization via Trajectory Representations based on Inflection Points

24

Omer Gold and Micha Sharir: On the Complexity of the Discrete Fréchet Distance under $L_1$ and $L_\infty$

10:50 – 11:10

Supanut Chaidee and Kokichi Sugihara: A Method for Fitting Real World Tessellations with Voronoi Diagrams

25

Hee-Kap Ahn, Helmut Alt, Maike Buchin, Ludmila Scharf and Carola Wenk: A Middle Curve Based on Discrete Fréchet Distance

11:10 – 11:30

Alon Baram, Efi Fogel, Dan Halperin, Michael Hemmer and Sebastian Morr: Exact Minkowski Sums of Polygons With Holes

26

Kevin Buchin, Tim Ophelders and Bettina Speckmann: Computing the Similarity Between Moving Curves

11:30 – 12:00

coffee break

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Evanthia Papadopoulou

Chair: Bettina Speckmann

Session 9A

Session 9B

12:00 – 12:20

Stephan Friedrichs, Michael Hemmer and Christiane Schmidt: Exact solutions for the continuous 1.5D Terrain Guarding Problem

27

Mark De Berg, Tim Leijssen and Marcel Roeloffzen: Kinetic Conflict Free Coloring

12:20 – 12:40

Andreas Haas and Michael Hemmer: Efficient Algorithms and Implementations for Visibility in 1.5D Terrains

28

Duru Türkoğlu: Kinetic Data Structures for Clipped Voronoi Computations

12:40 – 13:00

Günther Eder, Martin Held and Peter Palfrader: Experiments on Parallel Polygon Triangulation Using Ear Clipping

29

Norbert Bus and Lilian Buzer: Dynamic Convex Hull for Simple Polygonal Chains in Constant Amortized Time per Update

13:00 – 14:30

lunch

Track 1 - Lecture room P19

Track 2 - Lecture room P21

Chair: Michael Hemmer

Chair: Helmut Alt

Session 10A

Session 10B

14:30 – 14:50

Miroslaw Kowaluk and Gabriela Majewska: beta-skeletons for a set of line segments in R^2

30

Matias Korman, Wolfgang Mulzer, Andre van Renssen, Marcel Roeloffzen, Paul Seiferth and Yannik Stein: Time-Space Trade-offs for Voronoi Diagrams

14:50 – 15:10

Domen Mongus and Borut Žalik: Improved single tree-crow extraction from 3D point clouds

31

Elena Khramtcova and Evanthia Papadopoulou: Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures

15:10 – 15:30

Evangelos Anagnostopoulos, Ioannis Emiris and Ioannis Psarros: Low-quality dimension reduction and high-dimensional Approximate Nearest Neighbor

32