Program

Schedule

Download the program

Download the book of abstracts

Tuesday March 29th, 2016
18:30 20:00 Registration at Welcoming Reception
19:00 21:00 Welcoming Reception, Palazzo Congressi, 1st floor, Sala C
 
Wednesday March 30th, 2016
8:00   Registration opens
8:45 9:00 Opening Remarks (Auditorium)
Welcoming address by USI President Prof. Piero Martinoli
9:00 9:55 Invited talk: Dan Halperin, Hard versus Easy in Robot Motion Planning: Closing the Ring (Auditorium)
9:55 10:20 Fast-Forward: 1A, 1B, 2A, 2B (Auditorium)
10:20 10:50 Coffee Break
 
 
Session 1A (Auditorium) Session 1B (Room 253)
Chair: Michael Hofmann Chair: Günter Rote
10:50 11:05 Grouping Time-varying Data for Interactive Exploration
by Arthur van Goethem, Marc Van Kreveld, Maarten Löffler, Frank Staals and Bettina Speckmann
Separability and Convexity of Probabilistic Point Sets
by Martin Fink, John Hershberger, Nirman Kumar and Subhash Suri
11:05 11:20 New Results on Trajectory Grouping under Geodesic Distance
by Maarten Löffler, Frank Staals and Jerome Urhausen
Finding Plurality Points in R^d
by Mark de Berg, Joachim Gudmundsson and Mehran Mehr
11:20 11:35 A Refined Definition for Groups of Moving Entities and its Computation
by Marc Van Kreveld, Maarten Löffler, Frank Staals and Lionov Wiratma
On the space of Minkowski summands of a convex polytope
by Ioannis Emiris, Anna Karasoulou, Eleni Tzanaki and Zafeirakis Zafeirakopoulos
 
11:40 11:55 Fine-Grained Analysis of Problems on Curves
by Kevin Buchin, Maike Buchin, Maximilian Konzack, Wolfgang Mulzer and André Schulz
Approximating the Simplicial Depth in High Dimensions
by Peyman Afshani, Don Sheehy and Yannik Stein
11:55 12:10 Time-Space Trade-offs for Triangulating a Simple Polygon
by Boris Aronov, Matias Korman, Simon Pratt,André van Renssen and Marcel Roeloffzen
Bottleneck Distances and Steiner Trees in the Euclidean d-Space
by Pawel Winter and Stephan S. Lorenzen
12:10 13:30 Lunch (Aula Magna)
 
 
Session 2A (Auditorium) Session 2B (Room 253)
Chair: Giuseppe Liotta Chair: Sándor Fekete
13:30 13:45 An Improved Bound for Orthogeodesic Point Set Embeddings of Trees
by Imre Bárány, Kevin Buchin, Michael Hoffmann and Anita Liebenau
Improved Bounds on the Growth Constant of Polyiamonds
by Gill Barequet and Mira Shalah
13:45 14:00 Planar L-Shaped Point Set Embeddings of Trees
by Oswin Aichholzer, Thomas Hackl and Manfred Scheucher
Colouring Contact Graphs of Squares and Rectilinear Polygons
by Mark de Berg, Aleksandar Markovic and Gerhard Woeginger
14:00 14:15 Drawing trees and triangulations with few geometric primitives
by Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans and André Schulz
Connected Dominating Set in Unit Disk Graphs is W[1]-hard
by Mark de Berg, Hans Bodlaender and Sándor Kisfaludi-Bak
       
14:20 14:35 Strongly Monotone Drawings of Planar Graphs
by Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze and Manfred Scheucher
Flip Distance to a Non-crossing Perfect Matching
by Edouard Bonnet and Tillmann Miltzow
14:35 14:50 1-bend Upward Planar Drawings of SP-digraphs with the Optimal Number of Slopes
by Emilio Di Giacomo, Giuseppe Liotta and Fabrizio Montecchiani
Coloring and L(2,1)-labeling of unit disk intersection graphs
by Konstanty Junosza-Szaniawski, Paweł Rzążewski, Joanna Sokół and Krzysztof Węsek
 
