CHANGES IN THE PROGRAM

DAY 3, Wednesday: During the 16:45 Coffee break: Multimedia: Meet the creators (in front of GM).

DAY 3, Wednesday, Combinatorial Geometry 2: N. Mustafa's talk cancelled, Open session moved earlier. See program below.

BIRTHDAY: N. Amenta's talk cancelled, Jeff Erickson is giving a talk. See program below.

Invited Speakers

András Máthé, University of Warwick

Jo Wood, City University of London

Information

List of accepted SoCG papers

Detailed CG Week Program (pdf)

Booklet: Detailed CG Week Program with SoCG Abstracts (pdf)

Almost all talks, events will be held at Eötvös University's (ELTE) downtown campus in two buildings very close to each other: Gólyavár (main lecture rooms) and Building B (room 172). Address: Budapest, Múzeum krt. 6-8.

The receptions and the Business Meeting are at Rényi Institute, a three-minute walk from the main venue.

See map here.

Schedule

Lecture rooms:

GM: Gólyavár main lecture hall

GS: Gólyavár smaller room

B172: Building B room B172.

  • Sunday
DAY 0, June 10, Sunday.
  • Monday
DAY 1, June 11, Monday.
9:10-
10:30		 Session 1a. Room GM.
Chair: Michael Kerber		 Session 1b. Room GS.
Chair: Dömötör Pálvölgyi
Herbert Edelsbrunner and Georg Osang: The Multi-Cover Persistence of Euclidean Balls [DOI] [+]
 Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar and Kasturi Varadarajan: Capacitated Covering Problems in Geometric Spaces [DOI] [+]
Magnus Bakke Botnan and Håvard Bakke Bjerkevik: Computational Complexity of the Interleaving Distance [DOI] [+]
 Tanmay Inamdar and Kasturi Varadarajan: On Partial Covering For Geometric Set Systems [DOI] [+]
Frédéric Chazal and Vincent Divol: The Density of Expected Persistence Diagrams and its Kernel Based Estimation [DOI] [+]
 Édouard Bonnet and Panos Giannopoulos: Orthogonal Terrain Guarding is NP-Complete [DOI] [+]
Mickaël Buchet and Emerson G. Escolar: Realization of Indecomposable Persistence Modules of Arbitrarily Large Dimension [DOI] [+]
 Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman and David Rappaport: An Optimal Algorithm to Compute the Inverse Beacon Attraction Region [DOI] [+]
10:30-
11:00		 Coffee break
11:00-
11:30		 Session 2. Room GM Chair: Michael Kerber. Best paper by Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer and Uli Wagner: Shellability is NP-Complete [DOI] [+]
11:30-
12:10		 Multimedia Sneak Previews. Room GM
12:10-
13:00		 YRF and Workshop Fast Forward. Room GM
13:00-
14:30		 Lunch break
14:30-
16:00		 YRF1
Room GM.		 Machine Learning
Room GS.		 Fine Grained
Room B172.
14:30: Fugacci, Kerber, Manet: Topology-aware Terrain Simplification
14:45: Hoog, Kreveld, Meulemans, Verbeek, Wulms: Topological stability of kinetic k-centers
15:00: Ophelders, Sonke, Speckmann, Verbeek: A KDS for Discrete Morse-Smale Complexes
15:15: Kerber, Nigmetov: Spanners for Topological Summaries
15:30: Corbet, Fugacci, Kerber, Landi, Wang: A Kernel for Multi-parameter Persistence
15:45: Ölsböck: The Dynamic Wrap Complex 		14:30-15:15: Bei Wang: Stratification Learning with Computational Topology: Overview, Challenges, and Opportunities
15:15-16:00: Brittany Fasy: Road Network Analysis with Topological Data Analysis 		14:30: Opening words
14:35-15:25: Michał Pilipczuk: Parameterized algorithms for planar packing and covering problems using Voronoi diagrams
15:30-15:50: Sándor Kisfaludi-Bak: Cube Wiring and its Applications
16:00-
16:30		 Coffee break
16:30-
18:00		 YRF1
Room GM.		 Machine Learning
Room GS.		 Fine Grained starting at 16:20
Room B172.
16:30: Giunti, Chacholski, Landi: Classification of filtered chain complexes
16:45: Pritam, Boissonnat, Pareek: Strong Collapse for Persistence
17:00: Schreiber, Maria: Morse Complexes for Zigzag Persistent Homology
17:15: Krishnamoorthy, Saul, Wang: Stitch Fix for Mapper
17:30: Schenfisch, Fasy: Curvature Estimates of Point Clouds as a Tool in Quantitative Prostate Cancer Classification 		16:30-17:15: Melanie Schmidt: Practical Theory for Geometric Center Based Clustering
17:15-18:00: Ioannis Z. Emiris: Randomized Projections for Geometric Search in High Dimension 		16:20-17:10: Jean Cardinal: The geometry of 3SUM, k-SUM, and related problems
17:15-17:35: Pritam Bhattacharya: Approximation and Inapproximability of Guarding Polygons
17:40-18:00: Benjamin Burton: Parameterised complexity for knots and manifolds -- where to from here
  • Tuesday
