UTC+2  
14:0014:10  Welcome  
14:1014: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:4014:50  Break  
Session MoS1A Chair: Günter Rote, Host: Saeed Ilchi 
Session MoS1B Chair: Primož Škraba, Host: Hung P. Hoang 

14:5015: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:1015:30  A Quasipolynomial Algorithm for Wellspaced Hyperbolic TSP [doi] Sándor KisfaludiBak 
Dimensionality Reduction for kDistance Applied to Persistent Homology [doi] Shreya Arya, JeanDaniel Boissonnat, Kunal Dutta , and Martin Lotz 
15:3015:50  Flipping Geometric Triangulations on Hyperbolic Surfaces [doi] Vincent Despré , JeanMarc Schlenker, and Monique Teillaud 
Relative Persistent Homology [doi] Nelli Blaser and Morten Brun 
15:5016:00  Break  
16:0017:00 
Invited Talk — Chair: Sergio Cabello, Host: Manuel Wettstein Discrete Developable Surfaces: Theory and Fabrication of 3D Shapes from 2D Sheets Olga SorkineHornung 

17:0017:10  Break  
Session MoY1A Chair: Michael Kerber, Host: Bernd Gärtner 
Session MoY1B Chair: Erin Chambers, Host: Nicolas Grelier 

17:1017:30  On The Number of Compositions of Two Polycubes
Andrei Asinowski, Gill Barequet, Gil BenShachar , 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 1dimensional 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:3017: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 kcenter.

Simplicial Oversampling: Accounting for the Higherorder 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 knearest
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:5018:10  On the Power of Concatenation Arguments
Gill Barequet, Gil BenShachar, 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 supermultiplicative.

Optimizing Embeddings using Persistence
Jasna Urbančič and Primož Škraba
This work looks to optimize Takenstype embeddings of time series
using persistent (co)homology. The motivation is to assume that an
input time series exhibits periodic, quasiperiodic, 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:1018: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 NPhard and was shown to be APXhard 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 axisaligned 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 NPhard. No hardness of approximation result has been shown for this problem. Here for the first time we show that the problem is APXhard. We also study RedBlue Geometric Set Cover, where the points are given in two colors, red and blue, and the goal is to find a family of given axisaligned 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 axisaligned rectangles is also NPhard. Here for the first time we show that the problem is APXhard. Moreover, we show that RedBlue Geometric Set Cover is NPhard 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 datadriven 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:3018:40  Break  
18:4019:40 
Discussion Forum — Chair: Bettina Speckmann, Host: Michael Hoffmann Two Topics: Submission Regulations (allow submission by PC members, anonymize submissions) & Remote Participation 
UTC+2  Session TuS2A Chair: Frank Staals, Host: Nicolas El Maalouly 
Session TuS2B Chair: Mikkel Abrahamsen, Host: Meghana M. Reddy 
14:0014:20  A Generalization of Selfimproving Algorithms [doi] SiuWing Cheng, ManKwun Chiu, Kai Jin , and Man Ting Wong 
Removing Connected Obstacles in the Plane Is FPT [doi] Eduard Eiben and Daniel Lokshtanov 
14:2014:40  How to Find a Point in the Convex Hull Privately [doi] Haim Kaplan, Micha Sharir, and Uri Stemmer 
ETHTight Algorithms for Long Path and Cycle on Unit Disk Graphs [doi] Fedor Fomin, Daniel Lokshtanov, Fahad Panolan , Saket Saurabh, and Meirav Zehavi 
14:4015:00  On \betaPlurality 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:0015:20  Nodimensional Tverberg Theorems and Algorithms [doi] Aruni Choudhary and Wolfgang Mulzer 
Euclidean TSP in Narrow Strips [doi] Henk Alkema , Mark de Berg, and Sándor KisfaludiBak 
15:2015:30  Break  
15:3016:00 
Media Sneak Preview — Chair: Satyan Devadoss, Host: Manuel Wettstein


16:0016:10  Break  
Session TuS3A Chair: Mickaël Buchet, Host: Julia Schulte 
Session TuS3B Chair: Zuzana Patáková, Host: Daniel Bertschinger 

