CG Week 2021 Program, EDT (UTC-4)
For those who are going to give a talk at CG Week 2021, please sign the following release agreement form and return it to socg-21@buffalo.edu at your earliest time.
A PDF version of the program is available here.
SoCG 2021 Conference Proceedings is available here.
: presenter, : student
Monday, June 7, 2021
| SoCG Best Paper Chairs: Kevin Buchin and Éric Colin de Verdière,
Assistent: Minghua Wang,
Virtual Room: A Lower Bounds for Semialgebraic Range Searching and Stabbing Problems Peyman Afshani and Pingan Cheng |
||||||
| |
SoCG 1A Chair: Jean Cardinal Assistant: Chunwei Ma Virtual Room: A |
SoCG 1B Chair: Brittany Fasy Assistant: Minghua Wang Virtual Room: B |
||||
| Packing Squares into a Disk with Optimal Worst-Case Density Sándor Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist and Christian Scheffer |
Sketching Persistence Diagrams Donald Sheehy and Siddharth Sheth |
|||||
| Online Packing to Minimize Area or Perimeter Mikkel Abrahamsen and Lorenzo Beretta |
Computing Zigzag Persistence on Graphs in Near-Linear Time Tamal K. Dey and Tao Hou |
|||||
| |
On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem Arindam Khan, Arnab Maiti , Amatya Sharma and Andreas Wiese |
A Sparse Delaunay Filtration
Don Sheehy |
||||
| |
Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More Waldo Gálvez , Fabrizio Grandoni, Arindam Khan, Diego Ramírez-Romero and Andreas Wiese |
Computing the multicover bifiltration René Corbet , Michael Kerber, Michael Lesnick and Georg Osang |
||||
| Efficient generation of rectangulations via permutation languages Arturo Merino and Torsten Mütze |
A family of metrics from the truncated smoothing of Reeb graphs Erin Chambers, Elizabeth Munch and Tim Ophelders |
|||||
Media Sneak Preview Chairs:Valentin Polishchuk, Assistant: Minghua Wang, Virtual Room: A
|
||||||
| YRF 1A Chair: Marcel Roeloffzen Assistant: Chunwei Ma Virtual Room: A |
YRF 1B Chair: Haitao Wang Assistant: Ziyun Huang Virtual Room: B |
YRF 1C Chair: Jie Xue Assistant: Minghua Wang Virtual Room: C |
||||
| Perfect Matchings with Crossings Oswin Aichholzer, Ruy Fabila-Monroy, Philipp Kindermann, Irene Parada, Rosna Paul , Daniel Perz, Patrick Schnider and Birgit Vogtenhuber 1-minute video |
Independent Hyperplanes in Oriented Paving Matroids Lamar Chidiac and Winfried Hochstättler 1-minute video |
Using Generalized Heegaard Splittings in Computational 3-Manifold Topology Kristóf Huszár 1-minute video |
||||
| Plane Matchings in Simple Drawings of Complete Graphs Oswin Aichholzer, Alfredo Garcia, Javier Tejel, Birgit Vogtenhuber and Alexandra Weinberger 1-minute video |
Edge-unfolding nearly flat prismatoids Manuel Radons |
Homotopical decompositions of simplicial and Vietoris-Rips complexes Wojciech Chachólski, Alvin Jin , Martina Scolamiero and Francesca Tombari |
||||
| Untangling Almost Outerplanar Drawing Sujoy Bhore, Guangping Li , Martin Nöllenburg, Ignaz Rutter and Hsiang-Yun Wu 1-minute video |
A Geometric Approach to Papillae Identification in 3D Meshes Rayna Andreeva , Anwesha Sarkar and Rik Sarkar 1-minute video |
Realizing Persistent Homology by Subcomplexes Magnus Bakke Botnan and Pepijn Edwin Robert Roos Hoefgeest |
||||
| Algorithms For Max Cut on Unit Interval and Laminar Interval Graphs Utkarsh Joshi , Rahul Saladi and Josson Thoppil |
On the range of two-distance graphs Péter Ágoston 1-minute video |
Efficient two-parameter persistence computation via cohomology Fabian Lenzen, Ulrich Bauer and Michael Lesnick |
||||
| YRF 2A Chair: Jie Xue Assistant: Chunwei Ma Virtual Room: A |
YRF 2B Chair: Haitao Wang Assistant: Ziyun Huang Virtual Room: B |
YRF 2C Chair: Don Sheehy Assistant: Minghua Wang Virtual Room: C |
||||
| An exact optimal algorithm for the discrete median line segment problem in the plane? Ovidiu Daescu and Ka Yaw Teo |
Package delivery using handoffs among collaborating heterogeneous agents Kien Huynh and Joseph Mitchell 1-minute video |
On the adjacency structures of planar point-set triangulations Logan Graham 1-minute video |
||||
| The Visibility Center of a Polygon Anna Lubiw and Anurag Murty Naredla 1-minute video |
Moving Robots One by One is Hard Tzvika Geft and Dan Halperin 1-minute video |
Connecting 3-manifold triangulations with semimonotonic sequences of bistellar flips Benjamin A. Burton and Alexander He 1-minute video |
||||
| Large Perimeter Objects Surrounded by 1.5D Terrains Vahideh Keikha 1-minute video |
Enumerating All Convex Polyhedra Glued from Squares in Polynomial Time Stefan Langerman, Nicolas Potvin and Boris Zolotov 1-minute video |
Triangulations of Exotic 4-Manifolds Rhuaidi Burke and Benjamin Burton 1-minute video |
||||
| Discussion Forum,
Chair: Michael Hoffmann Assistant: Christine Belus, Virtual Room: Discussion Room |
||||||
Tuesday, June 8, 2021
| Invited Talk Chair: Éric Colin de Verdière Assistant: Chunwei Ma, Virtual Room: A On Laplacians Robert Ghrist |
||||||
| |
SoCG 2A Chair: Pankaj Agarwal Assistant: Chunwei Ma Virtual Room: A |
SoCG 2B Chair: Stefan Felsner Assistant: Minghua Wang Virtual Room: B |
||||
| Throwing a sofa through the window Dan Halperin , Micha Sharir and Itay Yehuda |
Complexity of Maximum Cut on Interval Graphs Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee and Bodhayan Roy |
|||||
| On Ray Shooting for Triangles in 3-Space and Related Problems Esther Ezra and Micha Sharir |
Adjacency Graphs of Polyhedral Surfaces Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz , Birgit Vogtenhuber and Alexander Wolff |
|||||
| |
Stabbing Convex Bodies with Lines and Flats Sariel Har-Peled and Mitchell Jones |
Polygon-Universal Graphs
Tim Ophelders , Ignaz Rutter, Bettina Speckmann and Kevin Verbeek |
||||
| |
Faster Algorithms for Largest Empty Rectangles and Boxes Timothy M. Chan |
Classifying Convex Bodies by their Contact and Intersection Graphs Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen and Peter M. R. Rasmussen |
||||
| Escaping the Curse of Spatial Partitioning: Matchings with Low Crossing Numbers and their Applications Monika Csikos and Nabil H. Mustafa |
Combinatorial Resultants in the Algebraic Rigidity Matroid Goran Malic and Ileana Streinu |
|||||
| Minisymposium on Computational Topology 1 Chair:Ulrich Bauer, Arnaud de Mesmay, and Uli Wagner Assistant: Minghua Wang Virtual Room: A |
Workshop on Geometry &Machine Learning 1 Chairs: Hu Ding and Jeff Phillips Assistant: Chunwei Ma Virtual Room: B |
|||||
| Invited talk: Simplicial approximation to CW complexes in practice Raphaël Tinarrage |
Invited Talk: Geometry and Landscape for Nonconvex Functions Rong Ge |
|||||
| Optimal Algorithms for Range Searching over Multi-Armed Bandits Siddharth Barman, Ramakrishnan Krishnamurthy, Saladi Rahul |
||||||
| Invited talk: Topology and Geometry of Random Polyominoes Erika Roldan |
Geometric Disentanglement by Random Convex Polytopes Michael Joswig, Marek Kaluba, Lukas Ruff |
|||||
| Obstructing Classification Via Projection Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jerome Urhausen, Kevin Verbeek |
||||||
| Minisymposium on Computational Topology 2 Chair: Ulrich Bauer, Arnaud de Mesmay, and Uli Wagner Assistant: Minghua Wang Virtual Room: A |
Workshop on Geometry &Machine Learning 2 Chairs: Hu Ding and Jeff Phillips Assistant: Chunwei Ma Virtual Room: B |
|||||
| Classification based on Topological Data Analysis Rolando Kindelan, Jose Frias, Mauricio Cerda, Nancy Hitschfeld |
||||||
| Invited talk: Rational homotopy theory and decidability of the extension problem Fedor Manin |
Fuzzy Simplicial Networks: A TopologyInspired Model to Improve Task Generalization in Few-shot Learning Henry Kvinge, Zachary New, Nico Courts, Jung H. Lee, Lauren A. Phillips, Courtney D. Corley, Aaron Tuor, Andrew Avila, Nathan O. Hodas |
|||||
| Geometric Message Passing Schemes with Cell Complex Neural Networks Mustafa Hajij, Kyle Istvan, Ghada Zamzmi |
||||||
| Training Neural Networks is ER-Complete Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow |
||||||
| Invited talk: Minimum weight disk triangulations and fillings Yuval Peled |
Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo Apostolos Chalkis, Vissarion Fisikopoulos, Marios Papachristou, Elias Tsigaridas |
|||||
| Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification Alejandro Flores-Velazco and David M. Mount |
||||||
Wednesday, June 9, 2021
| |
SoCG 3A Chair: Anne Driemel Assistant: Chunwei Ma Virtual Room: A |
SoCG 3B Chair: Ulrich Bauer Assistant: Minghua Wang Virtual Room: B |
||||
| Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation Karl Bringmann and André Nusser |
A stepping-up lemma for topological set systems Xavier Goaoc, Andreas Holmsen and Zuzana Patáková |
|||||
| Approximating the (Continuous) Fréchet Distance Connor Colombe and Kyle Fox |
Optimal bounds for the colorful fractional Helly theorem Denys Bulavka , Afshin Goodarzi and Martin Tancer |
|||||
| |
Chasing Puppies: Mobile Beacon Routing on Closed Curves Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Till Miltzow, Jérôme Urhausen , Jordi Vermeulen and Giovanni Viglietta |
Sunflowers in set systems of bounded dimension
Jacob Fox, Janos Pach and Andrew Suk |
||||
| |
SoCG 4A Chair: Michiel Smid Assistant: Chunwei Ma Virtual Room: A |
SoCG 4B Chair: Diane Souvaine Assistant: Minghua Wang Virtual Room: B |
||||
| Reliable Spanners for Metric Spaces Sariel Har-Peled, Manor Mendel and Dániel Oláh |
Colouring polygon visibility graphs and their generalizations James Davies, Tomasz Krawczyk, Rose McCarty and Bartosz Walczak |
|||||
| On the Edge Crossings of the Greedy Spanner David Eppstein and Hadi Khodabandeh |
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem Simon Hengeveld and Till Miltzow |
|||||
| |
Light Euclidean Steiner Spanners in the Plane Sujoy Bhore and Csaba Toth |
No Krasnoselskii Number for General Sets
Chaya Keller and Micha A. Perles |
||||
| |
CG Challenge - Chair: Sándor Fekete, Assistant: Chunwei Ma, Virtual Room: A
|
|||||
| |
Workshop on Geometric and Topological Methods in Biomedical Image Analysis 1 Chairs: Bei Wang and Chao Chen Assistant: Chunwei Ma Virtual Room: A |
Workshop on Geometry and Mobility 1 Chairs: Jiaxin Ding, Abhirup Ghosh, and Rik Sarkar Assistant: Minghua Wang Virtual Room: B |
||||
| |
Invited Talk: ManifoldNet: A Deep Neural Network for Manifold-Valued Data with Applications Baba C. Vemuri |
Invited Talk: Data structures for proximity searching under the Fréchet distance
Anne Driemel |
||||
| |
Invited Talk: Contributed topics discussion session: applications, datasets and open problems
|
|||||
| |
Invited Talk: Geometric Data Alignment of Biomedical Signals and Shapes Shantanu Joshi |
|
||||
| |
Business Meeting Chair: Michael Hoffmann Assistant: Christine Belus, Virtual Room: Discussion Room |
|||||
Thursday, June 10, 2021
| |
Invited Talk Chair: Kevin Buchin Assistant: Minghua Wang, Virtual Room: A 3SUM and related problems in fine-grained complexity Virginia Vassilevska Williams |
|||||
| |
SoCG 5A Chair: Guilherme Dias Da Fonseca Assistant: Chunwei Ma Virtual Room: A |
SoCG 5B Chair: Amir Nayyeri Assistant: Minghua Wang Virtual Room: B |
||||
| Approximate Range Counting under Differential Privacy Ziyue Huang and Ke Yi |
Strong Hanani-Tutte for the Torus Radoslav Fulek , Marcus Schaefer and Michael Pelsmajer |
|||||
| More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time Timothy M. Chan and Qizheng He |
Density Fingerprint of a Periodic Point Set Herbert Edelsbrunner, Teresa Heiss , Vitaliy Kurlin, Philip Smith and Mathijs Wintraecken |
|||||
| |
A Parallel Batch-Dynamic Data Structure for the Closest Pair Problem Yiqiu Wang , Shangdi Yu, Yan Gu and Julian Shun |
Minimal Delaunay triangulations of hyperbolic surfaces
Matthijs Ebbens , Hugo Parlier and Gert Vegter |
||||
| |
Approximate Nearest-Neighbor Search for Line Segments Ahmed Abdelkader and David Mount |
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries
Erin Chambers, Francis Lazarus, Arnaud De Mesmay and Salman Parsa |
||||
| |
Near Neighbor Search via Efficient Average Distortion Embeddings Deepanshu Kush , Aleksandar Nikolov and Haohua Tang |
Parameterized Complexity of Quantum Knot Invariants
Clément Maria |
||||
| |
Minisymposium on Computational Topology 3 Chairs:Ulrich Bauer, Arnaud de Mesmay, and Uli Wagner Assistant: Minghua Wang Virtual Room: A |
Workshop on Geometry and Mobility 2 Chairs: Jiaxin Ding, Abhirup Ghosh, and Rik Sarkar Assistant: Chunwei Ma Virtual Room: B |
||||
| |
Orientation-Preserving Vectorized Distance Between Curves
Jeff Phillips and Hasan Pourmahmood-Aghababa |
|||||
| |
Invited talk: High-performance computing with knots, 3-manifolds and 4-manifolds Ben Burton |
Route Reconstruction from Traffic Flow via Representative Trajectories
Bram Custers, Wouter Meulemans, Bettina Speckmann and Kevin Verbeek |
||||
| |
A Game Theoretic Approach to Transport Planning
Alastair Maxwell and Rik Sarkar |
|||||
| |
Exact Vertex-Aligned Sub-Trajectory Proximity Searches under the Continuous Fréchet Distance
Joachim Gudmundsson, Martin P. Seybold and John Pfeifer |
|||||
| |
Invited talk: Unknot recognition in quasipolynomial time Marc Lackenby |
Toward Persistent Homology for Moving Points
Ondrej Draganov, Farid Karimipour and Herbert Edelsbrunner |
||||
| |
|
|||||
| |
Minisymposium on Computational Topology 4 Chairs:Ulrich Bauer, Arnaud de Mesmay, and Uli Wagner Assistant: Minghua Wang Virtual Room: A |
Workshop on Geometry and Mobility 3 Chairs: Jiaxin Ding, Abhirup Ghosh, and Rik Sarkar Assistant: Chunwei Ma Virtual Room: B |
||||
| |
Invited talk: The Directional Transform: From Theory to Practice
Elizabeth Munch |
Invited Talk: Cyber-Physical Systems for Large-Scale On-demand Delivery
Desheng Zhang |
||||
| |
Invited talk: Discrete constructions and geometry driven collapses for shape reconstruction Dominique Attali |
Panel Discussion: Future research in geometry of mobility | ||||
Friday, June 11, 2021
| |
SoCG 6A Chair: Antoine Vigneron Assistant: Chunwei Ma Virtual Room: A |
SoCG 6B Chair: Jonathan Spreer Assistant: Minghua Wang Virtual Room: B |
||||
| On rich points and incidences with restricted sets of lines in 3-space Micha Sharir and Noam Solomon |
An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons Haitao Wang |
|||||
| Sublinear average-case shortest paths in weighted unit-disk graphs Adam Karczmarz, Jakub Pawlewicz and Piotr Sankowski |
Counting Cells of Order-k Voronoi Tessellations in R^3 with Morse Theory Ranita Biswas, Sebastiano Cultrera di Montesano , Herbert Edelsbrunner and Morteza Saghafian |
|||||
| |
An integer programming formulation using convex polygons for the convex partition problem Hadrien Cambazard and Nicolas Catusse |
Restricted Constrained Delaunay Triangulations
Marc Khoury and Jonathan Shewchuk |
||||
| |
Characterizing Universal Reconfigurability of Modular Pivoting Robot Hugo Akitaya, Erik D. Demaine, Andrei Gonczi , Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korter, Jayson Lynch, Irene Parada and Vera Sacristán |
Tracing isomanifolds in $\mathbb{R}^d$ in time polynomial in $d$ using Coxeter-Freudenthal-Kuhn triangulations
Jean-Daniel Boissonnat, Siargey Kachanovich and Mathijs Wintraecken |
||||
| |
SoCG 7A Chair: Jeff Phillips Assistant: Chunwei Ma Virtual Room: A |
SoCG 7B Chair: Bernd Gärtner Assistant: Minghua Wang Virtual Room: B |
||||
| On rich lenses in planar arrangements of circles and related problems Esther Ezra, Orit E. Raz, Micha Sharir and Joshua Zahl |
Geometric algorithms for sampling the flux space of metabolic networks Apostolos Chalkis , Vissarion Fisikopoulos, Elias Tsigaridas and Haris Zafeiropoulos |
|||||
| Rectilinear Steiner Trees in Narrow Strips Henk Alkema and Mark de Berg |
Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast Aditi Laddha and Santosh Vempala |
|||||
| |
Two-sided Kirszbraun Theorem Arturs Backurs, Sepideh Mahabadi , Konstantin Makarychev and Yury Makarychev |
On Undecided LP, Clustering and Active Learning
Stav Ashur and Sariel Har-Peled |
||||
| |
Orientation preserving Maps of the Square Grid Imre Bárány, Attila Pór and Pavel Valtr |
|
||||
| |
Awards: Test of Time & Best Student Presentation – Chair: Pankaj Agarwal, Assistant: Minghua Wang, Virtual Room: A
|
|||||
| |
Workshop on Geometric and Topological Methods in Biomedical Image Analysis 2 Chairs: Bei Wang and Chao Chen Assistant: Chunwei Ma Virtual Room: A |
|||||
| |
Invited Talk: Topological Analysis of Immunofluorescence Images Mathieu Carrière |
|||||
| |
Invited Talk: Signed Distance Persistent Homology of Tubular Shapes Anna Song |
|||||
| |
Invited Talk: Surface-Based Connectivity Integration Zhengwu Zhang |
|||||
| |
Invited Talk: Radiomics and Pathomics in Precision Medicine – Why Domain Still Matters Prateek Prasanna |
|||||