CG Week, June 17–21, 2019

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

PDF version of the program

Short Program
Full Program

Book of Abstracts

Full Book
Tuesday
Wednesday
Thursday
Friday

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 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 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
10:50

Dynamic Planar Point Location in External MemoryJ. I. Munro and Y.Nekrich

11:10

A Divide-and-Conquer Algorithm for Two-Point L1 Shortest Path Queries in Polygonal DomainsHaitao 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
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
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
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 Maseeh Atrium



2:30–4:00 Workshops + YRF Maseeh



Young Researchers Forum (Maseeh EB 92)

8th Annual Minisymposium on Computational Topology (Maseeh EB 103)

Workshop on Open Problems and Hard Instance Challenges (Maseeh EB 102)

   



4:00–4:30 Coffee/snack break Maseeh Atrium



4:30–6:00 Workshops + YRF (continued) Maseeh



Wednesday, June 19, 2019




9:00–10:00 SoCG Session WED-4 UPlace A + B



Session WED-4A: Smallest Enclosing, UPlace A
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
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 HomologyU. 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
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
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 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
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
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
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
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
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
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
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
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 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)

The 4th Workshop on Geometry and Machine Learning (Maseeh EB 103)

Algebraic Methods in Discrete and Computational Geometry (Maseeh EB 102)

   



4:00–4:30 Coffee/snack break Maseeh Atrium



4:30–6:00 Workshops + YRF (continued) Maseeh



6: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
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
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
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 HardDavid Eppstein

   
Session FRI-11B: Combinatorial Geometry III, UPlace B
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 UPlace A



Some Geometric and Computational Challenges Arising in Structural Molecular Biology Bruce Donald, Duke University

   



12:40–2:30 Lunch on your own Off-site



2:30–4:00 Workshops Maseeh



The 4th Workshop on Geometry and Machine Learning (Maseeh EB 103)

8th Annual Minisymposium on Computational Topology (Maseeh EB 92)

Algebraic Methods in Discrete and Computational Geometry (Maseeh EB 102)

   



4:00–4:30 Coffee/snack break Maseeh Atrium



4:30–6:00 Workshops (continued) Maseeh