A draft of the week's program is available both as a pdf and the table below. We will add more details (and better formatting) when we're able. Note there will also be a welcome reception in the evening on Sunday June 11 and Comp-Geometers' 60th BD Fest on Friday June 16.
Sunday, June 11, 2023
| Time | ||
|---|---|---|
| 6:00 PM–8:00 PM (18:00–20:00) | Welcome Reception (Second Floor Atrium in FO) | |
Monday, June 12, 2023
| Time | Session 1 (ECSS 2.102) | Session 2 (ECSS 2.415) |
|---|---|---|
| 8:00 AM (08:00) | Breakfast (SU 2.905/Artemis) | |
| 8:50 AM (08:50) | Opening (ECSS 2.102) | |
| 9:00 AM (09:00) | SoCG Best Paper Award Mickaël Buchet, Bianca B. Dornelas, and Michael KerberSparse higher order Čech filtrations (ECSS 2.102) |
|
| 9:30 AM (09:30) | Fast Forward: YRF (ECSS 2.102) | |
| 9:50 AM (09:50) | Short Break | |
| 10:00 AM–10:40 PM (10:00–10:40) | SoCG (Session Chair: Bei Wang) | SoCG (Session Chair: Arindam Khan) |
| 10:00 AM (10:00) | Pepijn Roos Hoefgeest and Lucas Slot The Christoffel-Darboux kernel for topological data analysis |
Sayan Bandyapadhyay, William Lochet, and Saket Saurabh FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii |
| 10:20 AM (10:20) | Nate Clause, Tamal K. Dey, Facundo Memoli, and Bei Wang Meta-Diagrams for 2-Parameter Persistence |
Eduard Eiben, Robert Ganian, and Iyad Kanj The Parameterized Complexity of Coordinated Motion Planning |
| 10:40 AM (10:40) | Coffee Break (ECSW Annex Atrium) | |
| 11:10 AM–12:30 PM (11:10–12:30) | SoCG (Session Chair: Tamal Dey) | SoCG (Session Chair: Siu-Wing Cheng) |
| 11:10 AM (11:10) | Richard Qi and Benjamin Qi New Approximation Algorithms for Touring Regions |
|
| 11:30 AM (11:30) | Aziz Burak Guelen, Facundo Memoli, Zhengchao Wan, and Yusu Wang A generalization of the persistent Laplacian to simplicial maps |
Sunil Arya and David Mount Optimal Volume-Sensitive Bounds for Polytope Approximation |
| 11:50 AM (11:50) | Ángel Javier Alonso and Michael Kerber Decomposition of zero-dimensional persistence modules via rooted subsets |
Ioannis Psarros and Dennis Rohde Random projections for curves in high dimensions |
| 12:10 PM (12:10) |  Ulrich Bauer, Michael Lesnick, and Fabian LenzenEfficient Two-Parameter Persistence Computation via Cohomology |
Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue Minimum-Membership Geometric Set Cover, Revisited |
| 12:30 PM (12:30) | Lunch Break (SU 2.905/Artemis) | |
| 1:45 PM (13:45) | Invited Talk Moon Duchin Redistricting as a computational geometry problem (ECSS 2.102) |
|
| 2:45 PM (14:45) | Coffee Break (ECSW Annex Atrium) | |
| 3:00 PM–4:15 PM (15:00–16:15) | Young Researchers Forum (Session Chair: Anne Driemel) | Young Researchers Forum (Session Chair: Tim Ophelders) |
| 3:00 PM (15:00) | Timothy M. Chan, Qizheng He and Yuancheng Yu On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k |
Sándor Kisfaludi-Bak and Geert van Wordragen A quadtree for hyperbolic space |
| 3:15 PM (15:15) | Jiaxi Zhang and Ezra Miller Geodesic Complexity of Convex Polyhedra |
Bradley McCoy, Brittany Terese Fasy, Hsien-Chih Chang, David L. Millman and Carola Wenk From Curves to Words |
| 3:30 PM (15:30) | Haitao Wang and Yiming Zhao Improved Algorithms for Distance Selection and Related Problems |
Elena Wang, Elizabeth Munch, Erin Wolf Chambers and Sarah Percival A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance |
| 3:45 PM (15:45) | Oliver Chubet, Parth Parikh, Don Sheehy and Siddharth Sheth Approximate Hausdorff Distance in Doubling Metrics |
Samira Jabry, Erin Chambers and Elizabeth Munch Un-smoothing of Contour Trees |
| 4:00 PM (16:00) | Tuyen Pham and Hubert WagnerKd-trees work with separable Bregman divergences |
Dhanush Giriyan, Jessi Cisewski-Kehe and Brittany Terese Fasy Image Shape Classification with the Weighted Euler Curve Transform |
| 4:20 PM (16:20) | Break | |
| 5:00 PM–6:15 PM (17:00–18:15) | Young Researchers Forum (Session Chair: Maike Buchin) | Young Researchers Forum (Session Chair: Bei Wang) |
| 5:00 PM (17:00) | Jacobus Conradi, Anne Driemel and Benedikt Kolbe Revisiting the Fréchet distance between piecewise smooth curves |
Florian Russold, Justin Curry, Washington Mio, Tom Needham and Osman Berat Okutan Convergence of Leray Cosheaves for Decorated Mapper Graphs |
| 5:15 PM (17:15) | Jacobus Conradi and Anne Driemel Subtrajectory Clustering for Human Motion Data |
Maria Herick, Michael Joachim and Jan Vahrenhold Adaptive Approximation of Persistent Homology |
| 5:30 PM (17:30) | Frederik Brüning, Anne Driemel, Alperen Ergür and Heiko Röglin On the number of iterations of the DBA algorithm |
Oliver Chubet, Kirk Gardner and Donald Sheehy Using Sub-barcodes for Topological Inference |
| 5:45 PM (17:45) | Aditya Acharya and David Mount Tracking Evolving Labels using Cone based Oracles |
Fritz Grimpen and Anastasios Stefanou Persistence of complements of spanning trees |
| 6:00 PM (18:00) | Hugo Akitaya and Frederick Stock Reconfiguration of 3D Pivoting Modular Robots |
Rescheduled SoCG Presentation Facundo Mémoli and Ling Zhou Ephemeral persistence features and the stability of filtered chain complexes |
| 6:00 PM (18:00) | Short Break | |
| 6:10 PM–7:30 PM (18:10–19:30) | DCG Reception (SU 2.905/Artemis) | |
Tuesday, June 13, 2023
| Time | Session 1 (ECSS 2.102) | Session 2 (ECSS 2.415) |
|---|---|---|
| 8:00 AM (08:00) | Breakfast (SU 2.905/Artemis) | |
| 9:00 AM–10:20 AM (9:00–10:20) | SoCG (Session Chair: Mathijs Wintraecken) | SoCG (Session Chair: Mati Korman) |
| 9:00 AM (09:00) | Mikkel Abrahamsen, Linda Kleist, and Till Miltzow Geometric Embeddability of Complexes is $\exists\R$-complete |
Arnold Filtser Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings |
| 9:20 AM (09:20) | Corentin Lunel and Arnaud de Mesmay A structural approach to tree decompositions of knots and spatial graphs |
Hung Le, Lazar Milenkovic, and Shay Solomon Sparse Euclidean Spanners with Optimal Diameter: A General Robust Lower Bound Via a Concave Inverse-Ackermann Function |
| 9:40 AM (09:40) | Benjamin Burton and Alexander He Finding large counterexamples by selectively exploring the Pachner graph |
Sarita de Berg, Marc van Kreveld, and Frank Staals The Complexity of Geodesic Spanners |
| 10:00 AM (10:00) | Kristóf Huszár and Jonathan Spreer On the Width of Complicated JSJ Decompositions |
Timothy M. Chan and Zhengcheng Huang Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size |
| 10:20 AM (10:20) | Coffee Break (ECSW Annex Atrium) | |
| 10:50 AM–12:10 PM (10:50–12:10) | SoCG (Session Chair: Jeff Erickson) | SoCG (Session Chair: David Eppstein) |
| 10:50 AM (10:50) | Jack Stade and Jamie Tucker-Foltz Topological Universality of the Art Gallery Problem |
Pankaj K. Agarwal and Sariel Har-Peled Computing Instance Optimal Kernels in Two Dimensions |
| 11:10 AM (11:10) | Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud Computing a Dirichlet domain for a hyperbolic surface |
Ahmad Biniaz Improved Bounds for Covering Paths and Trees in the Plane |
| 11:30 AM (11:30) | Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals Shortest Paths in Portalgons |
Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set |
| 11:50 AM (11:50) | Vincent Delecroix, Matthijs Ebbens, Francis Lazarus, and Ivan Yakovlev Algorithms for length spectra of combinatorial tori |
Daria Pchelina and Thomas Fernique When ternary triangulated disc packings are densest: examples, counter-examples and techniques |
| 12:10 PM (12:10) | Lunch Break (SU 2.905/Artemis) | |
| 1:30 PM–3:00 PM (13:30–15:00) | Computational Topology: Workshop on Mobius inversion and Reeb spaces Organizers: Amit Patel, Sarah Percival, and Elizabeth Vidaurre |
Workshop on Recent Developments in Geometric Clustering Organizers: Sayan Bandyapadhyay and Ali Vakilian |
| 1:30 PM (13:30) | Alex McCleary Interleavings and Couplings |
Vincent Cohen-Addad Recent Developments in Euclidean Clustering: Sketching and Approximation Algorithms |
| 2:00 PM (14:00) | Tung Lam ℓp- type Distances on Reeb Graphs |
|
| 2:20 PM (14:20) | Samson Zhou Learning-Augmented Algorithms for k-means Clustering |
|
| 2:30 PM (14:30) | Aziz Gülen Using Galois Connections to Prove Bottleneck Stability |
|
| 3:00 PM (15:00) | Coffee Break (ECSW Annex Atrium) | |
| 3:30 PM–5:30 PM (15:30–17:30) | Computational Topology: Workshop on Mobius inversion and Reeb spaces Organizers: Amit Patel, Sarah Percival, and Elizabeth Vidaurre |
Workshop on Recent Developments in Geometric Clustering Organizers: Sayan Bandyapadhyay and Ali Vakilian |
| 3:30 PM (15:30) | Woojin Kim The Discriminating Power of the Generalized Rank Invariant |
Deeparnab Chakrabarty Round-or-Cut Technique for designing Approximation Algorithms for Clustering Problems |
| 4:00 PM (16:00) | Ling Zhou Persistent Cup Product Structures and Related Invariants |
|
| 4:20 PM (16:20) | Liren Shan Explainable 𝑘-Means: Don’t Be Greedy, Plant Bigger Trees! |
|
| 4:30 PM (16:30) | Tatum Rask Cofiltrations: What, Where, and Why? |
|
| 5:00 PM (17:00) | Problem Session | |
| 5:30 PM (17:30) | Break | |
| 6:00 PM–6:50 PM (18:00–18:50) | Discussion Forum (ECSS 2.102) | |
| 6:50 PM (18:50) | Short Break | |
| 7:00 PM (19:00) | Conference Dinner (SU 2.602/Galaxy) | |
Wednesday, June 14, 2023
| Time | Session 1 (ECSS 2.102) | Session 2 (ECSS 2.415) |
|---|---|---|
| 8:00 AM (08:00) | Breakfast (SU 2.905/Artemis) | |
| 9:00 AM–10:20 AM (9:00–10:20) | SoCG (Session Chair: Yusu Wang) | SoCG (Session Chair: Maarten Loffler) |
| 9:00 AM (09:00) | J. Andreas Bærentzen, Rasmus E. Christensen, Emil T. Gæde, and Eva Rotenberg Multilevel Skeletonization Using Local Separators |
Michael Hoffmann and Meghana M. Reddy The Number of Edges in Maximal 2-planar Graphs |
| 9:20 AM (09:20) | Michael Kerber and Matthias Söls The localized Union-of-Balls Bifiltration |
Jacob Holm, Ivor van der Hoog, and Eva Rotenberg Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings |
| 9:40 AM (09:40) | Ulrich Bauer and Maximilian Schmahl Efficient Computation of Image Persistence |
Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani, and Martin Nöllenburg Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable |
| 10:00 AM (10:00) | Helena Bergold, Stefan Felsner, and Manfred Scheucher An extension theorem for signotopes |
Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder, and Raphael Steiner Linear size universal point sets for classes of planar graphs |
| 10:20 AM (10:20) | Coffee Break (ECSW Annex Atrium) | |
| 10:50 AM–12:10 PM (10:50–12:10) | SoCG (Session Chair: Esther Ezra) | SoCG (Session Chair: David Mount) |
| 10:50 AM (10:50) | Honglin Zhu and Hyuk Jun Kweon Maximum overlap area of a convex polyhedron and a convex polygon under translation |
Anurag Murty Naredla and Anna Lubiw The Geodesic Edge Center of a Simple Polygon |
| 11:10 AM (11:10) | Andrew Suk and Ji Zeng On higher dimensional point sets in general position |
Auguste Gezalyan and David Mount Voronoi Diagrams in the Hilbert Metric |
| 11:30 AM (11:30) | Egor Gorbachev and Marvin Künnemann Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d >= 4 |
Michael Hoffmann, Oswin Aichholzer, Man-Kwun Chiu, Hung Hoang, Yannic Maus, Jan Kynčl, Birgit Vogtenhuber, and Alexandra Weinberger Drawings of complete multipartite graphs up to triangle flips |
| 11:50 AM (11:50) | Peyman Afshani and Pingan Cheng Lower Bounds for Intersection Reporting among Flat Objects |
Evanthia Papadopoulou Voronoi-like graphs - towards extending Delaunays theorem and applications |
| 12:10 PM (12:10) | Lunch Break (SU 2.905/Artemis) | |
| 1:30 PM (13:30) | Invited Talk Sven Koenig Multi-Agent Path Finding and Its Applications (ECSS 2.102) |
|
| 2:30 PM (14:30) | Coffee Break (ECSW Annex Atrium) | |
| 3:00 PM (15:00) |
CG:SHOP (ECSS 2.102)
|
|
| 3:40 PM (15:40) |
Media Expo (Session Chair: Siddharth Sheth; ECSS 2.102)
|
|
| 4:20 PM (16:20) | Break | |
| 4:50 PM (16:50) | Business Meeting (SU 2.905/Artemis) | |
| 6:20 PM (18:20) | Short Break | |
| 6:30 PM (18:30) | Conference Dinner (SU 2.602/Galaxy) | |
Thursday, June 15, 2023
| Time | Session 1 (ECSS 2.102) | Session 2 (ECSS 2.415) |
|---|---|---|
| 8:00 AM (08:00) | Breakfast (SU 2.905/Artemis) | |
| 9:00 AM–10:20 AM (9:00–10:20) | SoCG (Session Chair: Boris Aronov) | SoCG (Session Chair: Frank Staals) |
| 9:00 AM (09:00) | Jean Cardinal and Micha Sharir Improved Algebraic Degeneracy Testing |
David Eppstein Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time |
| 9:20 AM (09:20) | Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz On the geometric thickness of 2-degenerate graphs |
Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki Reconfiguration of colorings in triangulations of the sphere |
| 9:40 AM (09:40) | Pankaj Agarwal and Esther Ezra Line Intersection Searching Amid Unit Balls in 3-Space |
Gergely Ambrus, Martin Balko, Nóra Frankl, Attila Jung, and Márton Naszódi On Helly numbers of exponential lattices |
| 10:00 AM (10:00) | Patrick Schnider and Pablo Soberon Combinatorial Depth Measures for Hyperplane Arrangements |
Timothy M. Chan Minimum $L_\infty$ Hausdorff Distance of Point Sets Under Translation: Generalizing Klee's Measure Problem |
| 10:20 AM (10:20) | Coffee Break (ECSW Annex Atrium) | |
| 10:50 AM–12:10 PM (10:50–12:10) | SoCG (Session Chair: Ben Burton) | SoCG (Session Chair: John Hershberger) |
| 10:50 AM (10:50) | Luis Scoccola, Hitesh Gakhar, Johnathan Bush, Nikolas Schonsheck, Tatum Rask, Ling Zhou, and Jose A. Perea Toroidal Coordinates: Decorrelating Circular Coordinates With Lattice Reduction |
Mikkel Abrahamsen and Bartosz Walczak Distinguishing classes of intersection graphs of homothets or similarities of two convex disks |
| 11:10 AM (11:10) | Luis Scoccola and Jose A. Perea FibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles |
Jared Albert Espenant, J. Mark Keil, and Debajyoti Mondal Finding a Maximum Clique in a Disk Graph |
| 11:30 AM (11:30) | Hubert Wagner Slice, simplify and stitch: topology-preserving simplification scheme for massive voxel data |
Sayan Bandyapadhyay, Fedor Fomin, and Tanmay Inamdar Coresets for Clustering in Geometric Intersection Graphs |
| 11:50 AM (11:50) | Alfredo Hubard and Andrew Suk Disjoint faces in simple drawings of the complete graph and topological Heilbronn problems |
Esther Galby, Andrea Munaro, and Shizhou Yang Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs |
| 12:10 PM (12:10) | Lunch Break (SU 2.905/Artemis) | |
| 1:30 PM (13:30) |
Test of Time Award (ECSS 2.102)
|
|
| 2:20 PM (14:20) | Best Student Presentation Award (ECSS 2.102) | |
| 2:30 PM (14:30) | Short Break | |
| 2:40 PM–4:30 PM (14:40–16:30) | 7th Workshop on Geometry and Machine Learning Organizers: Hubert Wagner and Jeff M. Phillips |
Workshop on Parameterized Algorithms for Geometric Problems Organizers: Sayan Bandyapadhyay, William Lochet, and Jie Xue |
| 2:40 PM (14:40) | Bei Wang with Archit Rathore, Yichu Zhou, and Vivek Srikumar Topology of Artificial Neuron Activations |
Meirav Zehavi Visibility Problems, Geometric Intersection Graphs and Graph Drawing |
| 3:00 PM (15:00) | Arnur Nigmetov with Dmitriy Morozov Topological Optimization with Big Steps |
|
| 3:20 PM (15:20) | Bala Krishnamoorthy with Nathan May A Normalized Bottleneck Distance on Persistence Diagrams and Homology Preservation under Dimension Reduction |
|
| 3:35 PM (15:35) | David Eppstein Widths of Geometric Graphs |
|
| 3:40 PM (15:40) | Invited Talk Anshumali Shrivastava Revisiting the Economics of Large Language Models with Neural Scaling Laws and Dynamic Sparsity |
|
| 4:30 PM (16:30) | Coffee Break (ECSW Annex Atrium) | |
| 5:00 PM–6:40 PM (17:00–18:40) | 7th Workshop on Geometry and Machine Learning Organizers: Hubert Wagner and Jeff M. Phillips (ends at 6:20 PM (18:20)) |
Workshop on Parameterized Algorithms for Geometric Problems Organizers: Sayan Bandyapadhyay, William Lochet, and Jie Xue |
| 5:00 PM (17:00) | Chao Chen with Xiaoling Hu, and Dimitris Samaras Topological Representation and Topological Uncertainty for Biomedical Image Analysis |
Huck Bennett Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all l_p Norms |
| 5:20 PM (17:20) | Shreyas Samaga with Cheng Xin, Soham Mukherjee, and Tamal K. Dey GRIL: A 2-parameter Persistence Based Vectorization for Machine Learning |
|
| 5:40 PM (17:40) | Mathijs Wintraecken with Hana Dal Poz Kourimska and Andre Lieutier Improved stability results for the medial axis |
|
| 5:50 PM (17:50) | Maarten Loeffler Removing Popular Faces in Curve Arrangements by Inserting one more Curve |
|
| 6:00 PM (18:00) | Reyan Ahmed with Mithun Ghosh, Kwang-Sung Jun, and Stephen Kobourov Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search |
|
Friday, June 16, 2023—Comp-Geometers' 60thBD-Fest
(website)
| Time | Event | Location |
|---|---|---|
| 8:00 AM (08:00) | Breakfast | SU 2.905/Artemis |
| 9:00 AM–10:15 AM (09:00–10:15) | Talk Session I | ECSS 2.102 |
| 9:00 AM (09:00) | Micha Sharir Pankaj, Boris, and Tamal: The first 35 years |
ECSS 2.102 |
| 9:25 AM (09:25) | Jonathan Shewchuk Factoring a Matrix into Linear Neural Networks |
ECSS 2.102 |
| 9:50 AM (09:50) | Esther Ezra Intersection searching and polynomial partitioning |
ECSS 2.102 |
| 10:15 AM (10:15) | Anecdote Time + Coffee Break | ECSW Annex Atrium |
| 11:00 AM–12:15 PM (11:00–12:15) | Talk Session II | ECSS 2.102 |
| 11:00 AM (11:00) | Chandrajit Bajaj SoCG of Machine Learning (Tribute to Boris, Pankaj, Tamal) |
ECSS 2.102 |
| 11:25 AM (11:25) | Sariel Har-Peled Some Hops Through Work with Boris and Pankaj |
ECSS 2.102 |
| 11:50 AM (11:25) | Siu-Wing Cheng Snapshots of My Works with Tamal |
ECSS 2.102 |
| 12:15 AM–1:00 PM (12:15–13:00) | Anecdote Time + Well Wishes | ECSS 2.102 |