14:55 15:10 Fast-Forward: 3A, 3B (Auditorium)
15:10 15:40 Coffee Break
 
    Session 3A (Auditorium) Session 3B (Room 253)
    Chair: Oswin Aichholzer Chair: Martin Held
15:40 15:55 Approximating Smallest Containers for Packing Three-dimensional Convex Objects
by Helmut Alt and Nadja Scharf
Trash Compaction
by Anika Rounds, Maarten Löffler, Hugo Akitaya and Greg Aloupis
15:55 16:10 Packing Plane Spanning Double Stars into Complete Geometric Graphs
by Patrick Schnider
An Approximation Algorithm for the Two-Watchman Route in a Simple Polygon
by Bengt J. Nilsson and Eli Packer
16:10 16:25 Epsilon-covering is NP-complete
by Tuong Nguyen, Isabelle Sivignon and Dominique Attali
A PTAS for Euclidean Maximum Scatter TSP
by Laszlo Kozma and Tobias Mömke
 
16:30 16:45 On the Separation of a Polyhedron from Its Single-Part Mold
by Dan Halperin and Shahar Shamai
Approximating Multidimensional Subset Sum and the Minkowski Decomposition of Polygons
by Charilaos Tzovas, Anna Karasoulou and Ioannis Emiris
16:45 17:00 Covering points with rotating polygons
by Carlos Alegría-Galicia, David Orden, Leonidas Palios, Carlos Seara and Jorge Urrutia
Fair and Square: Cake-Cutting in Two Dimensions
by Erel Segal-Halevi, Avinatan Hassidim and Yonatan Aumann
17:10 18:10 Business Meeting
 
Thursday March 31st, 2016
8:30   Registration opens  
9:00 9:55 Invited talk: Dorothea Wagner: Route Planning in Transportation - When the Metric Matters (Auditorium)
9:55 10:15 Fast-Forward: 4A, 4B, 5A, 5B (Auditorium)
10:15 10:45 Coffee Break
 
 
Session 4A (Auditorium) Session 4B (Room 253)
Chair: Vera Sacristán Chair: Bengt Nilsson
10:45 11:00 Voronoi Diagrams for Parallel Halflines in 3D
by Franz Aurenhammer, Günter Paulini and Bert Jüttler
Generalized Colorful Linear Programming and Further Applications
by Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles and Yannik Stein
11:00 11:15 Additive Weights for Straight Skeletons
by Martin Held and Peter Palfrader
Random Sampling with Removal
by Bernd Gärtner, Johannes Lengler and May Szedlak
11:15 11:30 Bisector Graphs for Min-/Max-Volume Roofs over Simple Polygons
by Günther Eder, Martin Held and Peter Palfrader
Characterizing the Distortion of Some Simple Euclidean Embeddings
by Jonathan Lenchner, Donald Sheehy and Liu Yang
 
11:35 11:50 Stabbing circles for some sets of Delaunay segments
by Merce Claverol, Elena Khramtcova, Evanthia Papadopoulou, Maria Saumell and Carlos Seara
A New Modular Parametric Search Framework
by Christian Knauer, David Kübel and Fabian Stehn
11:50 12:05 Approximation of a Spherical Tessellation by the Laguerre Voronoi Diagram
by Supanut Chaidee and Kokichi Sugihara
Detecting affine equivalences of planar rational curves
by Michael Hauer and Bert Jüttler
12:05 12:20 One Round Voronoi Game on Grids
by Rebvar Hosseini, Mehdi Khosravian, Mansoor Davoodi and Bahram Sadeghi Bigham
Robustness of Zero Set: Implementation
by Peter Franek, Marek Krčál and Hubert Wagner
12:20 13:30 Lunch (Mensa)
 
 
Session 5A (Auditorium) Session 5B (Room 253)
Chair: Gill Barequet Chair: Rodrigo Silveira
13:30 13:45 Non-crossing Bottleneck Matchings of Points in Convex Position
by Marko Savić and Miloš Stojaković
Dynamic Connectivity for Unit Disk Graphs
by Haim Kaplan, Wolfgang Mulzer, Liam Rodittyand Paul Seiferth
13:45 14:00 Bottleneck Matchings and Hamiltonian Cycles in Higher-Order Gabriel Graphs
by Ahmad Biniaz, Anil Maheshwari and Michiel Smid
On Kinetic Range Spaces and their Applications
by Jean-Lou De Carufel, Matthew Katz, Matias Korman, André van Renssen, Marcel Roeloffzen and Shakhar Smorodinsky
 