DAY 2, June 12, Tuesday.
9:00-
10:30		 YRF2
Room GM.		 Combinatorial Geometry 1
Room GS.		 Computational Topology 1
Room B172.
9:00: Çaǧırıcı, Roy: Maximum clique of disks in convex position
9:15: Berg, Bodlaender, Kisfaludi-Bak, Marx, Zanden: An Algorithmic Framework for Geometric Intersection Graphs
9:30: Damásdi: Conical partitions of point sets
9:45: Keikha, Kerkhof, Kreveld, Kostitsyna, Löffler, Staals, Urhausen, Vermeulen, Wiratma: Convex Partial Transversals of Planar Regions
10:00: Frankl: Large equilateral sets in subspaces of $\ell_\infty^n$
10:15: Xue, Li, Rahul, Janardan: Searching for the closest-pair in a convex polygonal translate 		9:00-9:30: Csaba Tóth: Exchange operations on noncrossing spanning trees
9:30-10:00: Jean Cardinal: Topological Drawings of Complete Bipartite Graphs
10:00-10:30: Radoslav Fulek: $\mathbb Z_2$-embeddings and Tournaments 		9:00-9:25: Tamal Dey: Nerves can only kill, also serially!
9:30-9:55: Ziga Virk: Persistence of geodesic spaces
10:00-10:25: Sara Kalisnik: Learning algebraic varieties from samples
10:30-
11:00		 Coffee break
11:00-
12:30		 YRF2
Room GM.		 Combinatorial Geometry 1
Room GS.		 Computational Topology 1
Room B172.
11:00: Eder, Held: Weighted Voronoi Diagrams in the L-inf Norm
11:15: Jin, Huang: A technique for polygon inclusion problem
11:30: Abdelkader: Delone Sets for Convex Bodies
11:45: Buchin, Hulshof, Ol'ah: $O(k)$-robust spanners in one dimension
12:00: Crombez, Fonseca, Gérard: Peeling Digital Potatoes
12:15: Bhattacharya, Ghosh, Pal: Constant Approximation Algorithms for Guarding Simple Polygons using Edge and Perimeter Guards 		11:00-11:30: Shakhar Smorodinsky: $k$-Conflict-Free Coloring of String Graphs
11:30-12:00: Adrian Dumitrescu: A Product Inequality for Extreme Distances
12:00-12:30: Andrey Kupavskii: Tilings with noncongruent triangles 		11:00-11:25: Lori Ziegelmeier: A complete characterization of the 1-dimensional intrinsic Cech persistence diagrams for metric graphs
11:30-11:55: Yusu Wang: Gromov-Hausdorff and Interleaving Distances for Trees
12:00-12:25: Mathijs Wintraecken: Triangulating stratified manifolds: a reach comparison theorem
12:30-
14:00		 Lunch break
14:00-
15:00		 Session 3. Room GM Invited talk by
Jo Wood: Stories are not Just Words. Or How Visualization Helps us to Explain, Reason, Explore and Remember
15:10-
16:10		 Session 4a. Room GM.
Chair: Benjamin Raichel		 Session 4b. Room GS.
Chair: Bei Wang
Ioannis Emiris and Ioannis Psarros: Products of Euclidean Metrics and Applications to Proximity Questions among Curves [DOI] [+]
 Kristóf Huszár, Jonathan Spreer and Uli Wagner: On the Treewidth of Triangulated $3$-Manifolds [DOI] [+]
