CG Week 2020 is online because of the COVID-19 pandemic
All Monday Tuesday Wednesday Thursday Friday All All

Monday, June 22, 2020

14:00-14:10 Welcome
14:10-14:40 SoCG Best Paper — Chairs: Sergio Cabello & Danny Chen, Host: Nicolas Grelier
Convex Hulls of Random Order Types [doi]
Xavier Goaoc and Emo Welzl
14:40-14:50 Break
Session Mo-S-1A
Chair: Günter Rote, Host: Saeed Ilchi
Session Mo-S-1B
Chair: Primož Škraba, Host: Hung P. Hoang
14:50-15:10 Barycentric Cuts through a Convex Body [doi]
Zuzana Patáková, Martin Tancer , and Uli Wagner
The Reeb Graph Edit Distance Is Universal [doi]
Ulrich Bauer , Claudia Landi, and Facundo Memoli
15:10-15:30 A Quasi-polynomial Algorithm for Well-spaced Hyperbolic TSP [doi]
Sándor Kisfaludi-Bak 
Dimensionality Reduction for k-Distance Applied to Persistent Homology [doi]
Shreya Arya, Jean-Daniel Boissonnat, Kunal Dutta , and Martin Lotz
15:30-15:50 Flipping Geometric Triangulations on Hyperbolic Surfaces [doi]
Vincent Despré , Jean-Marc Schlenker, and Monique Teillaud
Relative Persistent Homology [doi]
Nelli Blaser and Morten Brun 
15:50-16:00 Break
16:00-17:00 Invited Talk — Chair: Sergio Cabello, Host: Manuel Wettstein
Discrete Developable Surfaces: Theory and Fabrication of 3D Shapes from 2D Sheets
Olga Sorkine-Hornung
17:00-17:10 Break
Session Mo-Y-1A
Chair: Michael Kerber, Host: Bernd Gärtner
Session Mo-Y-1B
Chair: Erin Chambers, Host: Nicolas Grelier
17:10-17:30 On The Number of Compositions of Two Polycubes
Andrei Asinowski, Gill Barequet, Gil Ben-Shachar , Martha Carolina Osegueda, and Günter Rote
We provide tight bounds on the minimum and maximum possible numbers of compositions of two polycubes, either when each is of size n, or when their total size is 2n, in two and higher dimensions.
An Enumeration and Isotopy Classification of Oriented Textile Structures
Matt Bright  and Vitaliy Kurlin
We have developed a first method for encoding isotopy classes of links embedded in a thickened torus by 1-dimensional strings of symbols. We have designed a linear time algorithm to determine which codes give rise to realizable textiles in the plane. The new encoding and realizability algorithm have allowed us to enumerate for the first time all oriented single component textiles up to three crossings.
17:30-17:50 Samples Using Geometric Counting Lower Bounds
Sepideh Aghamolaei  and Mohammad Ghodsi
Using Szemerédi–Trotter theorem for bounding the number of incidences between n points and m lines, we compute the sample size required for achieving that bound. We prove a similar result for the size of the dominating set of a graph and use it to find a sample for k-center.
Simplicial Oversampling: Accounting for the Higher-order Relations in Data Improves the Solution of the Imbalanced Learning Problem
Oleg Kachan 
SMOTE is the established geometric approach to random oversampling to balance classes in the imbalanced classes learning problem, followed by many extensions. Its main idea is to introduce synthetic data points in the minor class with each new point being the convex combination of an existing data point and one of its k-nearest neighbors. This could be viewed as a sampling from the edges of a geometric neighborhood graph.
We propose a generalization of the sampling approach, thus sampling from the maximal simplices (with respect to an ambient space) of the clique complex of a neighborhood graph. That is, a position of a new point is defined by the barycentric coordinates with respect to a simplex spanned by an arbitrary number of data points being sufficiently close. We evaluate the generalized technique and conclude that it outperforms the original SMOTE.
17:50-18:10 On the Power of Concatenation Arguments
Gill Barequet, Gil Ben-Shachar, and Martha Carolina Osegueda 
We present several concatenation arguments, and show their applications to setting bounds on the growth constants of polyominoes and polycubes, and to families (e.g., trees) of polyominoes and polycubes whose enumerating sequences are pseudo sub- or super-multiplicative.
Optimizing Embeddings using Persistence
Jasna Urbančič  and Primož Škraba
This work looks to optimize Takens-type embeddings of time series using persistent (co)homology. The motivation is to assume that an input time series exhibits periodic, quasi-periodic, or recurrent behaviour, then use continuous optimization to find good embeddings. Here we provide a practical approach to finding good embeddings with indications as to possible theoretical questions and directions which arise.
18:10-18:30 Hardness of Approximation for Some Covering Problems
Sima Hajiaghaei 
In Geometric Set Cover the goal is to find a minimum sized cover for a given set of points in the plane by a family of given objects. This is a fundamental problem which has been studied for over 30 years. It has long been known to be NP-hard and was shown to be APX-hard by Chan and Grant in 2014. We study this and related problems here.
First, we consider the problem of Boxes Class Cover: points are given in two colors, red and blue, and the goal is to find a minimum number of axis-aligned rectangles that cover all the blue points but no reds. This problem is introduced for the first time in a paper in 2012 by Bereg et al., who showed the problem is NP-hard. No hardness of approximation result has been shown for this problem. Here for the first time we show that the problem is APX-hard.
We also study Red-Blue Geometric Set Cover, where the points are given in two colors, red and blue, and the goal is to find a family of given axis-aligned rectangles that cover all the blue points with the minimum number of reds. Chan in 2014 showed that the version of this problem where objects are axis-aligned rectangles is also NP-hard. Here for the first time we show that the problem is APX-hard. Moreover, we show that Red-Blue Geometric Set Cover is NP-hard to approximate within o(log n) factor of optimum, where the covering objects are convex objects and n is the number of blue points.
Quantifying barley morphology using Euler characteristic curves
Erik Amezquita , Michelle Quigley, Tim Ophelders, Elizabeth Munch, and Daniel H. Chitwood
Shape is foundational to biology. Observing and documenting shape has fueled biological understanding, and from this perspective, it is also a type of data.
The vision of topological data analysis, that data is shape and shape is data, will be relevant as biology transitions into a data-driven era where meaningful interpretation of large data sets is a limiting factor. We focus on quantifying the morphology of barley spikes and seeds using topological descriptors based on the Euler characteristic and relate the output back to genetic information.
18:30-18:40 Break
18:40-19:40 Discussion Forum — Chair: Bettina Speckmann, Host: Michael Hoffmann
Two Topics: Submission Regulations (allow submission by PC members, anonymize submissions) & Remote Participation

