| Sunday, June 7 |
| 13:00 -17:00 |
SoCG 25th anniversary Celebration |
| 17:00 - 20:00 |
Welcome Reception & Registration |
| Monday, June 8 |
| 8:15 - 09:00 |
Registration and Light breakfast |
| 9:00 -10:20 |
Session 1: Jack Snoeyink, session chair |
| 9:00 -9:20 |
Lower Bounds for Weak Epsilon-Nets and Stair-Convexity
Boris Bukh, Jiří Matoušek and Gabriel Nivasch |
| 9:20 -9:40 |
Epsilon Nets and Union Complexity
Kasturi Varadarajan |
| 9:40 -10:00 |
PTAS for Geometric Hitting Set Problems via Local Search
Nabil Hassan Mustafa and Saurabh Ray |
| 10:00 - 10:20 |
Near-Linear Approximation Algorithms for Geometric Hitting Sets
Pankaj K. Agarwal, Esther Ezra and Micha Sharir |
| 10:20 - 10:50 |
Coffee break |
| 10:50-11:50 |
Session 2: John Hershberger, session chair |
| 10:50 - 11:10 |
Coresets for Polytope Distance
Bernd Gärtner and Martin Jaggi
|
| 11:10 - 11:30 |
Kinetic Spanners in Rd
Mohammad Ali Abam and Mark de Berg |
| 11:30 - 11:50 |
Shooting Permanent Rays among Disjoint Polygons in the Plane
Mashhood Ishaque, Bettina Speckmann and Csaba D. Tóth |
| 12:00 - 1:30 |
Lunch |
| 1:30-2:30 |
Session 3: Scot Drysdale, session chair |
| 1:30 - 1:50 |
Computing Hereditary Convex Structures
Bernard Chazelle and Wolfgang Mulzer |
| 1:50 - 2:10 |
Binary Plane Partitions for Disjoint Line Segments
Csaba D.Tóth
|
| 2:10 - 2:30 |
Optimal In-Place Algorithms for 3-d Convex Hulls and 2-d Segment Intersection
Timothy M. Chan and Eric Y. Chen |
| 2:30-3:00 |
Coffee break |
| 3:00-4:20 |
Session 4, Video and Multimedia Presentations: Efi Fogel, session chair |
3:00-4:20 |
An IP Solution to the Art Gallery Problem
Marcelo C. Couto, Pedro J. de Rezende and Cid C. de Souza
Quadrilateral Meshes with Bounded Minimum Angle
Scott Hine, Betul Atalay, Dianna Xu and Suneeta Ramaswami
Animating a Continuous Family of Two-Site Voronoi Diagrams (and a Proof of a Bound on the Number of Regions)
Matthew T. Dickerson and David Eppstein
The Scale Axis Picture Show
Joachim Giesen, Balint Miklos, Mark Pauly and Camille Wormser
Rectangular Cartograms: The Game
Mark de Berg, Fred van Nijnatten, Bettina Speckmann and Kevin Verbeek
Geometric Tomography: A Limited-View Approach for Computed Tomography
Peter B. Noël and Jinhui Xu, Kenneth R. Hoffmann and Jason J. Corso
Straight Skeletons of Three-Dimensional Polyhedra
Gill Barequet and Amir Vaxman
Reconstructing Sharp Features of Triangular Meshes
Joseph S. B. Mitchell and Eli Packer
High Resolution Surface Reconstruction from Overlapping Multiple-Views
Nader Salman and Mariette Yvinec |
| 4:20 - 4:40 |
Coffee break |
| 4:40-5:40 |
Session 5: Jeff Erickson, session chair |
| 4:40 - 5:00 |
The Scale Axis Transform
Joachim Giesen, Balint Miklos, Mark Pauly and Camille Wormser
|
| 5:00 - 5:20 |
Integral Estimation from Point Cloud in d-Dimensional Space: A Geometric View
Chuanjiang Luo, Jian Sun and Yusu Wang |
| 5:20 - 5:40 |
Cut Locus and Topology from Surface Point Data
Tamal K. Dey and Kuiyu Li |
| 6:00 - 8:00 |
Business meeting |
| Tuesday, June 9 |
| 8:30 - 09:00 |
Light breakfast |
| 9:00 -10:20 |
Session 6: Carola Wenk, session chair |
| 9:00 -9:20 |
An Improved Bound on the Number of Unit Area Triangles
Roel Apfelbaum and Micha Sharir |
| 9:20 -9:40 |
Halving Lines and Measure Concentration in the Plane
Rom Pinchasi |
| 9:40 -10:00 |
Candle in the Woods: Asymptotic Bounds on Minimum Blocking Sets
Nataša Jovanovič, Jan Korst, Ramon Clout, Verus Pronk and Ludo Tolhuizen |
| 10:00 - 10:20 |
Approximate Center Points with Proofs
Gary L. Miller and Donald R. Sheehy |
| 10:20 - 10:50 |
Coffee break |
| 10:50-12:00 |
Invited Talk: Robert Lang |
| 10:50 - 12:00 |
Computational Origami: From Flapping Birds to Space Telescopes
Robert J. Lang |
| 12:00 - 1:30 |
Lunch |
| 1:30-2:30 |
Session 7: Dan Halperin, session chair |
| 1:30 - 1:50 |
Visibility Maps of Realistic Terrains Have Linear Smoothed Complexity
Mark de Berg, Herman Haverkort and Constantinos P.Tsirogiannis
|
| 1:50 - 2:10 |
Embedding Rivers in Polyhedral Terrains
Marc van Kreveld and Rodrigo I. Silveira |
| 2:10 - 2:30 |
The Euclidean Degree-4 Minimum Spanning Tree Problem is NP-hard
Andrea Francke and Michael Hoffmann |
| 2:30-3:00 |
Coffee break |
| 3:00-4:20 |
Session 8: Scot Drysdale, session chair |
| 3:00 -3:20 |
Divide-and-Conquer for Voronoi Diagrams Revisited
Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Thomas Hackl, Bert Jüettler, Elisabeth Pilgerstorfer and Margot Rabl |
| 3:20 -3:40 |
The Geodesic Farthest-Site Voronoi Diagram in a Polygonal Domain with Holes
Sang Won Bae and Kyung-Yong Chwa |
| 3:40 -4:00 |
Incremental Construction of the Delaunay Triangulation and the Delaunay Graph in Medium Dimension
Jean-Daniel Boissonnat, Olivier Devillers and Samuel Hornus |
| 4:00 - 4:20 |
Parallel Geometric Algorithms for Multi-Core Computers
Vicente H. F. Batista, David L. Millman, Sylvain Pion and Johannes Singler |
| 4:20-4:40 |
Coffee break |
| 4:40-5:40 |
Session 9: Mariette Yvinec, session chair |
| 4:40 - 5:00 |
Persistent Cohomology and Circular Coordinates
Vin de Silva and Mikael Vejdemo-Johansson |
| 5:00 - 5:20 |
Proximity of Persistence Modules and Their Diagrams
Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J. Guibas and Steve Y. Oudot |
| 5:20 - 5:40 |
Zigzag Persistent Homology and Real-valued Functions
Gunnar Carlsson, Vin de Silva and Dmitriy Morozov |
| 6:00 |
Conference Banquet |
| Wednesday, June 10 |
| 8:30 - 09:00 |
Light breakfast |
| 9:00 -10:20 |
Session 10: Stefan Funke, session chair |
| 9:00 -9:20 |
Distributed Vision with Smart Pixels
Sándor P. Fekete, Dietmar Fey, Marcus Komann, Alexander Kröeller, Marc Reichenbach and Christiane Schmidt |
| 9:20 -9:40 |
Area-Universal Rectangular Layouts
David Eppstein, Elena Mumford, Bettina Speckmann and Kevin Verbeek |
| 9:40 -10:00 |
Cache-Oblivious Range Reporting With Optimal Queries Requires Superlinear Space
Peyman Afshani, Chris Hamilton and Norbert Zeh |
| 10:00 - 10:20 |
A General Approach for Cache-Oblivious Range Reporting and Approximate Range Counting
Peyman Afshani, Chris Hamilton and Norbert Zeh |
| 10:20 - 10:50 |
Coffee break |
| 10:50-11:50 |
Session 11: Jack Snoeyink, session chair |
| 10:50 - 11:10 |
A Proof of the Molecular Conjecture
Naoki Katoh and Shin-ichi Tanigawa
|
| 11:10 - 11:30 |
Flattening Single-vertex Origami: The Non-Expansive Case
Gaiane Panina and Ileana Streinu |
| 11:30 - 11:50 |
Arrangements of Double Pseudolines
Luc Habert and Michel Pocchiola |
| 12:00 - 1:30 |
Lunch |
| 1:30-2:30 |
Session 12: J. Mark Keil, session chair |
| 1:30 - 1:50 |
k-means Requires Exponentially Many Iterations Even in the Plane
Andrea Vattani
|
| 1:50 - 2:10 |
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
Timothy M. Chan and Sariel Har-Peled |
| 2:10 - 2:30 |
On the Set Multi-Cover Problem in Geometric Settings
Chandra Chekuri, Ken L. Clarkson and Sariel Har-Peled |
| 2:30-3:00 |
Coffee break |
| 3:00-4:20 |
Session 13: Afra Zomorodian, session chair |
| 3:00 -3:20 |
Adaptive Isotopic Approximation of Nonsingular Curves: The Parametrizability and Nonlocal Isotopy Approach
Long Lin and Chee K. Yap
|
| 3:20 -3:40 |
On the Topology of Planar Algebraic Curves
Jinsan Cheng, Sylvain Lazard, Luis Peñaranda, Marc Pouget, Fabrice Rouillier and Elias Tsigaridas |
| 3:40 -4:00 |
Randomly Removing g Handles at Once
Glencora Borradaile, James R. Lee and Anastasios Sidiropoulos |
| 4:00 - 4:20 |
Minimum Cuts and Shortest Homologous Cycles
Erin W. Chambers, Jeff Erickson and Amir Nayyeri |
| 4:20-4:40 |
Coffee break |
| 4:40-5:40 |
Session 14: Carola Wenk, session chair |
| 4:40 - 5:00 |
Diameter of Polyhedra: Limits of Abstraction
Friedrich Eisenbrand, Nicolai Hähnle and Thomas Rothvoß
|
| 5:00 - 5:20 |
Minimum Manhattan Network is NP-Complete
Francis Y. L. Chin, Zeyu Guo and He Sun |
| 5:20 - 5:40 |
On Grids in Topological Graphs
Eyal Ackerman, Jacob Fox, János Pach and Andrew Suk |
| Thursday Workshop Program, June 11 |
