CG Week, June 17–21, 2019
PDF version of the program
Book of Abstracts
Full Book Tuesday Wednesday Thursday Friday
Location key:
UPlace A = University Place, Multnomah Falls + Elowah Falls Ballroom
UPlace B = University Place, Wahkeena Falls Ballroom
UPlace Lobby = University Place, Columbia Falls Ballroom lobby
Maseeh = Maseeh College of Engineering and Computer Science, classrooms
Maseeh Atrium = Maseeh College, central atrium
Crystal = Crystal Ballroom
*Student talks are asterisked, student speakers underlined.
Monday, June 17, 2019
|
|
|
|
| earlier | Excursions | Off-site |
|
|
|
|
| 6:00–8:00pm | Welcome reception | UPlace A + B |
|
|
|
|
Tuesday, June 18, 2019
|
|
|
|
| 9:00–9:10 | Welcome | UPlace A |
|
|
|
|
| 9:10–9:40 |
SoCG Best Paper, Session TUE-1 (chair: Yusu Wang & Gill Barequet) |
UPlace A |
|
|
|
|
|
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs V. Cohen-Addad, É. Colin de Verdière, D. Marx and A. de Mesmay |
|
|
|
|
|
| 9:40–10:20 | Fast forward: Workshops, YRF Part 1 | UPlace A |
|
|
|
|
| 10:20–10:50 | Coffee break | UPlace Lobby |
|
|
|
|
| 10:50–11:50 | SoCG Session TUE-2 | UPlace A + B |
|
|
|
|
|
Session TUE-2A: Data Structures I, UPlace A (chair: Dan Halperin)
|
|
| 10:50 |
Dynamic Planar Point Location in External Memory J. I. Munro and Y.Nekrich |
| 11:10 |
A Divide-and-Conquer Algorithm for Two-Point L1 Shortest Path Queries in Polygonal Domains Haitao Wang |
| 11:30 |
Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead Pankaj K. Agarwal, Ravid Cohen, Dan Halperin and Wolfgang Mulzer |
|
Session TUE-2B: Persistent Homology I, UPlace B (chair: Erin Chambers)
|
|
| 10:50 |
*DTM-based Filtrations H. Anai, F. Chazal, M. Glisse, Y. Ike, H. Inakoshi, R. Tinarrage and Y. Umeda |
| 11:10 |
Topological Data Analysis in Information Space Herbert Edelsbrunner, Ziga Virk, Hubert Wagner |
| 11:30 |
On the Metric Distortion of Embedding Persistence Diagrams into separable Hilbert spaces M. Carrière and U. Bauer |
|
|
|
|
| 11:50–12:00 | Break | UPlace Lobby |
|
|
|
|
| 12:00–1:00 | SoCG Session TUE-3 | UPlace A + B |
|
|
|
|
|
Session TUE-3A: Combinatorial Geometry I, UPlace A (chair: Joseph Mitchell)
|
|
| 12:00 |
*On the Complexity of the k-Level in Arrangements of Pseudoplanes M. Sharir and C. Ziv |
| 12:20 |
*On grids in point-line arrangements in the plane M. Mirzaei and A. Suk |
| 12:40 |
The Crossing Tverberg Theorem R. Fulek and B. Gärtner and A. Kupavskii and P. Valtr and U. Wagner |
|
Session TUE-3B: ε-Nets and VC Dimension, UPlace B (chair: Steve Oudot)
|
|
| 12:00 |
On weak ε-nets and the Radon number S. Moran and A. Yehudayoff |
| 12:20 |
Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges Y. Tao and Y. Wang |
| 12:40 |
*Journey to the Center of the Point Set S. Har-Peled and M. Jones |
|
|
|
|
| 1:00–2:30 | Catered lunch, sponsored by Mentor Graphics | Maseeh Atrium |
|
|
|
|
| 2:30–4:00 | Workshops + YRF | Maseeh |
|
|
|
|
|
Young Researchers Forum, Maseeh EB 92 (chair: Steve Oudot)
|
|
| 2:30 |
Ellipsoidal Voronoi Diagrams Ahmed Abdelkader and David Mount |
| 2:50 |
On tree-like abstract Voronoi diagrams in expected linear time Kolja Junginger and Evanthia Papadopoulou |
| 3:10 |
On Mergable Coresets for Polytope Distance Benwei Shi, Aditya Bhaskara, Waiming Tai and Jeff Phillips |
| 3:30 |
Art Gallery Problem for Indoor Localization Haotian Wang, Jie Gao, Niranjini Rajagopal, Anthony Rowe and Bruno Sinopoli |
|
8th Annual Minisymposium on Computational Topology, Maseeh EB 103
|
|
| 2:30 |
Exact Topological Inference of the Resting-State Brain Network in Twins Moo K. Chung |
| 3:30 |
Metric learning for persistence-based summaries and application to graph classification Yusu Wang |
|
Workshop on Open Problems and Hard Instance Challenges, Maseeh EB 102
|
|
| 2:30 |
Introduction: Overview, summary of background on the The Open Problems Project (TOPP), updates (TOPP 2.0), and the role of open problems in driving research in CG/CT |
|
Contributed open problems |
|
|
|
|
|
| 4:00–4:30 | Coffee/snack break | Maseeh Atrium |
|
|
|
|
| 4:30–6:30 | Workshops + YRF (continued) | Maseeh |
|
|
|
|
|
Young Researchers Forum, Maseeh EB 92 (chair: Radoslav Fulek)
|
|
| 4:30 |
Trajectory Visibility in a Simple Polygon Patrick Eades, Ivor van der Hoog, Frank Staals and Maarten Löffler |
| 4:50 |
Computing feasible trajectories for an articulated probe in three dimensions Ovidiu Daescu and Ka Yaw Teo |
| 5:10 |
New Applications of Nearest-Neighbor Chains Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael Goodrich, Stephen Kobourov, Pedro Matias and Valentin Polishchuk |
| 5:30 |
Active Learning a Convex Body in Low Dimensions Sariel Har-Peled, Mitchell Jones and Saladi Rahul |
|
8th Annual Minisymposium on Computational Topology, Maseeh EB 103
|
|
| 4:30 |
Topological Techniques for Characterizing Patterns Induced by Ion Bombardment Rachel Neville |
| 5:00 |
Topology-Preserving Deep Image Segmentation for Thin Biomedical Structures Chao Chen |
| 5:30 |
Sketching and Clustering Metric Measure Spaces Kritika Singhal |
| 6:00 |
Generalized Persistence Algorithm for Decomposing Multi-parameter Persistence Modules Tamal Dey |
|
Workshop on Open Problems and Hard Instance Challenges, Maseeh EB 102
|
|
| 4:30 |
Hard Instances Challenge overview, and presentation of prizes |
|
Presentation by winner(s) of the challenge |
|
|
Wrap-up and summary; benchmarks, contest repositories, Hard Instances Project (HIP); future directions discussion |
|
|
|
|
|
Wednesday, June 19, 2019
|
|
|
|
| 9:00–10:00 | SoCG Session WED-4 | UPlace A + B |
|
|
|
|
|
Session WED-4A: Smallest Enclosing, UPlace A (chair: Subhash Suri)
|
|
| 9:00 |
*Probabilistic Smallest Enclosing Ball in High Dimensions via Subgradient Sampling A. Krivošija and A. Munteanu |
| 9:20 |
Smallest k-Enclosing Rectangle Revisited T. M. Chan and S. Har-Peled |
| 9:40 |
Computing Shapley Values in the Plane S. Cabello and T. M. Chan |
|
Session WED-4B: Persistent Homology II, UPlace B (chair: Bettina Speckmann)
|
|
| 9:00 |
Exact computation of the matching distance on 2-parameter persistence modules Michael Kerber, Michael Lesnick and Steve Oudot |
| 9:20 |
Chunk Reduction for Multi-Parameter Persistent Homology U. Fugacci and M. Kerber |
| 9:40 |
*Computing Persistent Homology of Flag Complexes via Strong Collapses J-D. Boissonnat and S. Pritam |
|
|
|
|
| 10:00–10:30 | Coffee break | UPlace Lobby |
|
|
|
|
| 10:30–11:30 | SoCG Session WED-5 | UPlace A + B |
|
|
|
|
|
Session WED-5A: Combinatorial Geometry II, UPlace A (chair: Pankaj Agarwal)
|
|
| 10:30 |
*Ham-Sandwich cuts and center transversals in subspaces Patrick Schnider |
| 10:50 |
On the chromatic number of disjointness graphs of curves János Pach and István Tomon |
| 11:10 |
Semi-algebraic colorings of complete graphs J. Fox, J. Pach, and A. Suk |
|
Session WED-5B: Optimization and Approximation, UPlace B (chair: Jeff Phillips)
|
|
| 10:30 |
Packing Disks into Disks with Optimal Worst-Case Density S. P. Fekete and P. Keldenich and C. Scheffer |
| 10:50 |
*Preconditioning for the Geometric Transportation Problem A. B. Khesin, A. Nikolov, and D. Paramonov |
| 11:10 |
*Algorithms for Metric Learning via Contrastive Embeddings D. Ihara, N. Mohammadi and A. Sidiropoulos |
|
|
|
|
| 11:30–11:40 | Break | UPlace Lobby |
|
|
|
|
| 11:40–12:40 | Invited talk, Sanjoy Dasgupta (chair: Yusu Wang) | UPlace A |
|
|
|
|
|
A Geometric Data Structure from Neuroscience Sanjoy Dasgupta, UC San Diego |
|
|
|
|
|
| 12:40–2:30 | Lunch on your own | Off-site |
|
|
|
|
| 2:30–3:30 | SoCG Session WED-6 | UPlace A + B |
|
|
|
|
|
Session WED-6A: Graph Drawing I, UPlace A (chair: Matias Korman)
|
|
| 2:30 |
*Efficient Algorithms for Ortho-Radial Graph Drawing B. Niedermann, I. Rutter, and M. Wolf |
| 2:50 |
*Bounded degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12 D. Bokal, Z. Dvořák, P. Hliněný, J. Leaños, B. Mohar, T. Wiedera |
| 3:10 |
ℤ2-Genus of Graphs and Minimum Rank of Partial Symmetric Matrices R. Fulek and J. Kynčl |
|
Session WED-6B: Matching and Partitioning, UPlace B (chair: Monique Teillaud)
|
|
| 2:30 |
A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings N. Lahn and S. Raghvendra |
| 2:50 |
An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications P. K. Agarwal, B. Aronov, E. Ezra, and J. Zahl |
| 3:10 |
*Efficient Algorithms for Geometric Partial Matching Pankaj K. Agarwal, Hsien-Chih Chang, Allen Xiao |
|
|
|
|
| 3:30–4:00 | Coffee/snack break | UPlace Lobby |
|
|
|
|
| 4:00–5:00 | SoCG Session 7 | UPlace A + B |
|
|
|
|
|
Session WED-7A: Topology, UPlace A (chair: Raimund Seidel)
|
|
| 4:00 |
Topologically Trivial Closed Walks in Directed Surface Graphs Jeff Erickson and Yipu Wang |
| 4:20 |
*3-Manifold Triangulations with Small Treewidth K. Huszár and J. Spreer |
| 4:40 |
When Convexity Helps Collapsing Complexes D. Attali, A. Lieutier, and D. Salinas |
|
Session WED-7B: Algorithm Complexity, UPlace B (chair: Gill Barequet)
|
|
| 4:00 |
*The One-Way Communication Complexity of Dynamic Time Warping Distance V. Braverman, M. Charikar, W. Kuszmaul, D. P. Woodruff, and L. F. Yang |
| 4:20 |
Upward Book Embeddings of st-Graphs C. Binucci, G. Da Lozzo, E. Di Giacomo, W. Didimo, T. Mchedlidze, M. Patrignani |
|
|
|
|
| 5:00–6:00 | Discussion forum | UPlace A |
|
|
|
|
| 7:00–? | Banquet | Crystal |
|
|
|
|
Thursday, June 20, 2019
|
|
|
|
| 9:00–10:00 | SoCG Session THU-8 | UPlace A + B |
|
|
|
|
|
Session THU-8A: Contact and Surface Graphs, UPlace A (chair: Christiane Schmidt)
|
|
| 9:00 |
*Near-optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs H. Wang, J. Xue |
| 9:20 |
Morphing Contact Representations of Graphs Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Vincenzo Roselli |
| 9:40 |
Lower Bounds for Electrical Reduction on Surfaces Hsien-Chih Chang, Marcos Cossarini, Jeff Erickson |
|
Session THU-8B: Frechét Distance, UPlace B (chair: Chee Yap)
|
|
| 9:00 |
The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances A. Driemel, J. M. Phillips, I. Psarros |
| 9:20 |
*Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance K. Bringmann, M. Künnemann and A. Nusser |
| 9:40 |
*Polyline Simplification has Cubic Complexity K. Bringmann and B. R. Chaudhury |
|
|
|
|
| 10:00–10:30 | Coffee break | UPlace Lobby |
|
|
|
|
| 10:30–11:30 | SoCG Session THU-9 | UPlace A + B |
|
|
|
|
|
Session THU-9A: Geometric Data Structures, UPlace A (chair: Tamal Dey)
|
|
| 10:30 |
*A Spanner for the Day After K. Buchin, S. Har-Peled and D. Oláh |
| 10:50 |
*Searching for the Closest-pair in a Query Translate J. Xue, Y. Li, S. Rahul, R. Janardan |
| 11:10 |
*Preprocessing Ambiguous Imprecise Points I. van der Hoog, I. Kostitsyna, M. Löffler, B. Speckmann |
|
Session THU-9B: Robotics and Geometric Structures, UPlace B (chair: Esther Ezra)
|
|
| 10:30 |
General techniques for approximate incidences and their application to the camera posing problem D. Aiger, H. Kaplan, E. Kokiopoulou, M. Sharir, B. Zeisl |
| 10:50 |
Rods and Rings: Soft Subdivision Planner for ℝ3×S2 C.-H. Hsu, Y.-J. Chiang and C. Yap |
| 11:10 |
Optimal algorithm for geodesic farthest-point Voronoi diagrams Luis Barba |
|
|
|
|
| 11:30–11:40 | Break | UPlace Lobby |
|
|
|
|
| 11:40–11:55 | Fast forward: YRF Part 2 | UPlace A |
|
|
|
|
| 11:55–12:45 | Multimedia session | UPlace A |
|
|
|
|
|
Fréchet View – A Tool for Exploring Fréchet Distance Algorithms Peter Schäfer |
|
|
A manual comparison of convex hull algorithms Maarten Löffler |
|
|
Packing Geometric Objects with Optimal Worst-Case Density A. T. Becker, S. P. Fekete, P. Keldenich, S. Morr, C. Scheffer |
|
|
Properties of Minimal-Perimeter Polyominoes G. Barequet and G. Ben-Shachar |
|
|
|
|
|
| 12:45–1:30 | Box lunch | UPlace Lobby |
|
|
|
|
| 1:00–2:20 | Business meeting | UPlace A |
|
|
|
|
| 2:30–4:00 | Workshops + YRF | Maseeh |
|
|
|
|
|
Young Researchers Forum, Maseeh EB 92 (chair: Erin Chambers)
|
|
| 2:30 |
Skeletonisation Algorithms for Unorganised Point Clouds with Theoretical Guarantees Philip Smith and Vitaliy Kurlin |
| 2:50 |
Jaccard Filtration and stable paths for Mapper Nathaniel Saul, Bala Krishnamoorthy and Dustin Arendt |
| 3:10 |
First Steps Towards Lower-Bounding the Number of Topological Descriptors for Reconstruction Samuel Micka and David L. Millman |
| 3:30 |
On the Average Time Complexity of the Reduction Algorithm for Persistent Homology Hannah Schreiber and Michael Kerber |
|
The 4th Workshop on Geometry and Machine Learning, Maseeh EB 103
|
|
| 2:30 |
Tutorial: A Primer on the Geometry in Machine Learning Jeff Phillips (University of Utah) |
| 3:00 |
Greedy Is Good, But Needs Randomization Hu Ding (University of Science and Technology of China & Michigan State University) |
| 3:20 |
Condensation for the Approximate Nearest-Neighbor Rule Alejandro Flores-Velazco (University of Maryland) |
| 3:40 |
Relative Error RKHS Embeddings for Gaussian Kernels Wai Ming Tai (University of Utah) |
|
Algebraic Methods in Discrete and Computational Geometry, Maseeh EB 102
|
|
| 2:30 |
Algebraic techniques in geometry: State of (some of) the art Micha Sharir |
| 3:30 |
Cutting space curves and applications to discrete geometry Josh Zahl |
|
|
|
|
| 4:00–4:30 | Coffee/snack break | Maseeh Atrium |
|
|
|
|
| 4:30–6:00 | Workshops + YRF (continued) | Maseeh |
|
|
|
|
|
Young Researchers Forum, Maseeh EB 92 (chair: Donald Sheehy)
|
|
| 4:30 |
A Toroidal Maxwell-Cremona-Delaunay Correspondence Patrick Lin and Jeff Erickson |
| 4:50 |
On Minimal-Perimeter Polyforms Gill Barequet and Gil Ben-Shachar |
| 5:10 |
A 1∕4-Approximation Algorithm for the Maximum Hidden Vertex Set Problem in Simple Polygons Pritam Bhattacharya and Carlos Alegria |
| 5:30 |
Hardness of Approximation for Geometric Set Cover and Related Problems Sima Hajiaghaei |
|
The 4th Workshop on Geometry and Machine Learning, Maseeh EB 103
|
|
| 4:30 |
Invited: Approaches to Robust Artificial Intelligence: Can Geometry Help? Thomas G. Dietterich (Oregon State University) |
| 5:20 |
On the Geometry of Adversarial Examples Marc Khoury (UC Berkeley) |
| 5:40 |
A Topological Regularizer for Classifiers via Persistent Homology Chao Chen (Stony Brook University) |
|
Algebraic Methods in Discrete and Computational Geometry, Maseeh EB 102
|
|
| 4:30 |
Geometric approximation algorithms via the polynomial method Timothy Chan |
| 5:30 |
On Soft Computational Geometry Chee Yap |
|
|
|
|
| 6:00–7:00 | Springer-hosted reception | Maseeh Atrium |
|
|
|
|
Friday, June 21, 2019
|
|
|
|
| 9:00–10:00 | SoCG Session FRI-10 | UPlace A + B |
|
|
|
|
|
Session FRI-10A: Data Structures II, UPlace A (chair: Yusu Wang)
|
|
| 9:00 |
A New Lower Bound for Semigroup Orthogonal Range Searching Peyman Afshani |
| 9:20 |
Independent Range Sampling, Revisited Again Peyman Afshani and Jeff M. Phillips |
| 9:40 |
Dynamic Geometric Data Structures via Shallow Cuttings T. M. Chan |
|
Session FRI-10B: Graph Drawing II, UPlace B (chair: Evanthia Papadopoulou)
|
|
| 9:00 |
Dual Circumference and Collinear Sets V. Dujmović and P. Morin |
| 9:20 |
Cubic Planar Graphs That Cannot Be Drawn On Few Lines David Eppstein |
| 9:40 |
Connecting the Dots (with Minimum Crossings) Akanksha Agrawal, Grzegorz Guśpiel, Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi |
|
|
|
|
| 10:00–10:30 | Coffee break | UPlace Lobby |
|
|
|
|
| 10:30–11:30 | SoCG Session FRI-11 | UPlace A + B |
|
|
|
|
|
Session FRI-11A: Complexity, UPlace A (chair: Kasturi Varadarajan)
|
|
| 10:30 |
The Unbearable Hardness of Unknotting A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer |
| 10:50 |
Circumscribing Polygons and Polygonizations for Disjoint Line Segments H. A. Akitaya, M. Korman, M. Rudoy, C. D. Tóth, and D. L. Souvaine |
| 11:10 |
Counting Polygon Triangulations is Hard David Eppstein |
|
Session FRI-11B: Combinatorial Geometry III, UPlace B (chair: Micha Sharir)
|
|
| 10:30 |
An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting Goaoc X., Holmsen A., and Nicaud C. |
| 10:50 |
A Product Inequality for Extreme Distances Adrian Dumitrescu |
| 11:10 |
Convex Polygons in Cartesian Products J.-L. De Carufel, A. Dumitrescu, W. Meulemans, T. Ophelders, C. Pennarun, C. D. Tóth, and S. Verdonschot |
|
|
|
|
| 11:30–11:40 | Break | UPlace Lobby |
|
|
|
|
| 11:40–12:40 | Invited talk, Bruce Donald (chair: Gill Barequet) | UPlace A |
|
|
|
|
|
Some Geometric and Computational Challenges Arising in Structural Molecular Biology Bruce Donald, Duke University |
|
|
|
|
|
| 12:40–2:30 | Lunch + Birthday celebration for John Hershberger | Maseeh |
|
|
|
|
| 12:40 |
Lunch (Maseeh Atrium) |
| 1:15 |
Birthday celebration (Maseeh EB 102) |
| 2:15 |
Birthday cake and coffee (Maseeh Atrium) |
|
|
|
|
| 2:30–4:00 | Workshops | Maseeh |
|
|
|
|
|
8th Annual Minisymposium on Computational Topology, Maseeh EB 92
|
|
| 2:30 |
TDA on Genomics Data Laxmi Parida |
| 3:30 |
Geodesics in persistence diagram space Samir Chowdhury |
|
Algebraic Methods in Discrete and Computational Geometry, Maseeh EB 102
|
|
| 2:30 |
Applications of algebraic geometry and model theory in incidence combinatorics Saugata Basu |
| 3:30 |
Some things algebra told us about order types Xavier Goaoc |
|
|
|
|
| 4:00–4:30 | Coffee/snack break | Maseeh Atrium |
|
|
|
|
| 4:30–6:00 | Workshops (continued) | Maseeh |
|
|
|
|
|
8th Annual Minisymposium on Computational Topology, Maseeh EB 92
|
|
| 4:30 |
PersLay: A Simple and Versatile Neural Network Layer for Persistence Diagrams Mathieu Carriere |
| 5:00 |
Open Questions and Discussions |
|
Algebraic Methods in Discrete and Computational Geometry, Maseeh EB 102
|
|
| 4:30 |
Computing the first dimensional path homology for directed graphs Yusu Wang |
| 5:00 |
Ordered graphs and large bi-cliques in intersection graphs of curves Istvan Tomon |
| 5:30 |
Polynomial partitioning: Algorithms and applications Esther Ezra |
|
|
|
|