Marc Van Kreveld, Maarten Löffler and Lionov Wiratma: On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance [DOI] [+]
 Jonathan Spreer and Stephan Tillmann: The Trisection Genus of Standard Simply Connected PL $4$-Manifolds [DOI] [+]
Olivier Devillers, Sylvain Lazard and William Lenhart: 3D Snap Rounding [DOI] [+]
 Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh and Mathijs Wintraecken: Local Criteria for Triangulation of Manifolds [DOI] [+]
16:10-
16:30		 Coffee break
16:30-
17:50		 Session 5a. Room GM.
Chair: David Mount		 Session 5b. Room GS.
Chair: Wouter Meulemans
Timothy M. Chan and Dimitrios Skrepetos: Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs [DOI] [+]
 Zdenek Dvorak, Petr Hlineny and Bojan Mohar: Structure and Generation of Crossing-Critical Graphs [DOI] [+]
Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski and Florian Sikora: QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs [DOI] [+]
 Fabian Klute and Martin Nöllenburg: Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts [DOI] [+]
A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid and Shakhar Smorodinsky: Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs [DOI] [+]
 János Pach and Géza Tóth: A Crossing Lemma for Multigraphs [DOI] [+]
Kevin Buchin, Jeff Phillips and Pingfan Tang: Approximating the Distribution of the Median and other Robust Estimators on Uncertain Data [DOI] [+]
 Radoslav Fulek and Jan Kynčl: The $\mathbb{Z}_2$-Genus of Kuratowski Minors [DOI] [+]
  • Wednesday
DAY 3, June 13, Wednesday.
9:00-
10:20		 Session 6a. Room GM.
Chair: Benjamin Raichel		 Session 6b. Room GS.
Chair: Csaba Tóth
Roee David, Karthik C. S. and Bundit Laekhanukit: On the Complexity of Closest Pair via Polar-Pair of Point-Sets [DOI] [+]
 Bruce Reed, Janos Pach and Yelena Yuditsky: Almost All String Graphs are Intersection Graphs of Plane Convex Sets [DOI] [+]
Jie Xue, Yuan Li, Saladi Rahul and Ravi Janardan: New Bounds on Range Closest-Pair Problems [DOI] [+]
 Chaya Keller and Shakhar Smorodinsky: From a $(p,2)$-Theorem to a Tight $(p,q)$-Theorem [DOI] [+]
Thijs Laarhoven: Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors [DOI] [+]
 Leonardo Martínez-Sandoval, Edgardo Roldán-Pensado and Natan Rubin: Further Consequences of the Colorful Helly Hypothesis [DOI] [+]
Ryo Ashida and Kotaro Nakagawa: $\widetilde{O}(n^{1/3})$-Space Algorithm for the Grid Graph Reachability Problem [DOI] [+]
 Balázs Keszegh: Coloring Intersection Hypergraphs of Pseudo-Disks [DOI] [+]
10:20-
10:45		 Coffee break
10:45-
11:45		 Session 7a. Room GM.
Chair: Siu-Wing Cheng		 Session 7b. Room GS.
Chair: Jeff Erickson
Joseph O'Rourke: Edge-Unfolding Nearly Flat Convex Caps [DOI] [+]
 Adam Brown and Bei Wang: Sheaf-Theoretic Stratification Learning [DOI] [+]
Malte Milatz: Random Walks on Polytopes of Constant Corank [DOI] [+]
 Kevin Knudson and Bei Wang: Discrete Stratified Morse Theory: A User’s Guide [DOI] [+]
Herbert Edelsbrunner, Žiga Virk and Hubert Wagner: Smallest Enclosing Spheres and Chernoff Points in Bregman Geometry [DOI] [+]
 Tamal Dey, Jiayuan Wang and Yusu Wang: Graph Reconstruction by Discrete Morse Theory [DOI] [+]
11:45-
12:00		 Short break
12:00-
13:00		 Session 8a. Room GM.
Chair: Bettina Speckmann		 Session 8b. Room GS.
Chair: Dömötör Pálvölgyi
Timothy M. Chan: Tree Drawings Revisited [DOI] [+]
 Tamal Dey and Cheng Xin: Computing Bottleneck Distance for 2-D Interval Decomposable Modules [DOI] [+]