Tuesday, June 23, 2020

UTC+2 Session Tu-S-2A
Chair: Frank Staals, Host: Nicolas El Maalouly
Session Tu-S-2B
Chair: Mikkel Abrahamsen, Host: Meghana M. Reddy
14:00-14:20 A Generalization of Self-improving Algorithms [doi]
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin , and Man Ting Wong
Removing Connected Obstacles in the Plane Is FPT [doi]
Eduard Eiben  and Daniel Lokshtanov
14:20-14:40 How to Find a Point in the Convex Hull Privately [doi]
Haim Kaplan, Micha Sharir, and Uri Stemmer 
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs [doi]
Fedor Fomin, Daniel Lokshtanov, Fahad Panolan , Saket Saurabh, and Meirav Zehavi
14:40-15:00 On \beta-Plurality Points in Spatial Voting Games [doi]
Boris Aronov, Mark de Berg , Joachim Gudmundsson, and Michael Horton
The Parameterized Complexity of Guarding Almost Convex Polygons [doi]
Akanksha Agrawal , Kristine V.K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi
15:00-15:20 No-dimensional Tverberg Theorems and Algorithms [doi]
Aruni Choudhary  and Wolfgang Mulzer
Euclidean TSP in Narrow Strips [doi]
Henk Alkema  , Mark de Berg, and Sándor Kisfaludi-Bak
15:20-15:30 Break
15:30-16:00 Media Sneak Preview — Chair: Satyan Devadoss, Host: Manuel Wettstein
  • The Spiroplot App      [doi] Casper van Dommelen, Marc van Kreveld , and Jérôme Urhausen
  • Coordinated Particle Relocation with Global Signals and Local Friction      [doi] Victor Baez, Aaron Becker, Sándor Fekete , and Arne Schmidt
  • Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata      [doi] Amira Abdel-Rahman, Aaron Becker, Daniel E. Biediger, Kenneth Cheung, Sándor Fekete , Neil Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Mike Yannuzzi
  • How to Make a CG Video      [doi] Aaron Becker and Sándor Fekete 
  • Covering Rectangles by Disks: The Video      [doi] Sándor Fekete , Phillip Keldenich, and Christian Scheffer
  • Step-by-Step Straight Skeletons          [doi] Günther Eder , Martin Held, and Peter Palfrader
  • Computing animations of linkages with rotational symmetry      [doi] Sean Dewar, Georg Grasegger , and Jan Legerský
  • Hiding Sliding Cubes: Why Reconfiguring Modular Robots is Not Easy      [doi] Tillmann Miltzow, Irene Parada , Willem Sonke, Bettina Speckmann, and Jules Wulms
  • Dots & Polygons      [doi] Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken , Jolan Rensen, and Leo van Schooten
  • Designing Art Galleries      [doi] Toon van Benthem, Kevin Buchin, Irina Kostitsyna, and Stijn Slot 
  • Plane-filling trails      [doi] Herman Haverkort 
  • Visual Demo of Discrete Stratified Morse Theory        [doi] Youjia Zhou , Kevin Knudson, and Bei Wang