16:1016:30  Lexicographic Optimal Homologous Chains and Applications to Point Cloud Triangulations [doi] David CohenSteiner, André Lieutier, and and Julien Vuillamy 
Almostmonochromatic Sets and the Chromatic Number of the Plane [doi] Nora Frankl , Tamas Hubai, and Dömötör Pálvölgyi 
16:3016:50  On Rectangledecomposable 2parameter 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:5017:10  Edge Collapse and Persistence of Flag Complexes [doi] JeanDaniel Boissonnat and Siddharth Pritam 
Dense Graphs Have Rigid Parts [doi] Orit E. Raz and Jozsef Solymosi 
17:1017:20  Break  
Session TuS4A Chair: Dan Halperin, Host: Hung P. Hoang 
Session TuS4B Chair: Hubert Wagner, Host: Tim Taubner 

17:2017:40  On the Planar Twocenter Problem and Circular Hulls [doi] Haitao Wang 
Fast Algorithms for Minimum Cycle Basis and Minimum Homology Basis [doi] Abhishek Rathod 
17:4018:00  Dynamic Geometric Set Cover and Hitting Set [doi] Pankaj K. Agarwal, HsienChih Chang, Subhash Suri, Allen Xiao, and Jie Xue 
GPUAccelerated Computation of VietorisRips Persistence Barcodes [doi] Simon Zhang , Mengbai Xiao, and Hao Wang 
18:0018:20  Fast Algorithms for Geometric Consensuses [doi] Sariel HarPeled and Mitchell Jones 
Finding Closed Quasigeodesics on Convex Polyhedra [doi] Erik D. Demaine , Adam Hesterberg , and Jason S. Ku 
18:2018:30  Break  
Session TuY2A Chair: Tamal Dey, Host: Saeed Ilchi 
Session TuY2B Chair: Evanthia Papadopoulou, Host: Meghana M. Reddy 

18:3018: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:5019: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 GPSenabled 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 subtrajectory clustering. Since this is a multicriteria
optimization problem, there are many potential bundles of interest
and it is unclear which ones to choose. Recently an approach was
proposed for identifying socalled relevant bundles of
subtrajectories. 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:1019:30  Finding Surfaces in 2Dimnesional Simplicial Complexes with Bounded Treewidth 1Skeletons
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 1skeleton 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 1skeleton of K and the genus of K' are
constant. Otherwise, our algorithm is polynomial if the treewidth of
the 1skeleton 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.

UTC+2  Session WeS5A Chair: Kevin Buchin, Host: Daniel Bertschinger 
Session WeS5B Chair: Sylvain Lazard, Host: Julia Schulte 
14:0014:20  Dynamic Distributionsensitive Point Location [doi] SiuWing Cheng and ManKit Lau 
The Next 350 Million Knots [doi] Benjamin A. Burton 
14:2014:40  FourDimensional 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:4015: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:0015:20  Minimum Scan Cover with Angular Transition Costs [doi] Sándor Fekete, Linda Kleist, and Dominik Krupke 
Robust Anisotropic Powerfunctionsbased Filtrations for Clustering [doi] Claire Brécheteau 
15:2015:30  Break  
15:3016:30 
CG Challenge — Chair: Sándor Fekete, Host: Tim Taubner


16:3016:40  Break  
Session WeS6A Chair: Marc Glisse, Host: Patrick Schnider 
Session WeS6B Chair: David Mount, Host: Nicolas El Maalouly 

