Program

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
Student Presentation Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber
Sparse 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) Student Presentation 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) Student Presentation 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) Student Presentation Richard Qi and Benjamin Qi
New Approximation Algorithms for Touring Regions
11:30 AM (11:30) Student Presentation 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) Student Presentation Á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) Video Presentation Student Presentation Ulrich Bauer, Michael Lesnick, and Fabian Lenzen
Efficient 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
Video Presentation Student 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) Video Presentation 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) Student Presentation Corentin Lunel and Arnaud de Mesmay
A structural approach to tree decompositions of knots and spatial graphs
Student Presentation 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) Student Presentation Benjamin Burton and Alexander He
Finding large counterexamples by selectively exploring the Pachner graph
Student Presentation 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
Student Presentation 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) Student Presentation 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
Video Presentation 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
Student Presentation 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) Video Presentation Alex McCleary
Interleavings and Couplings
Video Presentation 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) Video Presentation 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) Student Presentation J. Andreas Bærentzen, Rasmus E. Christensen, Emil T. Gæde, and Eva Rotenberg
Multilevel Skeletonization Using Local Separators
Student Presentation Michael Hoffmann and Meghana M. Reddy
The Number of Edges in Maximal 2-planar Graphs
9:20 AM (09:20) Student Presentation 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) Video Presentation Student Presentation 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) Student Presentation Helena Bergold, Stefan Felsner, and Manfred Scheucher
An extension theorem for signotopes
Student Presentation 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) Student Presentation 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) Student Presentation Andrew Suk and Ji Zeng
On higher dimensional point sets in general position
Student Presentation Auguste Gezalyan and David Mount
Voronoi Diagrams in the Hilbert Metric
11:30 AM (11:30) Video Presentation Student Presentation 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
Student Presentation 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) Student Presentation 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)
  • Sándor Fekete: Welcome and Overview
  • Mikkel Abrahamsen, William Bille Meyling, and André Nusser: Constructing Concise Convex Covers via Clique Covers
  • Guilherme Dias da Fonseca: Shadoks Approach to Convex Covering
  • Questions and Discussion
  • Award Ceremony
  • Outlook: The Challenge Problem 2024
3:40 PM (15:40) Media Expo (Session Chair: Siddharth Sheth; ECSS 2.102)
  • Alexandra Camero and Ileana Streinu: Interactive 2D Periodic Graphs (live software demonstration)
  • Video Presentation Richard Berger, Vincent Ha, David Kratz, Michael Lin, Jeremy Moyer, and Chris Tralie: Godzilla Onions: A Skit And Applet for Explaining Euclidean Half-Plane Fractional Cascading
  • Video Presentation Oliver Chubet, Paul Macnichol, Parth Parikh, Donald Sheehy, and Siddharth Sheth: Greedy Permutations and Finite Voronoi Diagrams
  • Video Presentation Don Sheehy: The Sum of Squares in Polycubes
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
Video Presentation 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) Video Presentation 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)
  • Pankaj Agarwal: Opening Remarks
  • Video Presentation Herbert Edelsbrunner, Leonidas J. Guibas, and Micha Sharir: The complexity of many faces in arrangements of lines and of segments
  • Video Presentation Monique Teillaud and Andreas Fabri: on behalf of the CGAL Project
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
Video Presentation 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
Video Presentation 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) Video Presentation 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