16:00-16:10 Break
Session Tu-S-3A
Chair: Mickaël Buchet, Host: Julia Schulte
Session Tu-S-3B
Chair: Zuzana Patáková, Host: Daniel Bertschinger
16:10-16:30 Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations [doi]
David Cohen-Steiner, André Lieutier, and and Julien Vuillamy  
Almost-monochromatic Sets and the Chromatic Number of the Plane [doi]
Nora Frankl  , Tamas Hubai, and Dömötör Pálvölgyi
16:30-16:50 On Rectangle-decomposable 2-parameter Persistence Modules [doi]
Magnus Botnan, Vadim Lebovici  , and Steve Oudot
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons [doi]
Eyal Ackerman, Balázs Keszegh , and Günter Rote
16:50-17:10 Edge Collapse and Persistence of Flag Complexes [doi]
Jean-Daniel Boissonnat and Siddharth Pritam  
Dense Graphs Have Rigid Parts [doi]
Orit E. Raz  and Jozsef Solymosi
17:10-17:20 Break
Session Tu-S-4A
Chair: Dan Halperin, Host: Hung P. Hoang
Session Tu-S-4B
Chair: Hubert Wagner, Host: Tim Taubner
17:20-17:40 On the Planar Two-center Problem and Circular Hulls [doi]
Haitao Wang 
Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis [doi]
Abhishek Rathod  
17:40-18:00 Dynamic Geometric Set Cover and Hitting Set [doi]
Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue 
GPU-Accelerated Computation of Vietoris-Rips Persistence Barcodes [doi]
Simon Zhang  , Mengbai Xiao, and Hao Wang
18:00-18:20 Fast Algorithms for Geometric Consensuses [doi]
Sariel Har-Peled and Mitchell Jones  
Finding Closed Quasigeodesics on Convex Polyhedra [doi]
Erik D. Demaine , Adam Hesterberg , and Jason S. Ku 
18:20-18:30 Break
Session Tu-Y-2A
Chair: Tamal Dey, Host: Saeed Ilchi
Session Tu-Y-2B
Chair: Evanthia Papadopoulou, Host: Meghana M. Reddy
18:30-18:50 Minimal Delaunay triangulations of hyperbolic surfaces
Matthijs Ebbens , Hugo Parlier, and Gert Vegter
Motivated by recent work on Delaunay triangulations of hyperbolic surfaces, we consider the minimal number of vertices of such triangulations. In particular, we will show that every hyperbolic surface has a Delaunay triangulation where edges are given by distance paths and where the number of vertices grows linearly as function of the genus g. We will show that the order of this bound is attained for some families of surfaces. Finally, we will give an example showing that the Ω(√g) lower bound in the more general case of topological surfaces is tight for hyperbolic surfaces as well.
Decomposition and Partition Algorithms for Tissue Dissection
Maike Buchin and Leonie Selbach 
We consider the decomposition of simple polygons and the partition of graphs under specific constraints. Our research is motivated by an application in the field of protein diagnostics, that is processing tissue samples for laser capture mircodissection. For the dissection to be successful the region of interest has to satisfy certain constraints in size and morphology. We consider different algorithmic approaches for the segmentation of these regions.
18:50-19:10 Which Integrable Projection is Which?
Josh Vekhter  and Etienne Vouga
Given a piecewise constant vector field v on a manifold m, we begin with the question of when it can be expressed as the gradient of some scalar field s, in which case we say that this field is discretely integrable. When v is not integrable, one can then begin considering projections from v to the space of integrable fields. In this document we note that there are a number of related notions of integrable projection defined in the literature. We present a framework in which we generalize three of these notions to simplicial complexes in arbitrary dimension, and which shows promise as a computational tool for solving otherwise combinatorially hard problems in computational topology.
Computing relevant subtrajectory bundles faster
Erfan Hosseini Sereshgi  and Carola Wenk
The ubiquitous use of smartphones and other GPS-enabled devices leads to vast amounts of tracking data being collected on a regular basis. But generally, processing large GPS trajectory data requires bundling portions of the trajectories together; this is referred to as sub-trajectory clustering. Since this is a multi-criteria optimization problem, there are many potential bundles of interest and it is unclear which ones to choose. Recently an approach was proposed for identifying so-called relevant bundles of sub-trajectories. We provide a faster algorithm for computing such relevant bundles, by employing a combination of exponential and binary search. This yields a runtime improvement of a linear factor over the previous exhaustive search algorithm.
19:10-19:30 Finding Surfaces in 2-Dimnesional Simplicial Complexes with Bounded Treewidth 1-Skeletons
Mitchell Black  and Amir Nayyeri
We present an algorithm for finding a subcomplex K' of a simplicial complex K such that K' is a surface with specified boundary, genus, and orientability. This algorithm is parameterized by the treewidth of the 1-skeleton of the simplicial complex K and the genus of the surface K'. Our algorithm is linear in the number of vertices of K if the treewidth of the 1-skeleton of K and the genus of K' are constant. Otherwise, our algorithm is polynomial if the treewidth of the 1-skeleton of K is constant.
Topology Aware Morphological Operations
Erin Chambers, Ellen Gasparovic, Tao Ju, David Letscher, Hannah Schreiber , and Dan Zeng
This work in progress aims to give a solution of the homological simplification problem in ℝ2 which is also geometrically nice.