Arthur van Goethem and Kevin Verbeek: Optimal Morphs of Planar Orthogonal Drawings [DOI] [+]
 Wai Ming Tai and Jeff Phillips: Near-Optimal Coresets of Kernel Density Estimates [DOI] [+]
Yifei Jin, Jian Li and Wei Zhan: Odd Yao-Yao Graphs may not be Spanners [DOI] [+]
 Bruno Jartoux and Nabil H. Mustafa: Optimality of Geometric Local Search [DOI] [+]
13:00-
14:30		 Lunch break. For committee members: Lunch at XO bistro from 13:05.
14:30-
15:30		 Session 9. Room GM Invited talk by
András Máthé: Circle squaring and other combinatorial problems in geometric measure theory
15:30-
16:45		 YRF3
Room GM.		 Educational Forum
Room GS.		 Computational Topology 2
Room B172.
15:30: Held, Lorenzo: Spiral-Like Paths on Triangulated Terrains
15:45: Vass, Tapolcai: Enumerating Maximal Regional Failures of Backbone Communication Networks in Near Linear Parametric Time
16:00: Löffler, Beck, Blum, Kryven, Zink: NP-completeness of Planar Steiner Orientation
16:15: Keller, Perles: Blockers for Simple Hamiltonian Paths in Convex Geometric Graphs of Odd Order
16:30: Asinowski, Barequet, Zheng: On $d$-D Polycubes with Small Perimeter Defect 		15:30-15:50: Sándor Fekete: IDEA instructions: Visualizing algorithms without words
15:50-16:10: Brittany Fasy: Teaching Computational (Geometry and) Topology
16:10-16:30: Jisu Kim: R package TDA for Topological Data Analysis
16:30-16:50: Efi Fogel: Teaching with CGAL Arrangements 		15:30-16:00: Omer Bobrowski: Homological percolation - the formation of large cycles
16:05-16:35: Anthea Monod: Statistical Inference for Persistent Homology via Rank Functions
16:45-
17:15		 Coffee break. Multimedia: Meet the creators (in front of GM)
17:15-
18:30		 Combinatorial Geometry 2
Room GM.		 Educational Forum
Room GS.		 Computational Topology 2
Room B172.
17:15-17:35: Bartosz Walczak: Towards double-logarithmic upper bounds on the chromatic number of triangle-free geometric intersection graphs
Nabil Mustafa: TALK CANCELLED
17:35- : Open ended open problem session 		17:15-17:30: Dave Millman and Joe Mitchell: Overview of CG/CT courses taught worldwide
17:30-18:30: Panel discussion: Franz Aurenhammer, Erin Chambers, Dan Halperin, David Mount, Joe O'Rourke 		17:15-17:45: Primoz Skraba: Random Structures, Persistence, and Stability
17:50-18:20: Discussion
  • Thursday
DAY 4, June 14, Thursday.
9:20-
10:20		 Session 10a. Room GM.
Chair: Luis Barba		 Session 10b. Room GS.
Chair: Jeff Erickson
Timothy M. Chan and Konstantinos Tsakalidis: Dynamic Planar Orthogonal Point Location in Sublogarithmic Time [DOI] [+]
 Anastasios Sidiropoulos, Kritika Singhal and Vijay Sridhar: Fractal Dimension and Lower Bounds for Geometric Problems [DOI] [+]
Pankaj Agarwal, Lars Arge and Frank Staals: Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon [DOI] [+]
 Michael Elkin and Ofer Neiman: Near Isometric Terminal Embeddings for Doubling Metrics [DOI] [+]
Sang Won Bae, Sergio Cabello, Otfried Cheong, Yoonsung Choi, Fabian Stehn and Sang Duk Yoon: The Reverse Kakeya Problem [DOI] [+]
 Timothy Carpenter, Anastasios Sidiropoulos, Daniel Lokshtanov, Fedor Fomin and Saket Saurabh: Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces [DOI] [+]
10:20-
10:45		 Coffee break
10:45-
11:45		 Session 11a. Room GM.
Chair: Marc van Kreveld		 Session 11b. Room GS.
Chair: Birgit Vogtenhuber
Eunjin Oh and Hee-Kap Ahn: Point Location in Dynamic Planar Subdivisions [DOI] [+]
 Oliver Roche-Newton: An Improved Bound for the Size of the Set $A/A+A$ [DOI] [+]