14:05
14:45
Open Problem Session (Auditorium)
Chair: Bettina Speckman
 
15:20   Social Event: Excursion to Monte Brè (hiking). Further details will follow.
19:00   Dinner at Restaurant "Vetta Monte Brè"
 
Friday April 1st, 2016
8:30   Registration open  
9:00 9:55 Invited talk: Emo Welzl: From Crossing-Free Graphs on Wheel Sets to Polytopes with Few Vertices (Auditorium)
9:55 10:20 Fast-Forward: 6A, 6B, 7A, 7B (Auditorium)
10:20 10:50 Coffee Break
 
 
Session 6A (Auditorium) Session 6B (Room 253)
Chair: Maria Saumell Chair: Marc Van Kreveld
10:50 11:05 Finding the k-Visibility Region of a Point in a Simple Polygon in the Memory-Constrained Model
by Yeganeh Bahoo, Bahareh Banyassady, Prosenjit K. Bose, Stephane Durocher and Wolfgang Mulzer
Covering Polygons with Rectangles
by Roland Glück
11:05 11:20 Minimal Witness Sets For Art Gallery Problems
by Eyup Serdar Ayaz and Alper Ungor
Two-Dimensional Closest Pair Algorithms in the VAT-Model
by Fabian Dütsch
11:20 11:35 Reconstructing a Unit-Length Orthogonally Convex Polygon from its Visibility Graph
by Nodari Sitchinava and Darren Strash
Computing the maximum overlap of a disk and a piecewise circular domain under translation
by Narcis Coll, Marta Fort and J. Antoni Sellares
 
11:40 11:55 An Approximation Algorithm for the Art Gallery Problem
by Edouard Bonnet and Tillmann Miltzow
Beaconless geocast protocols are interesting, even in 1D
by Joachim Gudmundsson, Irina Kostitsyna,Maarten Löffler, Vera Sacristán and Rodrigo I. Silveira
11:55 12:10 Parameterized Hardness of Art Gallery Problems
by Edouard Bonnet and Tillmann Miltzow
Computing Minimum-Link Separating Polygons in Practice
by Moritz Baum, Thomas Bläsius, Andreas Gemsa,Ignaz Rutter and Franziska Wegner
12:10 12:25 Visibility Testing and Counting for Uncertain Segments
by Mohammadali Abam, Sharareh Alipour, Mohammad Ghodsi and Mohammad Mahdian
Computing Pretropisms for the Cyclic n-Roots Problem
by Jeff Sommars and Jan Verschelde
12:25 13:40 Lunch (Mensa)
 
 
Session 7A (Auditorium) Session 7B (Room 253)
Chair: Wolfgang Mulzer Chair: Birgit Vogtenhuber
13:40 13:55 Computing the Fréchet Distance between Real-Valued Surfaces
by Kevin Buchin, Tim Ophelders and Bettina Speckmann
Ramsey-type theorems for lines in 3-space
by Jean Cardinal, Michael S. Payne and Noam Solomon
13:55 14:10 Discrete Fréchet Distance for Uncertain Points
by Maike Buchin and Stef Sijben
Peeling the Cactus: Subexponential-Time Algorithms for Counting Triangulations
by Dániel Marx and Tillmann Miltzow
14:10 14:25 Mapping polygons to the grid with small Hausdorff and Fréchet distance
by Quirijn W. Bouts, Irina Kostitsyna, Marc Van Kreveld, Wouter Meulemans, Willem Sonke and Kevin Verbeek
Holes in 2-convex point sets
by Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr and Birgit Vogtenhuber
14:25 14:40 Map Simplification with Topology Constraints: Exactly and in Practice
by Stefan Funke, Thomas Mendel, Alexander Miller,Sabine Storandt and Maria Wiebe
 
 
14:40   End of Workshop

 

List of accepted papers