Wednesday, June 24, 2020

UTC+2 Session We-S-5A
Chair: Kevin Buchin, Host: Daniel Bertschinger
Session We-S-5B
Chair: Sylvain Lazard, Host: Julia Schulte
14:00-14:20 Dynamic Distribution-sensitive Point Location [doi]
Siu-Wing Cheng and Man-Kit Lau 
The Next 350 Million Knots [doi]
Benjamin A. Burton 
14:20-14:40 Four-Dimensional Dominance Range Reporting in Linear Space [doi]
Yakov Nekrich 
On Implementing Straight Skeletons: Challenges and Experiences [doi]
Günther Eder, Martin Held, and Peter Palfrader 
14:40-15:00 Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles [doi]
Monika Henzinger, Stefan Neumann  , and Andreas Wiese
Parallel Computation of Alpha Complexes for Biomolecules [doi]
Talha Bin Masood , Tathagata Ray, and Vijay Natarajan
15:00-15:20 Minimum Scan Cover with Angular Transition Costs [doi]
Sándor Fekete, Linda Kleist, and Dominik Krupke  
Robust Anisotropic Power-functions-based Filtrations for Clustering [doi]
Claire Brécheteau 
15:20-15:30 Break
15:30-16:30 CG Challenge — Chair: Sándor Fekete, Host: Tim Taubner
  • Welcome & Overview Sándor Fekete
  • Technical comments Dominik Krupke
  • Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions [doi]
    Günther Eder, Martin Held, Stefan de Lorenzo , and Peter Palfrader
  • Computing Low-Cost Convex Partitions for Planar Point Sets Based on a Memetic Approach [doi]
    Laurent Moalic , Dominique Schmitt, Julien Lepagnot, and Julien Kritter
  • Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming [doi]
    Da Wei Zheng , Jack Spalding-Jamieson, and Brandon Zhang
  • Questions & Discussion
  • Award Ceremony
  • Outlook
