Except as noted, all presentations will take place in Emerald/Ruby Hall.
* Starred talks were rescheduled after the proceedings went to press; the papers appear out of order in the proceedings.
| Tuesday, June 5 | ||
|---|---|---|
| 6:30 | Welcome Reception: Waterfall Area | |
| Wednesday, June 6 | ||
|---|---|---|
| Session 1A — Suresh Venkatasubramanian | Session 1B (Sapphire Hall) — Helmut Alt | |
| 9:15-9:40 | A PTAS for k-Means Clustering Based on Weak Coresets
Dan Feldman, Morteza Monemizadeh, and Christian Sohler | Guard Placement For Wireless Localization
David Eppstein, Michael T. Goodrich, and Nodari Sitchinava |
| 9:40-10:05 | Constant-Factor Bicriteria Linear-time Approximations for Generalized k-Mean/Median/Center
Dan Feldman, Amos Fiat, and Micha Sharir | Aperture-Angle and Hausdorff-Approximation of Convex Figures
Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, and Mira Lee |
| 10:05-10:30 | Weak ε-nets Have a Basis of Size O(1/ε) in Any Dimension*
Nabil H. Mustafa and Saurabh Ray | Traversing a Set of Points with a Minimum Number of Turns
Sergey Bereg, Prosenjit Bose, Adrian Dumitrescu, Ferran Hurtado, and Pavel Valtr |
| 10:30-11:00 | — Coffee break — | |
| 11:00-12:00 | Invited Talk: A Geometric Perspective on Machine Learning Partha Niyogi (University of Chicago) | |
| 12:00-2:00 | — Lunch — | |
| Session 2 — Jeff Erickson | ||
| 2:00-2:20 | Thick Non-Crossing Paths and Minimum-Cost Flows in Polygonal Domains
Joseph S. B. Mitchell and Valentin Polishchuk | |
| 2:20-2:40 | Finding Bounded-Curvature Paths in Narrow Simply Connected Regions
Jonathan Backer and David Kirkpatrick | |
| 2:40-3:00 | Shortest Paths on Realistic Polyhedra
Yevgeny Schreiber | |
| 3:00-3:20 | Querying Approximate Shortest Paths in Anisotropic Regions
Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang | |
| 3:20-4:00 | — Coffee break — | |
| Session 3 — Ileana Streinu | ||
| 4:00-4:20 | Happy Endings for Flip Graphs
David Eppstein | |
| 4:20-4:40 | Offline Variants of the “Lion and Man” Problem
Adrian Dumitrescu, Ichiro Suzuki, and Pawel Zylinski | |
| 4:40-5:00 | A New Upper Bound for Embedding 3-Polytopes on the Grid
Ares Ribó, Günter Rote, and André Schulz | |
| 5:15-6:30 | — Business meeting: Emerald/Ruby Hall — | |
| Thursday, June 7 | |||
|---|---|---|---|
| Video Session — Monique Teillaud | Session 4 (Sapphire Hall) — Suresh Venkatasubramanian | ||
| 9:00-9:10 | Computing the Exact Arrangement of Circles on a Sphere, with applications in structural biology
Frédéric Cazals and Sébastien Loriot | 9:00-9:25 | Decomposition of Multiple Coverings into Several Parts
János Pach and Géza Tóth |
| 9:10-9:20 | Visualizing Bregman Voronoi Diagrams
Frank Nielsen, Jean-Daniel Boissonnat, and Richard Nock | ||
| 9:20-9:30 | Medial Axis Approximation from Inner Voronoi Balls: A Demo of the Mesecina Tool
Balint Miklos, Joachim Giesen, and Mark Pauly | ||
| 9:25-9:50 | An Optimal Generalization of the Centerpoint Theorem, and its Extensions
Nabil H. Mustafa and Saurabh Ray | ||
| 9:30-9:40 | Inflating the Cube by Shrinking
Kevin Buchin and André Schulz | ||
| 9:40-9:50 | Heilbronn's Triangle Problem
Gill Barequet and Alina Shaikhet | ||
| 9:50-10:00 | Kinetic 3D-Convex Hulls via Self-Adjusting Computation: An Illustration
Umut A. Acar, Guy E. Blelloch, and Kanat Tangwongsan | 9:50-10:15 | There Are Not Too Many Magic Configurations
Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote |
| 10:00-10:10 | Towards an Implementation of the 3D Visibility Skeleton
Linqiao Zhang, Hazel Everett, Sylvain Lazard, and Sue Whitesides | ||
| 10:15-10:40 | — Coffee break — | ||
| Session 5 — John Iacono | |||
| 10:40-11:00 | Quadratic and Cubic B-Splines by Generalizing Higher-Order Voronoi Diagrams
Yuanxin Liu and Jack Snoeyink | ||
| 11:00-11:20 | Snap Rounding of Bézier Curves
Arno Eigenwillig, Lutz Kettner, and Nicola Wolpert | ||
| 11:20-11:40 | Optimal Simplification of Polygonal Chain for Rendering
Lilian Buzer | ||
| 11:40-12:00 | Streaming Algorithms for Line Simplification
Mohammad Ali Abam, Mark de Berg, Peter Hachenberger, and Alireza Zarei | ||
| 12:00-2:00 | — Lunch — | ||
| Session 6 — Jeff Erickson | |||
| 2:00-2:20 | The Theory of Multidimensional Persistence
Gunnar Carlsson and Afra Zomorodian | ||
| 2:20-2:40 | Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes
Jean-Daniel Boissonnat, Leonidas J. Guibas, and Steve Y. Oudot | ||
| 2:40-3:00 | Probabilistic Embeddings of Bounded Genus Graphs Into Planar Graphs
Piotr Indyk and Anastasios Sidiropoulos | ||
| 3:00-3:20 | Distributed Computation of Virtual Coordinates
Mirela Ben-Chen, Craig Gotsman, and Camille Wormser | ||
| 3:20-4:00 | — Coffee break — | ||
| Session 7 — Helmut Alt | |||
| 4:00-4:20 | A Space-Optimal Data-Stream Algorithm for Coresets in the Plane*
Pankaj K. Agarwal and Hai Yu | ||
| 4:20-4:40 | On Regular Vertices on the Union of Planar Objects
Esther Ezra, János Pach, and Micha Sharir | ||
| 4:40-5:00 | On the Number of k-rich Transformations
Jozsef Solymosi and Gábor Tardos | ||
| 5:00-5:20 | Similar Simplices in a d-dimensional Point Set
Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, and Micha Sharir | ||
| 6:30 | — Banquet: Roof terrace — | ||
| Friday, June 8 | ||
|---|---|---|
| Session 8A — Helmut Alt | Session 8B (Sapphire Hall) — John Iacono | |
| 9:00-9:25 | Line Transversals to Disjoint Balls
Ciprian Borcea, Xavier Goaoc, and Sylvain Petitjean | New Upper Bounds on the Quality of PCA Bounding Boxes in R2 and R3
Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter Rote |
| 9:25-9:50 | The Voronoi Diagram of Three Lines in 3D
Hazel Everett, Daniel Lazard, Sylvain Lazard, and Mohab Safey El Din | Pareto Envelopes in R3 under l1 and l∞ Distance Functions
Victor Chepoi and Karim Nouioua |
| 9:50-10:15 | Between Umbra and Penumbra
Julien Demouth, Olivier Devillers, Hazel Everett, Sylvain Lazard, and Raimund Seidel | Computing the Volume of the Union of Cubes
Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir |
| 10:15-11:00 | — Coffee break — | |
| Session 9 — Ileana Streinu | ||
| 10:40-11:00 | Approximating the Centroid is Hard
Luis Rademacher | |
| 11:00-11:20 | Hardness of Minkowski Addition and Related Operations
Hans Raj Tiwary | |
| 11:20-11:40 | A Geometric Framework for Solving Subsequence Problems in Computational Biology Efficiently
Thorsten Bernholt, Friedrich Eisenbrand, and Thomas Hofmeister | |
| 11:40-12:00 | On the Exact Maximum Complexity of Minkowski Sums of Convex Polyhedra
Efi Fogel and Dan Halperin | |
| 12:00-2:00 | — Lunch — | |
| Session 10 — Suresh Venkatasubramanian | ||
| 2:00-2:20 | On Approximate Halfspace Range Counting and Relative ε-Approximations
Boris Aronov, Sariel Har-Peled, and Micha Sharir | |
| 2:20-2:40 | On Approximate Range Counting and Halfspace Depth
Peyman Afshani and Timothy Chan | |
| 2:40-3:00 | A Data Structure for Multi-Dimensional Range Reporting
Yakov Nekrich | |
| 3:00-3:20 | Tight Bounds for Dynamic Convex Hull Queries
Erik D. Demaine and Mihai Pǎtraşcu | |
| 3:20-4:00 | — Coffee break — | |
| Session 11 — Jeff Erickson | ||
| 4:00-4:20 | Kinetic kd-Trees and Longest-Side kd-Trees
Mohammad Ali Abam, Mark de Berg, and Bettina Speckmann | |
| 4:20-4:40 | Fully Dynamic Geometric Spanners
Liam Roditty | |
| 4:40-5:00 | Embeddings of Moving Points in Euclidean Space
Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu | |
| 5:00 | — Conference ends — | |