Franz Aurenhammer, Günter Paulini and Bert Jüttler Voronoi Diagrams for Parallel Halflines in 3D
Bernd Gärtner, Johannes Lengler and May Szedlak Random Sampling with Removal
Boris Aronov, Matias Korman, Simon Pratt,André van Renssen and Marcel Roeloffzen Time-Space Trade-offs for Triangulating a Simple Polygon
Jean-Lou De Carufel, Matthew Katz, Matias Korman, André van Renssen, Marcel Roeloffzen and Shakhar Smorodinsky On Kinetic Range Spaces and their Applications
Roland Glück Covering Polygons with Rectangles
Erel Segal-Halevi, Avinatan Hassidim and Yonatan Aumann Fair and Square: Cake-Cutting in Two Dimensions
Martin Fink, John Hershberger, Nirman Kumar and Subhash Suri Separability and Convexity of Probabilistic Point Sets
Mark de Berg, Joachim Gudmundsson and Mehran Mehr Finding Plurality Points in R^d
Jean Cardinal, Michael S. Payne and Noam Solomon Ramsey-type theorems for lines in 3-space
Laszlo Kozma and Tobias Mömke A PTAS for Euclidean Maximum Scatter TSP
Fabian Dütsch Two-Dimensional Closest Pair Algorithms in the VAT-Model
Ahmad Biniaz, Anil Maheshwari and Michiel Smid Bottleneck Matchings and Hamiltonian Cycles in Higher-Order Gabriel Graphs
Gill Barequet and Mira Shalah Improved Bounds on the Growth Constant of Polyiamonds
Bengt J. Nilsson and Eli Packer An Approximation Algorithm for the Two-Watchman Route in a Simple Polygon
Supanut Chaidee and Kokichi Sugihara Approximation of a Spherical Tessellation by the Laguerre Voronoi Diagram
Mark de Berg, Hans Bodlaender and Sándor Kisfaludi-Bak Connected Dominating Set in Unit Disk Graphs is W[1]-hard
Patrick Schnider Packing Plane Spanning Double Stars into Complete Geometric Graphs
Michael Hauer and Bert Jüttler Detecting affine equivalences of planar rational curves
Mark de Berg, Aleksandar Markovic and Gerhard Woeginger Colouring Contact Graphs of Squares and Rectilinear Polygons
Oswin Aichholzer, Thomas Hackl and Manfred Scheucher Planar L-Shaped Point Set Embeddings of Trees
Edouard Bonnet and Tillmann Miltzow Flip Distance to a Non-crossing Perfect Matching
Edouard Bonnet and Tillmann Miltzow An Approximation Algorithm for the Art Gallery Problem
Stefan Funke, Thomas Mendel, Alexander Miller,Sabine Storandt and Maria Wiebe Map Simplification with Topology Constraints: Exactly and in Practice
Marko Savić and Miloš Stojaković Non-crossing Bottleneck Matchings of Points in Convex Position
Pawel Winter and Stephan S. Lorenzen Bottleneck Distances and Steiner Trees in the Euclidean d-Space
Peyman Afshani, Don Sheehy and Yannik Stein Approximating the Simplicial Depth in High Dimensions
Nodari Sitchinava and Darren Strash Reconstructing a Unit-Length Orthogonally Convex Polygon from its Visibility Graph
Haim Kaplan, Wolfgang Mulzer, Liam Rodittyand Paul Seiferth Dynamic Connectivity for Unit Disk Graphs
Narcis Coll, Marta Fort and J. Antoni Sellares Computing the maximum overlap of a disk and a piecewise circular domain under translation
Emilio Di Giacomo, Giuseppe Liotta and Fabrizio Montecchiani 1-bend Upward Planar Drawings of SP-digraphs with the Optimal Number of Slopes
Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze and Manfred Scheucher Strongly Monotone Drawings of Planar Graphs
Merce Claverol, Elena Khramtcova, Evanthia Papadopoulou, Maria Saumell and Carlos Seara Stabbing circles for some sets of Delaunay segments
Dan Halperin and Shahar Shamai On the Separation of a Polyhedron from Its Single-Part Mold
Imre Bárány, Kevin Buchin, Michael Hoffmann and Anita Liebenau An Improved Bound for Orthogeodesic Point Set Embeddings of Trees
Günther Eder, Martin Held and Peter Palfrader Bisector Graphs for Min-/Max-Volume Roofs over Simple Polygons
Christian Knauer, David Kübel and Fabian Stehn A New Modular Parametric Search Framework
Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr and Birgit Vogtenhuber Holes in 2-convex point sets
Arthur van Goethem, Marc Van Kreveld, Maarten Löffler, Frank Staals and Bettina Speckmann Grouping Time-varying Data for Interactive Exploration
Gregor Hültenschmidt, Philipp Kindermann, Wouter Meulemans and André Schulz Drawing trees and triangulations with few geometric primitives
Martin Held and Peter Palfrader Additive Weights for Straight Skeletons
Jeff Sommars and Jan Verschelde Computing Pretropisms for the Cyclic n-Roots Problem
Dániel Marx and Tillmann Miltzow Peeling the Cactus: Subexponential-Time Algorithms for Counting Triangulations
Carlos Alegría-Galicia, David Orden, Leonidas Palios, Carlos Seara and Jorge Urrutia Covering points with rotating polygons
Helmut Alt and Nadja Scharf Approximating Smallest Containers for Packing Three-dimensional Convex Objects
Edouard Bonnet and Tillmann Miltzow Parameterized Hardness of Art Gallery Problems
Kevin Buchin, Tim Ophelders and Bettina Speckmann Computing the Fréchet Distance between Real-Valued Surfaces
Eyup Serdar Ayaz and Alper Ungor Minimal Witness Sets For Art Gallery Problems
Tuong Nguyen, Isabelle Sivignon and Dominique Attali Epsilon-covering is NP-complete
Peter Franek, Marek Krčál and Hubert Wagner Robustness of Zero Set: Implementation
Moritz Baum, Thomas Bläsius, Andreas Gemsa,Ignaz Rutter and Franziska Wegner Computing Minimum-Link Separating Polygons in Practice
Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles and Yannik Stein Generalized Colorful Linear Programming and Further Applications
Rebvar Hosseini, Mehdi Khosravian, Mansoor Davoodi and Bahram Sadeghi Bigham One Round Voronoi Game on Grids
Yeganeh Bahoo, Bahareh Banyassady, Prosenjit K. Bose, Stephane Durocher and Wolfgang Mulzer Finding the k-Visibility Region of a Point in a Simple Polygon in the Memory-Constrained Model
Jonathan Lenchner, Donald Sheehy and Liu Yang Characterizing the Distortion of Some Simple Euclidean Embeddings
Mohammadali Abam, Sharareh Alipour, Mohammad Ghodsi and Mohammad Mahdian Visibility Testing and Counting for Uncertain Segments
Marc Van Kreveld, Maarten Löffler, Frank Staals and Lionov Wiratma A Refined Definition for Groups of Moving Entities and its Computation
Kevin Buchin, Maike Buchin, Maximilian Konzack, Wolfgang Mulzer and André Schulz Fine-Grained Analysis of Problems on Curves
Quirijn W. Bouts, Irina Kostitsyna, Marc Van Kreveld, Wouter Meulemans, Willem Sonke and Kevin Verbeek Mapping polygons to the grid with small Hausdorff and Fréchet distance
Maarten Löffler, Frank Staals and Jerome Urhausen New Results on Trajectory Grouping under Geodesic Distance
Konstanty Junosza-Szaniawski, Paweł Rzążewski, Joanna Sokół and Krzysztof Węsek Coloring and L(2,1)-labeling of unit disk intersection graphs
Maike Buchin and Stef Sijben Discrete Fréchet Distance for Uncertain Points
Joachim Gudmundsson, Irina Kostitsyna,Maarten Löffler, Vera Sacristán and Rodrigo I. Silveira Beaconless geocast protocols are interesting, even in 1D
Charilaos Tzovas, Anna Karasoulou and Ioannis Emiris Approximating Multidimensional Subset Sum and the Minkowski Decomposition of Polygons
Ioannis Emiris, Anna Karasoulou, Eleni Tzanaki and Zafeirakis Zafeirakopoulos On the space of Minkowski summands of a convex polytope
Anika Rounds, Maarten Löffler, Hugo Akitaya and Greg Aloupis Trash Compaction