16:30-16:40 Break
Session We-S-6A
Chair: Marc Glisse, Host: Patrick Schnider
Session We-S-6B
Chair: David Mount, Host: Nicolas El Maalouly
16:40-17:00 Persistent Homology Based Characterization of the Breast Cancer Immune Microenvironment: A Feasibility Study [doi]
Andrew Aukerman, Mathieu Carrière , Chao Chen, Kevin Gardner, Raúl Rabadán, and Rami Vanguri
Almost Sharp Bounds on the Number of Discrete Chains in the Plane [doi]
Nora Frankl   and Andrey Kupavskii
17:00-17:20 Intrinsic Topological Transforms via the Distance Kernel Embedding [doi]
Clément Maria, Steve Oudot, and Elchanan Solomon 
The ε-t-Net Problem [doi]
Noga Alon, Bruno Jartoux , Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky
17:20-17:40 Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes [doi]
Glencora Borradaile, William Maxwell  , and Amir Nayyeri
Incidences between Points and Curves with Almost Two Degrees of Freedom [doi]
Micha Sharir  and Oleg Zlydenko
17:40-18:00 An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology [doi]
Tamal K. Dey, Tianqi Li  , and Yusu Wang
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets [doi]
Boris Aronov, Esther Ezra , and Micha Sharir
18:00-18:20 Efficient Approximation of the Matching Distance for 2-parameter Persistence [doi]
Michael Kerber  and Arnur Nigmetov
Faster Approximation Algorithms for Geometric Set Cover [doi]
Timothy M. Chan and Qizheng He  
18:20-18:30 Break
18:30-20:00 Business Meeting — Chair: Monique Teillaud, Host: Michael Hoffmann

Thursday, June 25, 2020

UTC+2 Session Th-S-7A
Chair: Elena Arseneva, Host: Manuel Wettstein
Session Th-S-7B
Chair: Irina Kostitsyna, Host: Saeed Ilchi
14:00-14:20 Empty Squares in Arbitrary Orientation among Points [doi]
Sang Won Bae and Sang Duk Yoon 
Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips) [doi]
Uli Wagner and Emo Welzl 
14:20-14:40 Geometric Secluded Paths and Planar Satisfiability [doi]
Kevin Buchin, Valentin Polishchuk , Leonid Sedov, and Roman Voronov
Holes and Islands in Random Point Sets [doi]
Martin Balko, Manfred Scheucher , and Pavel Valtr
14:40-15:00 Homotopic Curve Shortening and the Affine Curve-Shortening Flow [doi]
Sergey Avvakumov and Gabriel Nivasch 
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages [doi]
Michael A. Bekos, Giordano Da Lozzo, Svenja Griesbach  , Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou
15:00-15:20 The Topological Correctness of PL-approximations of Isomanifolds [doi]
Jean-Daniel Boissonnat and Mathijs Wintraecken 
Extending Drawings of Graphs to Arrangements of Pseudolines [doi]
Alan Arroyo , Julien Bensmail, and R. Bruce Richter
15:20-15:30 Break
15:30-16:30 Invited Talk — Chair: Danny Chen, Host: Hung P. Hoang
Geometric Statistics for Computational Anatomy
Xavier Pennec
16:30-16:40 Break
Session Th-S-8A
Chair: Elizabeth Munch, Host: Patrick Schnider
Session Th-S-8B
Chair: Emo Welzl, Host: Nicolas Grelier
16:40-17:00 Worst-case Optimal Covering of Rectangles by Disks [doi]
Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich  , Christian Scheffer, and Sahil Shah
Long Alternating Paths Exist [doi]
Wolfgang Mulzer  and Pavel Valtr
17:00-17:20 Homotopy Reconstruction via the Cech Complex and the Vietoris-Rips Complex [doi]
Jisu Kim , Jaehyeok Shin, Frédéric Chazal, Alessandro Rinaldo, and Larry Wasserman
Radon Numbers Grow Linearly [doi]
Dömötör Pálvölgyi 
17:20-17:40 Persistence of the Conley Index in Combinatorial Dynamical Systems [doi]
Tamal K. Dey, Marian Mrozek, and Ryan Slechta  
Bounding Radon Number via Betti Numbers [doi]
Zuzana Patáková 
17:40-18:00 A Toroidal Maxwell-Cremona-Delaunay Correspondence [doi]
Jeff Erickson and Patrick Lin  
Bounded VC-dimension Implies the Schur-Erdős Conjecture [doi]
Jacob Fox, János Pach, and Andrew Suk 
18:00-18:10 Break
Session Th-S-9A
Chair: Tim Ophelders, Host: Bernd Gärtner
Session Th-S-9B
Chair: Jinhui Xu, Host: Tim Taubner
18:10-18:30 A Near-linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread [doi]
Kyle Fox and Jiashuai Lu  
The Stretch Factor of Hexagon-Delaunay Triangulations [doi]
Michael Dennis, Ljubomir Perković , and Duru Türkoğlu
18:30-18:50 Further Results on Colored Range Searching [doi]
Timothy M. Chan, Qizheng He  , and Yakov Nekrich
Algorithms for Subpath Convex Hull Queries and Ray-shooting among Segments [doi]
Haitao Wang 
18:50-19:10 Terrain Visibility Graphs: Persistence Is Not Enough [doi]
Safwa Ameer, Matt Gibson, Erik Krohn, Sean Soderman  , and Qing Wang
Sketched MinDist [doi]
Jeff M. Phillips  and Pingfan Tang
19:10-19:30 Elder-rule-staircodes for Augmented Metric Spaces [doi]
Chen Cai, Woojin Kim  , Facundo Memoli, and Yusu Wang
k-Median Clustering under Discrete Fréchet and Hausdorff Distances [doi]
Abhinandan Nath  and Erin Taylor
19:30-19:50 Combinatorial Properties of Self-Overlapping Curves and Interior Boundaries [doi]
Parker Evans  , Brittany Terese Fasy, and Carola Wenk