Ivor Hoog V.D., Elena Khramtcova and Maarten Löffler: Dynamic Smooth Compressed Quadtrees [DOI] [+]
 Boris Bukh, Xavier Goaoc, Alfredo Hubard and Matthew Trager: Consistent Sets of Lines with No Colorful Incidence [DOI] [+]
Eunjin Oh and Hee-Kap Ahn: Approximate Range Queries for Clustering [DOI] [+]
 Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman and Aurélien Ooms: Subquadratic Encodings for Point Configurations [DOI] [+]
11:45-
12:00		 Short break
12:00-
13:00		 Session 12a. Room GM.
Chair: Siu-Wing Cheng		 Session 12b. Room GS.
Chair: Bettina Speckmann
Haitao Wang and Jingru Zhang: An $O(n \log n)$-Time Algorithm for the $k$-Center Problem in Trees [DOI] [+]
 Andreas Haas: Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality [DOI] [+]
Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Ian Munro and Michiel Smid: Faster Algorithms for some Optimization Problems on Collinear Points [DOI] [+]
 Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed and Yann Vaxès: Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs [DOI] [+]
Sharath Raghvendra: Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line [DOI] [+]
 Ludovic Calès, Apostolos Chalkis, Ioannis Emiris and Vissarion Fisikopoulos: Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises [DOI] [+]
13:00-
14:30		 Lunch break
14:30-
15:30		 Session 13a. Room GM.
Chair: Luis Barba		 Session 13b. Room GS.
Chair: Csaba Tóth
Chih-Hung Liu: A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon [DOI] [+]
 Radoslav Fulek and Jan Kynčl: Hanani--Tutte for Approximating Maps of Graphs [DOI] [+]
Kolja Junginger and Evanthia Papadopoulou: Deletion in Abstract Voronoi Diagrams in Expected Linear Time [DOI] [+]
 Éric Colin de Verdière, Thomas Magnard and Bojan Mohar: Embedding Graphs into Two-Dimensional Simplicial Complexes [DOI] [+]
Ahmed Abdelkader, Chandrajit Bajaj, Mohamed Ebeida, Ahmed Mahmoud, Scott Mitchell, John Owens and Ahmad Rushdi: Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm [DOI] [+]
 Joshua Grochow and Jamie Tucker-Foltz: Computational Topology and the Unique Games Conjecture [DOI] [+]
15:30-
15:50		 Coffee break
15:50-
16:50		 Session 14a. Room GM.
Chair: David Mount		 Session 14b. Room GS.
Chair: Michael Kerber
Erik D. Demaine, Sándor Fekete, Phillip Keldenich, Henk Meijer and Christian Scheffer: Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch [DOI] [+]
 Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang and Lori Ziegelmeier: Vietoris-Rips and Cech Complexes of Metric Gluings [DOI] [+]
Victor Milenkovic, Elisha Sacks and Nabeel Butt: Table Based Detection of Degenerate Predicates in Free Space Construction [DOI] [+]
 Jean-Daniel Boissonnat, André Lieutier and Mathijs Wintraecken: The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces [DOI] [+]
Stefan Felsner, Linda Kleist, Torsten Mütze and Leon Sering: Rainbow Cycles in Flip Graphs [DOI] [+]
 Benjamin A. Burton: The HOMFLY-PT Polynomial is Fixed-Parameter Tractable [DOI] [+]
  • Friday
BIRTHDAY, June 15, Friday.
9:00-
9:05		 Opening remarks
9:10-
9:40		 Hermann Maurer, (video/scribe presentation), Graz Univ. of Technology
9:45-
10:15		 Micha Sharir, Tel Aviv Univ.
10:20-
10:50		 Coffee break
10:50-
11:20		 Jack Snoeyink, UNC Chapel Hill
11:25-
11:55		 János Pach, EPFL and Renyi Institute
12:00-
13:30		 Lunch break
13:30-
13:55		 Tiow Seng Tan, National Univ. Singapore
14:00-
14:25		 Dmitriy Morozov, Lawrence Berkeley National Lab
14:30-
14:55		 David Kirkpatrick, UBC
15:00-
15:25		 Jeff Erickson, U. Illinois Urbana-Champaign
15:30-
15:55		 Bernd Gärtner, ETH Zürich
16:00-
16:25		 József Solymosi, University of British Columbia
16:30-
17:15		 Remarks by three honorees
17:15-
18:00		 Champagne!