16:4017: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:0017:20  Intrinsic Topological Transforms via the Distance Kernel Embedding [doi] Clément Maria, Steve Oudot, and Elchanan Solomon 
The εtNet Problem [doi] Noga Alon, Bruno Jartoux , Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky 
17:2017: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:4018:00  An Efficient Algorithm for 1Dimensional (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:0018:20  Efficient Approximation of the Matching Distance for 2parameter Persistence [doi] Michael Kerber and Arnur Nigmetov 
Faster Approximation Algorithms for Geometric Set Cover [doi] Timothy M. Chan and Qizheng He 
18:2018:30  Break  
18:3020:00 
Business Meeting — Chair: Monique Teillaud, Host: Michael Hoffmann 
UTC+2  Session ThS7A Chair: Elena Arseneva, Host: Manuel Wettstein 
Session ThS7B Chair: Irina Kostitsyna, Host: Saeed Ilchi 
14:0014: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:2014: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:4015:00  Homotopic Curve Shortening and the Affine CurveShortening 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:0015:20  The Topological Correctness of PLapproximations of Isomanifolds [doi] JeanDaniel Boissonnat and Mathijs Wintraecken 
Extending Drawings of Graphs to Arrangements of Pseudolines [doi] Alan Arroyo , Julien Bensmail, and R. Bruce Richter 
15:2015:30  Break  
15:3016:30 
Invited Talk — Chair: Danny Chen, Host: Hung P. Hoang Geometric Statistics for Computational Anatomy Xavier Pennec 

16:3016:40  Break  
Session ThS8A Chair: Elizabeth Munch, Host: Patrick Schnider 
Session ThS8B Chair: Emo Welzl, Host: Nicolas Grelier 

16:4017:00  Worstcase 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:0017:20  Homotopy Reconstruction via the Cech Complex and the VietorisRips 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:2017: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:4018:00  A Toroidal MaxwellCremonaDelaunay Correspondence [doi] Jeff Erickson and Patrick Lin 
Bounded VCdimension Implies the SchurErdős Conjecture [doi] Jacob Fox, János Pach, and Andrew Suk 
18:0018:10  Break  
Session ThS9A Chair: Tim Ophelders, Host: Bernd Gärtner 
Session ThS9B Chair: Jinhui Xu, Host: Tim Taubner 

18:1018:30  A Nearlinear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread [doi] Kyle Fox and Jiashuai Lu 
The Stretch Factor of HexagonDelaunay Triangulations [doi] Michael Dennis, Ljubomir Perković , and Duru Türkoğlu 
18:3018:50  Further Results on Colored Range Searching [doi] Timothy M. Chan, Qizheng He , and Yakov Nekrich 
Algorithms for Subpath Convex Hull Queries and Rayshooting among Segments [doi] Haitao Wang 
18:5019: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:1019:30  Elderrulestaircodes for Augmented Metric Spaces [doi] Chen Cai, Woojin Kim , Facundo Memoli, and Yusu Wang 
kMedian Clustering under Discrete Fréchet and Hausdorff Distances [doi] Abhinandan Nath and Erin Taylor 
19:3019:50  Combinatorial Properties of SelfOverlapping Curves and Interior Boundaries [doi] Parker Evans , Brittany Terese Fasy, and Carola Wenk 
 
UTC+2  Session FrY3A Chair: Anne Driemel, Host: Daniel Bertschinger 
Session FrY3B Chair: Michael Kerber, Host: Meghana M. Reddy 
14:0014: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:

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:2014: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
applicationspecific.

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 transportbased 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:4015:00  Voronoibased 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 measurebased 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:0015:10  Break  
15:1016:20 
Awards: Test of Time & Best Student Presentation — Chair: Pankaj Agarwal, Host: Julia Schulte


16:2016:30  Break  
Workshop: Computational Aspects of Learning and Processing Metrical Data Chair: Anastasios Sidiropoulos, Host: Ahad N. Zehmakan 

16:3017:10  Metric Learning: Overview and New Directions
Brian Kulis
Metric learning is a supervised machine learning problem concerned
with learning a taskspecific 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 socalled
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:1017: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 treebased approximation algorithms for
searching nearest neighbors with respect to the Wasserstein1
distance. I will start with describing a standard treebased
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 highaccuracy
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:3518: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 1skeleton 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 ErdosRenyi 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 ERpertubed
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 ERperturbed
RGG. The talk will focus on the metric recovery problem. We will
show how the Jaccard index and the edgeclique 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:0018: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 Euclideanbased 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:2518:50  Optimal terminal dimensionality reduction in Euclidean space
Jelani Nelson
The JohnsonLindenstrauss 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:5019: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 cchordal 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:1519: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
shortestpath 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
k1. 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.