Friday, June 26, 2020

UTC+2 Session Fr-Y-3A
Chair: Anne Driemel, Host: Daniel Bertschinger
Session Fr-Y-3B
Chair: Michael Kerber, Host: Meghana M. Reddy
14:00-14:20 Practical volume estimation of polytopes by billiard trajectories and a new annealing schedule
Apostolos Chalkis , Ioannis Z. Emiris, and Vissarion Fisikopoulos
We study the problem of estimating the volume of convex polytopes. Our algorithm is based on Multiphase Monte Carlo (MMC) methods and our main contributions include:
  1. a new uniform sampler employing Billiard Walk (BW) for the first time in volume computation,
  2. a new simulated annealing schedule, generalizing existing MMC by making use of adaptive convex bodies which fit to the input, thus drastically reducing the required number of iterations.
Extensive experiments show that our algorithm requires fewer oracle calls and arithmetic operations in total, when compared to existing practical algorithms for volume approximation. We offer an open-source, optimized C++ implementation, and analyze its performance. Our code tackles problems intractable so far, offering the first implementation to scale up to dimension d=100 for V-polytopes and zonotopes, and for d in the thousands for H-polytopes in less than one hour.
Duality in Persistent Homology of Images
Adelie Garin , Teresa Heiss, Kelly Maggs, and Bea Bleibe and Vanessa Robins
We derive the relationship between the persistent homology barcodes of two dual filtered CW complexes. Applied to greyscale digital images, we obtain an algorithm to convert barcodes between the two different (dual) topological models of pixel connectivity.
14:20-14:40 Robust Boolean operations on polygons
Shengtan Mao  and Jack Snoeyink
We detail an implementation of regularized Boolean operations (union, intersection, difference) on two polygonal regions. It is based on an optimal red/blue segment intersection algorithm that requires only double the input precision. We carefully define predicates so that we do not need to define shared endpoints or overlapping segments as degeneracies requiring special handling but can fold them into the general case. We do not address the geometric rounding of intersection points (which may require more than double precision) back to input precision since such rounding must be application-specific.
Understanding the Topology and the Geometry of the Persistence Diagram Space via Optimal Partial Transport
Vincent Divol  and Theo Lacombe
Despite the obvious similarities between the metrics used in topological data analysis and those of optimal transport, an explicit optimal transport based formalism to study persistence diagrams and similar topological descriptors has yet to come. By considering the space of persistence diagrams as a measure space, and by observing that its metrics can be expressed as optimal partial transport problems, we introduce a generalization of persistence diagrams, namely Radon measures supported on the upper half plane. Such measures naturally appear in topological data analysis when considering continuous representations of persistence diagrams (e.g. persistence surfaces) but also as limits for laws of large numbers on persistence diagrams or as expectations of probability distributions on the persistence diagrams space. This formalism allows us to prove topological properties of this new space, which will also hold for the closed subspace of persistence diagrams.
This bridge between optimal transport and persistence diagram metrics allows us to address various problems that naturally arise when dealing with persistence diagram, both in theory and in applications.
First, we provide a characterization of convergence in the space of persistence diagram (with respect to the diagram metrics) in terms of vague convergence of measures. This result provides a powerful tool to study convergence and continuity properties in the space of persistence diagrams; in particular it allows us to give an exhaustive characterization of continuous linear representations of persistence diagrams, a common tool used when incorporating persistence diagrams in machine learning pipeline.
Second, this formalism allows us to prove new results regarding persistence diagrams in a random setting, as it enables to manipulate some continuous such as expected persistence diagrams (that are not standard persistence diagrams) and to prove convergence rates and stability results in this context.
Finally, an optimal transport-based formalism has huge strengths in applications. Indeed, modern tools routinely used in computational optimal transport can be straightforwardly adapted to persistence diagrams metrics, allowing to estimate efficiently distances, barycenters, or quantizations of persistence diagrams to name a few.
This presentation is based on the preprint [Divol & Lacombe, 2019].
14:40-15:00 Voronoi-based similarity distances between arbitrary crystal lattices
Vitaliy Kurlin and Marco Michele Mosca 
This document develops new distance metrics based on Voronoi cell of a crystal lattice to compare crystal structures. Crystal structure prediction methods generate many simulated crystals used for materials discovery or drug design of which many of them may be similar to each other. Therefore, we may need to filter datasets by removing similar structures that can be time consuming for different computations. The proposed distances are invariant under rigid motions and can be used for clustering and visualizing datasets of crystals.
Recovering the homology of immersed manifolds
Raphaël Tinarrage 
Given a sample of an abstract manifold immersed in some Euclidean space, we describe a way to recover the singular homology of the original manifold. It consists in estimating its tangent bundle—seen as subset of another Euclidean space—in a measure theoretic point of view, and in applying measure-based filtrations for persistent homology.
The construction we propose is consistent and stable, and does not involve the knowledge of the dimension of the manifold. In order to obtain quantitative results, we introduce the normal reach, which is a notion of reach suitable for an immersed manifold.
15:00-15:10 Break
15:10-16:20 Awards: Test of Time & Best Student Presentation — Chair: Pankaj Agarwal, Host: Julia Schulte
  • Test of Time Award Introduction Pankaj Agarwal
  • Epsilon-Nets and Simplex Range Queries David Haussler and Emo Welzl
  • Applications of Random Sampling in Computational Geometry, II Kenneth L. Clarkson and Peter W. Shor
  • Test of Time Award Outlook Pankaj Agarwal
  • Best Student Presentation Award Sergio Cabello and Danny Chen
