Program
| March 18 | March 19 | March 20 | March 21 | Show all | Download as PDF |
Sunday, March 18
18:30-21:00 Welcoming (Hotel Giotto, via Fontebella 41, http://www.hotelgiottoassisi.it/)
Monday, March 19
9:00-9:10 Opening
9:10-10:10 Invited lecture: Olivier Devillers. Delaunay triangulations, theory vs. practice.
10:10-10:20 Fast Forward of Session 1.1
10:20-11:00 Coffee Break
11:00-12:15 Session 1.1
| Session 1.1 - A: Delaunay Graphs | Session 1.1 - B: Graph Drawing - I |
| Mikhail Bogdanov, Monique Teillaud and Gert Vegter. Covering spaces and Delaunay triangulations of the 2D flat torus | Alexander Pilz. Augmentability to Cubic Graphs |
| Okke Schrijvers, Frits van Bommel and Kevin Buchin. Delaunay triangulations on the word RAM: Towards a practical worst-case optimal algorithm | Anna Kwiatkowska and Maciej Syslo. Book Embedding of N-free posets |
| Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh and Steve Oudot. Equating the witness and restricted Delaunay complexes | Toru Hasunuma and Ayane Haruna. A Linear Time Algorithm for the Queue-Numbers of Maximal Outerplanar Graphs |
| Miguel A. Mosteiro. Probabilistic Lower Bounds on the Length of a Longest Edge in Delaunay Graphs of Random Points in a d-Ball | Luca Castelli Aleardi and Eric Fusy. Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings |
| Don Sheehy. Tighter Bounds on the Size of Optimal Meshes | Martin Balko. Grid Representations and the Chromatic Number |
12:15-12:20 Short Break
12:20-12:30 Fast Forward of Session 1.2
12:30-14:00 Lunch Break
14:00-15:15 Session 1.2
| Session 1.2 - A: Computational Models and Complexity Results | Session 1.2 - B: Points, Lines, and Curves |
| Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote and André Schulz. Memory-Constrained Algorithms for Simple Polygons | Ruy Fabila-Monroy, Clemens Huemer and Eulália Tramuns The expected number of points in circles |
| Mark De Berg, Marcel Roeloffzen and Bettina Speckmann. Kinetic Collision Detection for Low-Density Scenes in the Black-Box Model | József Solymosi and Miloš Stojakovič. Many collinear k-tuples with no k+1 collinear points |
| Sylvie Temme and Jan Vahrenhold. Revisiting the Construction of SSPDs in the Presence of Memory Hierarchies | Stefan Huber, Martin Held, Roland Kwitt and Peter Meerwald. Topology-Preserving Watermarking of Vector Data |
| Christian Knauer and Daniel Werner. Erdős-Szekeres is NP-hard in 3 dimensions - and what now? | Kevin Buchin, Maike Buchin, Wouter Meulemans and Bettina Speckmann. Locally Correct Fréchet Matchings |
| Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen and Michiel Smid. Unsolvability of the Weighted Region Shortest Path Problem | Tillmann Miltzow and Alexander Pilz. Selection of Extreme Points and Halving Edges of a Set by its Chirotope |
15:15-15:20 Short Break
15:20-15:30 Fast Forward of Session 1.3
15:30-16:00 Coffee Break
16:00-17:00 Session 1.3
| Session 1.3 - A : Guarding and Art Gallery Problems | Session 1.3 - B : Optimization, Approximation, and Robust Algorithms |
| Prosenjit Bose, Jean Cardinal, Sebastien Collette, Ferran Hurtado, Stefan Langerman, Matias Korman and Perouz Taslakian. Coloring and Guarding Arrangements | Rainer Erbes, Anja Mantel, Elmar Schömer and Nicola Wolpert. Triangle-Triangle Tolerance Tests |
| Alexander Kröller and Christiane Schmidt. Energy-Aware Art Gallery Illumination | Ioannis Emiris, Vissarion Fisikopoulos and Luis Peñaranda. Optimizing the computation of sequences of determinantal predicates |
| Farnoosh Khodakarami, Farzad Didehvar and Ali Mohades. A Fixed Parameter Algorithm for Guarding 1.5D Terrains | Efi Fogel, Michael Hemmer, Asaf Porat and Dan Halperin. Lines Through Segments in Three Dimensional Space |
| Giovanni Viglietta. Partial Searchlight Scheduling is Strongly PSPACE-complete | Manos Kamarianakis and Menelaos I. Karavelas. Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments |
17:00-17:45 Open problems Session
Tuesday, March 20
9:10-10:10 Invited lecture: Jan Kratochvíl. Geometric Intersection Graphs: Old Problems, New Approaches (and Vice Versa).
10:10-10:20 Fast Forward of Session 2.1
10:20-11:00 Coffee Break
11:00-12:15 Session 2.1
| Session 2.1 - A: Triangulations, Skeletons, and Partitions | Session 2.1 - B: Graph Drawing - II |
| Christiane Schmidt. Maxmin Length Triangulation in Polygons | Tamara Mchedlidze. Upward planar embedding of a n-vertex oriented path into O(n2) points |
| Wolfgang Aigner, Franz Aurenhammer and Bert Juettler. On Triangulation Axes of Polygons | Maryam Tahmasbi and Zahra Mazaheri. Aligned Matched Drawability of Some Graph Triples |
| Wolfgang Mulzer and Daniel Werner. A Lower Bound for Shallow Partitions | Kolja Knauer, Piotr Micek and Bartosz Walczak. Outerplanar graph drawings with few slopes |
| Edgardo Roldán-Pensado and Pablo Soberón. An extension of a Theorem of Yao & Yao | Stefan Felsner, Michael Kaufmann and Pavel Valtr. The graphs that can be drawn with one bend per edge |
| Oswin Aichholzer, Howard Cheng, Satyan L. Devadoss, Thomas Hackl, Stefan Huber, Brian Li and Andrej Risteski. What makes a Tree a Straight Skeleton? | Jan Kratochvil and Torsten Ueckerdt. Non-crossing Connectors in the Plane |
12:15-12:20 Short Break
12:20-12:30 Fast Forward of Session 2.2
12:30-14:00 Lunch Break
14:00-15:15 Session 2.2
| Session 2.2 - A: Optimization and Approximation Algorithms | Session 2.2 - B: Efficient and On-line Algorithms |
| Christian Scheffer and Jan Vahrenhold. Simplified Medial-Axis Approximation with Guarantees | Marta Fort and J.Antoni Sellarès. Maximizing k-influence regions |
| Wolfgang Mulzer and Daniel Werner. Approximating Tverberg Points in Linear Time for Any Fixed Dimension | Robert Schieweck and Anita Schöbel. Properties and Algorithms for Line Location with Extensions |
| Asish Mukhopadhyay and Satish Chandra Panigrahi. All-maximum and all-minimum problems under some measures | Julien Rivaud. On the homotopy test on surfaces with boundaries |
| Kevin Verbeek. Homotopic C-oriented Routing | Robert Georges, Frank Hoffmann and Klaus Kriegel. On the Exploration Problem for Polygons with One Hole |
| Ioannis Emiris, Vissarion Fisikopoulos and Christos Konaxis. Exact and approximate algorithms for resultant polytopes | Canek Peláez, Adriana Ramírez-Vigueras, Carlos Seara and Jorge Urrutia. On the Rectilinear Convex Layers of a Planar Set |
15:15-15:20 Short Break
15:20-15:30 Fast Forward of Session 2.3
15:30-16:00 Coffee Break
16:00-17:00 Session 2.3
| Session 2.3 - A: Point Sets and Colors - I | Session 2.3 - B: Proximity and Geometric Graphs |
| Sergey Bereg, José Miguel Díaz-Báñez, Ruy Fabila-Monroy, Pablo Pérez-Lantero, Adriana Ramírez-Vigueras, Thosinori Sakai, Jorge Urrutia and Inmaculada Ventura. On balanced 4-holes in bichromatic point sets | Prosenjit Bose, Vida Dujmovic, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristan, Maria Saumell and David R. Wood. Proximity graphs: E, δ, Δ, χ and ω |
| David Eppstein, Marc van Kreveld, Bettina Speckmann and Frank Staals. One-to-one Point Set Matchings for Grid Map Layout | Luis F. Barba, Ruy Fabila-Monroy, Dolores Lara, Jesús Leaños, Cynthia Rodríguez, Gelasio Salazar and Francisco Zaragoza. The Erdős-Sós Conjecture for Geometric Graphs |
| Jean Cardinal, Nathann Cohen, Sébastien Collette, Michael Hoffmann, Stefan Langerman and Günter Rote. Coloring Dynamic Point Sets on a Line | Miroslaw Kowaluk. Planar β-skeletons via point location in monotone subdivisions of subset of lunes |
| Greg Aloupis, Muriel Dulieu, John Iacono, Stefan Langerman, Ozgur Ozkan, Suneeta Ramaswami and Stefanie Wuhrer. Order type invariant labeling and comparison of point sets | Matthew Bauer and Mirela Damian. Some Sparse Yao Graphs are Spanners |
17:00-17:45 Business Meeting
19:30 Bus for Social Dinner
Wednesday, March 21
9:30-10:30 Invited lecture: Günter Rote. Motion planning for a rigid robot in the plane.
10:30-10:40 Fast Forward of Session 3.1
10:40-11:10 Coffee Break
11:10-12:10 Session 3.1
| Session 3.1 - A: Voronoi Diagrams | Session 3.1 - B: Point Sets and Colors - II |
| Evanthia Papadopoulou and Maksym Zavershynskyi. On the order-k Voronoi diagram of line segments | Victor Alvarez and Atsuhiro Nakamoto. Colored Quadrangulations with Steiner Points |
| Evanthia Papadopoulou and Sandeep Kumar Dey. On the Farthest Line-Segment Voronoi Diagram | Viola Mészáros. Extremal problems in colored point sets in the plane |
| Darius Geiß, Rolf Klein and Rainer Penninger. Optimally solving a general transportation problem using Voronoi diagrams | Birgit Vogtenhuber, Oswin Aichholzer and Ferran Hurtado. Compatible Matchings for Bichromatic Plane Straight-line Graphs |
| Andreas Gemsa, D. T. Lee, Chih-Hung Liu and Dorothea Wagner. Higher Order City Voronoi Diagrams | Sergey Kopeliovich and Kira Vyatkina. On Counting Empty Pseudo-Triangles in a Point Set |
12:10-12:15 Short Break
12:15-12:25 Fast Forward of Session 3.2
12:25-14:00 Lunch Break
14:00-15:00 Session 3.2
| Session 3.2 - A: Tiling, Folding, Piercing, and Gluing | Session 3.2 - B: Zonotopes, Convex Sets, and Mapping |
| Kokichi Sugihara. Computer Generation of Triply-Crossing Tile Patterns | Hiba Abdallah and Quentin Merigot. On the reconstruction of convex sets from random normals measurements |
| Farhad Shahrokhi. New separation theorems and sub-exponential time algorithms for packing and piercing of fat objects | Michal Černý and Miroslav Rada. On Ellipsoidal Approximations of Zonotopes |
| Erik Demaine, Martin Demaine, Jin-Ichi Itoh, Anna Lubiw, Chie Nara and Joseph O'Rourke. Refold Rigidity of Convex Polyhedra | Miroslav Rada and Michal Černý. A Uniform Approach to Enumeration of Facets, Enumeration of Vertices and Computation of Volume of a Zonotope |
| Marc van Kreveld, Maarten Löffler and Janos Pach. How Many Potatoes are in a Mesh? | Richard Klein, Hari K. Voruganti and Michael Sears. Domain Mapping using Harmonic Functions in non-convex domains of genus non-zero |
15:00-15:05 Closing Remarks