16:20-16:30 Break
Workshop: Computational Aspects of Learning and Processing Metrical Data
Chair: Anastasios Sidiropoulos, Host: Ahad N. Zehmakan
16:30-17:10 Metric Learning: Overview and New Directions
Brian Kulis
Metric learning is a supervised machine learning problem concerned with learning a task-specific distance function from supervised data. It has found numerous applications in problems such as similarity search, clustering, and ranking. Much of the foundational work in this area focused on the class of so-called Mahalanobis metrics, which may be viewed as Euclidean distances after linear transformations of the data. This talk will describe two recent directions in metric learning: deep metric learning and divergence learning. The first replaces the linear transformations with the output of a neural network, while the second considers a broader class than Mahalanobis metrics. I will discuss some of my recent work along both of these fronts, as well as ongoing attempts to combine these approaches together using a novel framework called deep divergences.
17:10-17:35 Scalable Nearest Neighbor Search for Optimal Transport
Ilya Razenshteyn
The Optimal Transport (aka Wasserstein) distance is an increasingly popular similarity measure for structured data domains, such as images or text documents. This raises the necessity for fast nearest neighbor search with respect to this distance, a problem that poses a substantial computational bottleneck for various tasks on massive datasets. In this talk, I will discuss fast tree-based approximation algorithms for searching nearest neighbors with respect to the Wasserstein-1 distance. I will start with describing a standard tree-based technique, known as QuadTree, which has been previously shown to obtain good results. Then I'll introduce a variant of this algorithm, called FlowTree, and show that it achieves better accuracy, both in theory and in practice. In particular, the accuracy of FlowTree is in line with previous high-accuracy methods, while its running time is much faster.
The talk is based on a joint work with Arturs Backurs, Yihe Dong, Piotr Indyk and Tal Wagner. The paper can be found here and the code here.
17:35-18:00 Recovering metric structure behind perturbed networks
Yusu Wang
Graphs and network data are ubiquitous across a wide range of scientific and application domains. Often in practice, an input graph can be considered as a noisy observed snapshot of a hidden true graph (which could be the 1-skeleton of a hidden domain). In this talk, I will advocate the following network model: We assume that there is a true graph G∗ which is a certain proximity graph for points sampled from a hidden domain X, and thus captures the geometry of X. The observed graph G is an Erdos-Renyi type perturbed version of G∗; in particular, edges not in G∗ can be added with probability p, while edges in G∗ can be deleted with probability q. We also call such an observed graph a ER-pertubed RGG (random geometric graph). We are interested both in recovering the original shortest path metric of G∗ from the noisy observed graph G, and in understanding properties of such ER-perturbed RGG. The talk will focus on the metric recovery problem. We will show how the Jaccard index and the edge-clique number can both be used to recover the shortest path metric in G∗ within a constant factor, but with different pros and cons.
This talk is based on joint work with M. Kahle, S. Parthasarathy, D. Sivakoff, and M. Tian.
18:00-18:25 Controlling the space projection in Mahalanobis distance learning with respect to specific instances
Amaury Habrard
Mahalanobis distance learning is one of the most famous framework of metric learning. It can be interpreted as finding a good projection of the data where some Euclidean-based distances can be used to perform efficiently some classification or clustering tasks. In this talk, I will show that this space can be controlled by applying some regression constraints over specific chosen instances. I will also discuss some recent work for designing/learning good metrics in the context of imbalanced data classification where the idea is to adapt the metric with respect to the type of instances used to compare a query point.
18:25-18:50 Optimal terminal dimensionality reduction in Euclidean space
Jelani Nelson
The Johnson-Lindenstrauss lemma states that for any X ⊂ ℝd with |X| = n and for any ε, there exists a map f:X → ℝm for m = O(log n / ε2) such that: for all x ∈ X, for all y ∈ X, (1-ε) |x - y|2 ≤ |f(x) - f(y)|2 \leq (1+ε) |x - y|2. We show that this statement can be strengthened. In particular, the above claim holds true even if "for all y ∈ X" is replaced with "for all y ∈ ℝd ".
Joint work with Shyam Narayanan.
18:50-19:15 Generalized Metric Repair
Ben Raichel
Many modern data analysis algorithms either assume or are considerably more efficient if the distances between the data points satisfy a metric. However, as real data sets are noisy, they often do not possess this fundamental property. To address this issue, here we consider the generalized metric repair problem (GMR). Given a positively weighted connected graph, G, call a cycle in G broken if it contains an edge whose weight is greater than the sum of the weights of the other edges in the cycle. In GMR the goal is to modify as few edge weights as possible such that no broken cycles remain. We argue any hitting set of the broken cycles determines a solution, leading to both hardness and approximation results. Specifically, we give 1) an approximation preserving reduction from MULTICUT, 2) for any constant c a fixed parameter tractable algorithm for c-chordal graphs, and 3) approximations parameterized on measures of how badly the cycles are broken. Moreover, when the graph G is a complete graph, we give an O(OPT1/3) approximation, where OPT is the optimal solution size.
19:15-19:40 On metric embeddings, shortest path decompositions and face cover of planar graphs
Arnold Filtser
We will discuss the problem of low distortion embeddings of shortest-path metrics of weighted graphs into ℓ₁. Shortest path decomposition (SPD) is a hierarchical partition of a graph using shortest paths. Every (weighted) path graph has an SPD of depth 1. A graph G has an SPD of depth k if after removing some shortest path P, every connected component in G ∖ P has an SPD of depth k-1. We present a novel metric embedding technique based on SPD. We will show that any graph with SPD of depth k, can be embedded into ℓ₁ with distortion O(√{k}). Afterwards, we will show how to use this result in order to embed a planar graph with γ faces into ℓ₁ with distortion O(√{log γ}). We will also discuss implications to the sparsest cut problem.