Accepted Contributions
 Proceedings at dagstuhl.de
Schedule
Rooms: (Tue.  Fri.)
A (for Auditorium). On ground floor, directly ahead of entrance.
Used for all singletrack sessions, track A of SoCG talks, and YRF talks.
B (for Basement). One floor down, adjacent to elevators / staircase.
Used for track B of SoCG talks and workshops.
C (for Classroom). One floor up; nearest room to elevators / staircase.
Used for track C of workshops.
D (for Demo). Adjacent to C, on 2nd floor.
Used for Multimedia presentations.
(Note: each presentation will also be featured in lobby at specific times)
Detailed daily schedules (click to to show / hide contents)
Printed copies will be available at the registration desk.
Tuesday June 14  
12:00  13:15 
Lunch reception
[+] Location: Jaharis Center courtyard (across street from SoCG) Please bring ID. In case of bad weather, we may move to the SoCG coffee break room. 

13:25  13:35 
Welcome  
13:35  14:00 
Multimedia Preview
[+]
Interactive Geometric Algorithm Visualization in a Browser
Geometric Models for Musical Audio Data
Visualizing Scissors Congruence
Visualization of Geometric Spanner Algorithms
Path Planning for Simple Robots using Soft Subdivision Search
Exploring Circle Packing Algorithms
The Explicit Corridor Map: Using the Medial Axis for RealTime Path Planning and Crowd Simulation
High Dimensional Geometry of Sliding Window Embeddings of Periodic Videos
Introduction to Persistent Homology 

Session 1A Chair: Joseph O'Rourke 
Session 1B Chair: Matias Korman 

14:00  14:20 
The Planar Tree Packing Theorem
[DOI]
[+] Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters and Csaba Toth Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edgedisjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of García et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees. 
An Efficient Randomized Algorithm for HigherOrder Abstract Voronoi Diagrams
[DOI]
[+] Cecilia Bohler, Rolf Klein and ChihHung Liu Given a set of n sites in the plane, the orderk Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites.The orderk Voronoi diagram arises for the knearestneighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study orderk Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete orderk Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O(k(nk) log^{2}n + n log^{3}n) steps, where O(k(nk)) is the number of faces in the worst case. Due to those axioms, this result applies to disjoint line segments in the L_{p} norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_{1} or Euclidean metric before. 
14:20  14:40 
Degree Four Plane Spanners: Simpler and Better
[DOI]
[+] Iyad Kanj, Ljubomir Perkovic and Duru Turkoglu Let P be a set of n points embedded in the plane, and let C be the complete Euclidean graph whose pointset is P. Each edge in C between two points p, q is realized as the line segment [pq], and is assigned a weight equal to the Euclidean distance pq. In this paper, we show how to construct in O(nlg{n}) time a plane spanner of C of maximum degree at most 4 and of stretch factor at most 20. This improves a long sequence of results on the construction of bounded degree plane spanners of C. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree while significantly improving their stretch factor upper bound from 156.82 to 20. The construction of our spanner is based on Delaunay triangulations defined with respect to the equilateraltriangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a wellstructured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateraltriangle distance. 
The Farthestpoint Geodesic Voronoi Diagram of
Points on the Boundary of a Simple Polygon
[DOI] [+] Eunjin Oh, Luis Barba and HeeKap Ahn Given a set of sites (points) in a simple polygon, the farthestpoint geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)time algorithm to compute the farthestpoint geodesic Voronoi diagram for m sites lying on the boundary of a simple ngon. 
14:40  15:00 
On Visibility Representations of Nonplanar
Graphs
[DOI]
[+] Therese Biedl, Giuseppe Liotta and Fabrizio Montecchiani A rectangle visibility representation (RVR) of a graph consists of an assignment of axisaligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NPhard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straightline drawings of 1plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge. 
Qualitative Symbolic Perturbation
[DOI]
[+] Olivier Devillers, Menelaos Karavelas and Monique Teillaud In a classical Symbolic Perturbation scheme, degeneracies are handled by substituting some polynomials in epsilon for the inputs of a predicate. Instead of a single perturbation, we propose to use a sequence of (simpler) perturbations. Moreover, we look at their effects geometrically instead of algebraically; this allows us to tackle cases that were not tractable with the classical algebraic approach. 
15:00  15:20 
Inserting Multiple Edges into a Planar Graph
[DOI] [+] Markus Chimani and Petr Hlineny Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. An optimal solution to this problem is known to approximate the crossing number of the graph G+F. Finding an exact solution to MEI is NPhard for general F, but linear time solvable for the special case of F=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=F was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [ChimaniHlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees. We give the first exact algorithm for this problem; it requires only O(V(G)) time for any constant k. 
Fixed Points of the Restricted Delaunay
Triangulation Operator
[DOI]
[+] Marc Khoury and Jonathan Richard Shewchuk The restricted Delaunay triangulation can be conceived as an operator that takes as input a kmanifold (typically smooth) embedded in R^{d} and a set of points sampled with sufficient density on that manifold, and produces as output a kdimensional triangulation of the manifold, the input points serving as its vertices. What happens if we feed that triangulation back into the operator, replacing the original manifold, while retaining the same set of input points? If k = 2 and the sample points are sufficiently dense, we obtain another triangulation of the manifold. Iterating this process, we soon reach an iteration for which the input and output triangulations are the same. We call this triangulation a fixed point of the restricted Delaunay triangulation operator. With this observation, and a new test for distinguishing ``critical points'' near the manifold from those near its medial axis, we develop a provably good surface reconstruction algorithm for R^{3} with unusually modest sampling requirements. We develop a similar algorithm for constructing a simplicial complex that models a 2manifold embedded in a highdimensional space R^{d}, also with modest sampling requirements (especially compared to algorithms that depend on sliver exudation). The latter algorithm builds a nonmanifold representation similar to the flow complex, but made solely of Delaunay simplices. The algorithm avoids the curse of dimensionality: its running time is polynomial, not exponential, in d. 
15:20  15:40 
Strongly Monotone Drawings of Planar Graphs
[DOI] [+] Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze and Manfred Scheucher A straightline drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossingfree strongly monotone drawings for some classes of planar graphs; namely, 3connected planar graphs, outerplanar graphs, and 2trees. The drawings of 3connected planar graphs are based on primaldual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex. 
Incremental Voronoi Diagrams
[DOI]
[+] Luis Barba, Stefan Langerman, Sarah R. Allen and John Iacono We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram VD(S) (and several variants thereof) of a set S of n sites in the plane as sites are added to the set. To that effect, we define a general update operation for planar graphs that can be used to model the incremental construction of several variants of Voronoi diagrams as well as the incremental construction of an intersection of halfspaces in R^{3}. We show that the amortized number of edge insertions and removals needed to add a new site to the Voronoi diagram is O(n^{1/2}). A matching Omega(n^{1/2}) combinatorial lower bound is shown, even in the case where the graph representing the Voronoi diagram is a tree. This contrasts with the O(log(n)) upper bound of Aronov et al. [Aronov et al., in proc. of LATIN, 2006] for farthestpoint Voronoi diagrams in the special case where points are inserted in clockwise order along their convex hull. We then present a semidynamic data structure that maintains the Voronoi diagram of a set S of n sites in convex position. This data structure supports the insertion of a new site p (and hence the addition of its Voronoi cell) and finds the asymptotically minimal number K of edge insertions and removals needed to obtain the diagram of S U (p) from the diagram of S, in time O(K polylog n) worst case, which is O(n^{1/2} polylog n) amortized by the aforementioned combinatorial result. The most distinctive feature of this data structure is that the graph of the Voronoi diagram is maintained explicitly at all times and can be retrieved and traversed in the natural way; this contrasts with other known data structures supporting nearest neighbor queries. Our data structure supports general search operations on the current Voronoi diagram, which can, for example, be used to perform point location queries in the cells of the current Voronoi diagram in O(log n) time, or to determine whether two given sites are neighbors in the Delaunay triangulation. 
15:40  16:10 
Coffee break  
Session 2A Chair: Sergio Cabello 
Session 2B Chair: Erin Chambers 

16:10  16:30 
Hyperplane Separability and Convexity of
Probabilistic Point Sets
[DOI]
[+] Martin Fink, John Hershberger, Nirman Kumar and Subhash Suri We describe an O(n^{d}) time algorithm for computing the exact probability that two ddimensional probabilistic point sets are linearly separable, for any fixed d >= 2. A probabilistic point in dspace is the usual point, but with an associated (independent) probability of existence. We also show that the ddimensional separability problem is equivalent to a (d+1)dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership by a factor of n [Agarwal et al., ESA, 2014]. In addition, our algorithms can handle "input degeneracies" in which more than k+1 points may lie on a kdimensional subspace, thus resolving an open problem in [Agarwal et al., ESA, 2014]. Finally, we prove lower bounds for the separability problem via a reduction from the kSUM problem, which shows in particular that our O(n^{2}) algorithms for 2dimensional separability and 3dimensional convex hull membership are nearly optimal. 
Polynomialsized Topological Approximations
Using the Permutahedron
[DOI]
[+] Aruni Choudhary, Michael Kerber and Sharath Raghvendra Classical methods to model topological properties of point clouds, such as the VietorisRips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multiscale filtration of the Rips complex with improved bounds for size: precisely, for n points in R^{d}, we obtain a O(d)approximation with at most n2^{O(d log k)} simplices of dimension k or lower. In conjunction with dimension reduction techniques, our approach yields a O(polylog (n))approximation of size n^{O(1)} for Rips filtrations on arbitrary metric spaces. This result stems from highdimensional lattice geometry and exploits properties of the permutahedral lattice, a wellstudied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every (1+epsilon)approximation of the Cech filtration has to contain n^{Omega(log log n)} features, provided that epsilon < 1/(log^{1+c}n for c in (0,1). 
16:30  16:50 
On the Separability of Stochastic Geometric
Objects, with Applications
[DOI]
[+] Jie Xue, Yuan Li and Ravi Janardan In this paper, we study the linear separability problem for stochastic geometric objects under the wellknown unipoint/multipoint uncertainty models. Let S=S^{R} U S^{B} be a given set of stochastic bichromatic points, and define n = min{S^{R}, S^{B}} and N = max{S^{R}, S^{B}}. We show that the separableprobability (SP) of S can be computed in O(nN^{d1}) time for d >= 3 and O(min{nN log N, N^{2}}) time for d=2, while the expected separationmargin (ESM) of S can be computed in O(nN^{d}) time for d >= 2. In addition, we give an Omega(nN^{d1}) witnessbased lower bound for computing SP, which implies the optimality of our algorithm among all those in this category. Also, a hardness result for computing ESM is given to show the difficulty of further improving our algorithm. As an extension, we generalize the same problems from points to general geometric objects, i.e., polytopes and/or balls, and extend our algorithms to solve the generalized SP and ESM problems in O(nN^{d}) and O(nN^{d+1}) time, respectively. Finally, we present some applications of our algorithms to stochastic convexhull related problems. 
Eliminating HigherMultiplicity Intersections, II.
The Deleted Product Criterion in the rMetastable Range
[DOI]
[+] Isaac Mabillard and Uli Wagner Motivated by Tverbergtype problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into R^{d} without highermultiplicity intersections. We focus on conditions for the existence of almost rembeddings, i.e., maps f: K > R^{d} such that the intersection of f(sigma_1), ..., f(sigma_r) is empty whenever sigma_1,...,sigma_r are pairwise disjoint simplices of K. Generalizing the classical HaefligerWeber embeddability criterion, we show that a wellknown necessary deleted product condition for the existence of almost rembeddings is sufficient in a suitable rmetastable range of dimensions: If r d > (r+1) dim K + 2 then there exists an almost rembedding K> R^{d} if and only if there exists an equivariant map of the rfold deleted product of K to the sphere S^{d(r1)1}. This significantly extends one of the main results of our previous paper (which treated the special case where d=rk and dim K=(r1)k, for some k> 2), and settles an open question raised there. 
16:50  17:10 
Separating a Voronoi Diagram via Local Search
[DOI]
[+] V.S.P. Vijay Bhattiprolu and Sariel HarPeled Given a set P of n points in R^{d} , we show how to insert a set Z of O(n^{11/d}) additional points, such that P can be broken into two sets P1 and P2 , of roughly equal size, such that in the Voronoi diagram V(P u Z), the cells of P1 do not touch the cells of P2 ; that is, Z separates P1 from P2 in the Voronoi diagram (and also in the dual Delaunay triangulation). In addition, given such a partition (P1 , P2 ) of P , we present an approximation algorithm to compute a minimum size separator realizing this partition. We also present a simple local search algorithm that is a PTAS for approximating the optimal Voronoi partition. 
Delaunay Triangulations on Orientable Surfaces
of Low Genus
[DOI]
[+] Mikhail Bogdanov, Monique Teillaud and Gert Vegter Earlier work on Delaunay triangulation of point sets on the 2D flat torus, which is locally isometric to the Euclidean plane, was based on lifting the point set to a locally isometric 9sheeted covering space of the torus. Under mild conditions the Delaunay triangulation of the lifted point set, consisting of 9 copies of the input set, projects to the Delaunay triangulation of the input set. We improve and generalize this work. First we present a new construction based on an 8sheeted covering space, which shows that eight copies suffice for the standard flat torus. Then we generalize this construction to the context of compact orientable surfaces of higher genus, which are locally isometric to the hyperbolic plane. We investigate more thoroughly the Bolza surface, homeomorphic to a sphere with two handles, both because it is the hyperbolic surface with lowest genus, and because triangulations on the Bolza surface have applications in various fields such as neuromathematics and cosmological models. While the general properties (existence results of appropriate covering spaces) show similarities with the results for the flat case, explicit constructions and their proofs are much more complex, even in the case of the apparently simple Bolza surface. One of the main reasons is the fact that two hyperbolic translations do not commute in general. To the best of our knowledge, the results in this paper are the first ones of this kind. The interest of our contribution lies not only in the results, but most of all in the construction of covering spaces itself and the study of their properties. 
17:10  17:30 
On Variants of kmeans Clustering
[DOI]
[+] Sayan Bandyapadhyay and Kasturi Varadarajan Clustering problems often arise in fields like data mining and machine learning. Clustering usually refers to the task of partitioning a collection of objects into groups with similar elements, with respect to a similarity (or dissimilarity) measure. Among the clustering problems, kmeans clustering in particular has received much attention from researchers. Despite the fact that kmeans is a well studied problem, its status in the plane is still open. In particular, it is unknown whether it admits a PTAS in the plane. The best known approximation bound achievable in polynomial time is 9+epsilon. In this paper, we consider the following variant of kmeans. Given a set C of points in R^{d} and a real f > 0, find a finite set F of points in R^{d} that minimizes the quantity f*F+sum_{p in C} min_{q in F} {pq}^{2}. For any fixed dimension d, we design a PTAS for this problem that is based on local search. We also give a ``bicriterion'' local search algorithm for kmeans which uses (1+epsilon)k centers and yields a solution whose cost is at most (1+epsilon) times the cost of an optimal kmeans solution. The algorithm runs in polynomial time for any fixed dimension. The contribution of this paper is twofold. On the one hand, we are able to handle the square of distances in an elegant manner, obtaining a nearoptimal approximation bound. This leads us towards a better understanding of the kmeans problem. On the other hand, our analysis of local search might also be useful for other geometric problems. This is important considering that little is known about the local search method for geometric approximation. 
Structure and Stability of the 1Dimensional
Mapper
[DOI]
[+] Mathieu Carrière and Steve Oudot Given a continuous function f:X>R and a cover I of its image by intervals, the Mapper is the nerve of a refinement of the pullback cover f^{1}(I). Despite its success in applications, little is known about the structure and stability of this construction from a theoretical point of view. As a pixelized version of the Reeb graph of f, it is expected to capture a subset of its features (branches, holes), depending on how the interval cover is positioned with respect to the critical values of the function. Its stability should also depend on this positioning. We propose a theoretical framework relating the structure of the Mapper to that of the Reeb graph, making it possible to predict which features will be present and which will be absent in the Mapper given the function and the cover, and for each feature, to quantify its degree of (in)stability. Using this framework, we can derive guarantees on the structure of the Mapper, on its stability, and on its convergence to the Reeb graph as the granularity of the cover I goes to zero. 
17:30  17:50 
Testing Convexity of Figures Under the Uniform
Distribution
[DOI]
[+] Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova We consider the following basic geometric problem: Given epsilon in (0,1/2), a 2dimensional figure that consists of a black object and a white background is epsilonfar from convex if it differs in at least an epsilon fraction of the area from every figure where the black object is convex. How many uniform and independent samples from a figure that is epsilonfar from convex are needed to detect a violation of convexity with probability at least 2/3? This question arises in the context of designing property testers for convexity. Specifically, a (1sided error) tester for convexity gets samples from the figure, labeled by their color; it always accepts if the black object is convex; it rejects with probability at least 2/3 if the figure is epsilonfar from convex. We show that Theta(epsilon^{4/3}) uniform samples are necessary and sufficient for detecting a violation of convexity in an epsilonfar figure and, equivalently, for testing convexity of figures with 1sided error. Our testing algorithm runs in time O(epsilon^{4/3}) and thus beats the Omega(epsilon^{3/2}) sample lower bound for learning convex figures under the uniform distribution from the work of Schmeltz (Data Structures and Efficient Algorithms,1992). It shows that, with uniform samples, we can check if a set is approximately convex much faster than we can find an approximate representation of a convex set. 
Convergence Between Categorical
Representations of Reeb Space and Mapper
[DOI]
[+] Elizabeth Munch and Bei Wang The Reeb space, which generalizes the notion of a Reeb graph, is one of the few tools in topological data analysis and visualization suitable for the study of multivariate scientific datasets. First introduced by Edelsbrunner et al., it compresses the components of the level sets of a multivariate mapping and obtains a summary representation of their relationships. A related construction called mapper, and a special case of the mapper construction called the Joint Contour Net have been shown to be effective in visual analytics. Mapper and JCN are intuitively regarded as discrete approximations of the Reeb space, however without formal proofs or approximation guarantees. An open question has been proposed by Dey et al. as to whether the mapper construction converges to the Reeb space in the limit. In this paper, we are interested in developing the theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis. Using tools from category theory, we formally prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations. Given a sequence of refined discretizations, we prove that these approximations converge to the Reeb space in the interleaving distance; this also helps to quantify the approximation quality of the discretization at a fixed resolution. 
18:45  20:45 
Social event: The Black Rose Irish pub.
[+] Address: 160 State st., Boston 02109 www Walking from SoCG: 1.4km, 18 min. Subway from SoCG: orange line towards Oak Grove. Stop at State St. Walk East on State st. Please bring ID. 

 Wednesday
Wednesday June 15  
Session 3A Chair: Monique Teillaud 
Session 3B Chair: David Mount 

9:00  9:20 
A QuasilinearTime Algorithm for Tiling the
Plane Isohedrally with a Polyomino
[DOI]
[+] Stefan Langerman and Andrew Winslow A plane tiling consisting of congruent copies of a shape is isohedral provided that for any pair of copies, there exists a symmetry of the tiling mapping one copy to the other. We give a O(n*log^{2}n)time algorithm for deciding if a polyomino with n edges can tile the plane isohedrally. This improves on the O(n^{18})time algorithm of Keating and Vince and generalizes recent work by Brlek, Provençal, Fédou, and the second author. 
Weak 1/rnets for Moving Points
[DOI]
[+] Alexandre Rok and Shakhar Smorodinsky In this paper, we extend the weak 1/rnet theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog N of a weak 1/rnet of cardinality O(r^{d(d+1)/2}log^{d} r) whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of N has one polynomial coordinate. 

9:20  9:40 
Congruence Testing of Point Sets in 4space
[DOI] [+] Heuna Kim and Günter Rote We give a deterministic O(n log n)time algorithm to decide if two npoint sets in 4dimensional Euclidean space are the same up to rotations and translations. It has been conjectured that O(n log n) algorithms should exist for any fixed dimension. The best algorithms in dspace so far are a deterministic algorithm by Brass and Knauer [Int. J. Comput. Geom. Appl., 2000] and a randomized Monte Carlo algorithm by Akutsu [Comp. Geom., 1998]. They take time O(n^{2} log n) and O(n^{3/2} log n) respectively in 4space. Our algorithm exploits many geometric structures and properties of 4dimensional space. 
New Lower Bounds for epsilonnets
[DOI]
[+] Nabil Mustafa, Andrey Kupavskiy and Janos Pach Following groundbreaking work by Haussler and Welzl (1987), the use of small epsilonnets has become a standard technique for solving algorithmic and extremal problems in geometry and learning theory. Two significant recent developments are: (i) an upper bound on the size of the smallest epsilonnets for set systems, as a function of their socalled shallowcell complexity (Chan, Grant, Konemann, and Sharpe); and (ii) the construction of a set system whose members can be obtained by intersecting a point set in R^{4} by a family of halfspaces such that the size of any epsilonnet for them is at least (1/(9*epsilon)) log (1/epsilon) (Pach and Tardos). The present paper completes both of these avenues of research. We (i) give a lower bound, matching the result of Chan et al., and (ii) generalize the construction of Pach and Tardos to halfspaces in R^{d}, for any d >= 4, to show that the general upper bound of Haussler and Welzl for the size of the smallest epsilonnets is tight. 

9:45  10:45 
Invited Talk: Daniela Rus, Toward Pervasive Robots
[+] The digitization of practically everything coupled with the mobile Internet, the automation of knowledge work, and advanced robotics promises a future with democratized use of machines and widespread use of robots and customization. However, pervasive use of robots remains a hard problem. Where are the gaps that we need to address in order to advance toward a future where robots are common in the world and they help reliably with physical tasks? What is the role of geometric reasoning along this trajectory? In this talk I will discuss challenges toward pervasive use of robots and recent developments in geometric algorithms for customizing robots. I will focus on a suite of geometric algorithms for automatically designing, fabricating, and tasking robots using a printandfold approach. I will also describe how geometric reasoning can play a role in creating robots more capable of reasoning in the world. By enabling ondemand creation of programmable robots, we can begin to imagine a world with one robot for every physical task. 

10:45  11:15 
Coffee break  
11:15  11:35 
Best Paper:
The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions
[DOI]
[+] Boris Aronov, Otfried Cheong, Michael Gene Dobbins and Xavier Goaoc We show that the union of translates of a convex body in three dimensional space can have a cubic number holes in the worst case, where a hole in a set is a connected component of its compliment. This refutes a 20yearold conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions. 

11:35  11:50 
YRF Preview (for Wednesday's talks)  
Session 4A Chair: Jean Cardinal 
Session 4B Chair: Kevin Verbeek 

11:55  12:15 
Who Needs Crossings? Hardness of Plane
Graph Rigidity
[DOI]
[+] Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch and Tao Schardl We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: "globally noncrossing" graphs, which avoid crossings in all of their configurations; matchstick graphs, with unitlength edges and where only noncrossing configurations are considered; and unrestricted graphs (crossings allowed) with unit edge lengths (or in the global rigidity case, edge lengths in {1,2}). We show that all nine of these questions are complete for the class ExistsR, defined by the Existential Theory of the Reals, or its complement ForallR; in particular, each problem is (co)NPhard. One of these nine results  that realization of unitdistance graphs is ExistsRcomplete  was shown previously by Schaefer (2013), but the other eight are new. We strengthen several prior results. Matchstick graph realization was known to be NPhard (Eades & Wormald 1990, or Cabello et al. 2007), but its membership in NP remained open; we show it is complete for the (possibly) larger class ExistsR. Global rigidity of graphs with edge lengths in {1,2} was known to be coNPhard (Saxe 1979); we show it is ForallRcomplete. The majority of the paper is devoted to proving an analog of Kempe's Universality Theorem  informally, "there is a linkage to sign your name"  for globally noncrossing linkages. In particular, we show that any polynomial curve phi(x,y)=0 can be traced by a noncrossing linkage, settling an open problem from 2004. More generally, we show that the nontrivial regions in the plane that may be traced by a noncrossing linkage are precisely the compact semialgebraic regions. Thus, no drawing power is lost by restricting to noncrossing linkages. We prove analogous results for matchstick linkages and unitdistance linkages as well. 
Approximating Dynamic Time Warping and Edit
Distance for a Pair of Point Sequences
[DOI]
[+] Pankaj Agarwal, Kyle Fox, Jiangwei Pan and Rex Ying We present the first subquadratic algorithms for computing similarity between a pair of point sequences in R^{d}, for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + eps)approximations of DTW and ED in nearlinear time for point sequences drawn from kpacked or kbounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is kpacked if the length of its intersection with any ball of radius r is at most kr, and it is kbounded if the subcurve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1. The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimumweight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimumweight paths through these rectangles. 

12:15  12:35 
Configurations of Lines in 3space and Rigidity of
Planar Structures
[DOI]
[+] Orit E. Raz Let L be a sequence (l_{1},l_{2},...,l_{n}) of n lines in C^{3}. We define the *intersection graph* G_{L}=([n],E) of L, where [n]:={1,..., n}, and with {i,j} in E if and only if i neq j and the corresponding lines l_{i} and l_{j} intersect, or are parallel (or coincide). For a graph G=([n],E), we say that a sequence L is a *realization* of G if Gsubset G_{L}. One of the main results of this paper is to provide a combinatorial characterization of graphs G=([n],E) that have the following property: For every *generic* realization L of G, that consists of n pairwise distinct lines, we have G_{L}=K_{n}, in which case the lines of L are either all concurrent or all coplanar. The general statements that we obtain about lines, apart from their independent interest, turns out to be closely related to the notion of graph rigidity. The connection is established due to the socalled ElekesSharir framework, which allows us to transform the problem into an incidence problem involving lines in three dimensions. By exploiting the geometry of contacts between lines in 3D, we can obtain alternative, simpler, and more precise characterizations of the rigidity of graphs. 
On Computing the Fréchet Distance Between Surfaces
[DOI]
[+] Amir Nayyeri and Hanzhong Xu We describe two (1+epsilon)approximation algorithms for computing the Fréchet distance between two homeomorphic piecewise linear surfaces R and S of genus zero and total complexity n, with Fréchet distance delta. (1) A 2^{O((n + ( (Area(R)+Area(S))/(epsilon.delta)^2 )^2 )} time algorithm if R and S are composed of fat triangles (triangles with angles larger than a constant). (2) An O(D/(epsilon.delta)^2) n + 2^{O(D^4/(epsilon^4.delta^2))} time algorithm if R and S are polyhedral terrains over [0,1]^{2} with slope at most D. Although, the Fréchet distance between curves has been studied extensively, very little is known for surfaces. Our results are the first algorithms (both for surfaces and terrains) that are guaranteed to terminate in finite time. Our latter result, in particular, implies a linear time algorithm for terrains of constant maximum slope and constant Fréchet distance. 

12:35  12:55 
Crossing Number is Hard for Kernelization
[DOI]
[+] Petr Hlineny and Marek Derňár The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixedparameter tractable for the parameter k [Grohe, STOC 2001]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of G). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NPhard, which has been an open problem for some time, too, and then employ the complexity technique of crosscomposition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge. 
Grouping Timevarying Data for Interactive
Exploration
[DOI]
[+] Arthur van Goethem, Marc Van Kreveld, Maarten Löffler, Bettina Speckmann and Frank Staals We present algorithms and data structures that support the interactive analysis of the grouping structure of one, two, or higherdimensional timevarying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of timevarying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: groupsize, groupduration, and interentity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an outputsensitive manner. Our results hold in R^{d} for fixed d. 

12:55  14:30 
Lunch: Hei La Moon dim sum restaurant
[+] Location: 88 Beach St, Boston, MA 02111 (5 minute walk from SoCG: exit building, turn left, walk on Harrison until Beach, turn right, pass gate, cross large avenue, restaurant is on the left) 

Multimedia room open through lunch and the afternoon  
14:30  16:00 
A: Young Researchers Forum  B: Workshop 1: 5th Mini Symposium on Computational Topology, Part I [Web] [+] Organizers: Justin Curry, Pawel Dlotko, Michael Lesnick and Clement Maria Software solutions for geometric and topological understanding of high dimensional data. This part focuses on the state of the art implementations of algorithms for computing topological features in data analysis. Existing software for statistics in topology (e.g, TDA Rpackage, persistence landscape toolbox, kernel for persistence) will also be showcased. 
C: Workshop 2: Geometric Computing on Uncertain Data [Web] [+] Organizers: Pankaj Agarwal, Nirman Kumar, Ben Raichel and Subhash Suri There is a growing need for geometric algorithms that can gracefully operate under data uncertainty. The sources of data uncertainty can vary widely, from measurement noise to missing information and strategic randomness, among others. A number of researchers within computational geometry have recently explored a variety of data uncertainty models and problemspecific approaches, demonstrating a breadth of interest and scope. The research, however, is still in a state of infancy, and ripe for a broader exchange of ideas. The goal of the workshop is to provide a forum for computational geometers interested in this topic to learn about the current state of the art, stimulate discussions about new directions and challenges, and to foster collaborations. 

14:30 
Universal Guards: Guarding all Polygonalizations of a Point Set in the Plane
[+] Sándor Fekete, Qian Li, Joseph Mitchell and Christian Scheffer The Art Gallery Problem (AGP) seeks to find the fewest guards to see all of a given domain; in its classic combinatorial variant (posed by Victor Klee), it asks for the number of guards that always suffice and are sometimes necessary to guard any simple $n$gon: the answer is the well known $\lfloor n/3\rfloor$. While Klee's question was posed about guarding an $n$vertex {\em simple polygon}, a related question about {\em point sets} was posed at the 2014 GoodmanPollack Fest (NYU, November 2014): Given a set $S$ of $n$ points in the plane, how many guards always suffice to guard any simple polygon with vertex set $S$? A set of guards that guard every polygonalization of $S$ is said to be a set of {\em universal guards} for the point set. The question is how many universal guards are always sufficient, and sometimes necessary, for any set of $n$ points? We give the first set of results on universal guarding. We focus here on the case in which guards must be placed at a subset (the {\em guarded points}) of the input set $S$ and thus will be vertex guards for any polygonalization of~$S$. 14:45  AllPairs Shortest Paths in Unit Disk Graphs in Slightly Subquadratic Time [+] Timothy Chan and Dimitrios Skrepetos In this paper we study the allpairs shortest paths problem in (unweighted) unit disk graphs. The previous best solution for this problem required O(n 15:00  Improved Bounds on the Growth Constant of Polyiamonds [+] Gill Barequet and Mira Shalah In this paper we provide improved lower and upper bounds on the asymptotic growth constant of polyiamonds, proving that it is between~2.8424 and~3.6050. 15:15  Approximate Range Counting Revisited [+] Saladi Rahul This work presents several new results on approximate range counting. For a given query, if the actual count is $k$, then the data structures in this paper output a value, $\tau$, lying in the range $[(1\vare)k,(1+\vare)k]$. The key results are the following: [A] A new technique for efficiently solving any approximate range counting problem is presented. This technique can be viewed as an enhancement of Aronov and HarPeled's technique [{\it SIAM Journal of Computing, 2008}]; key reasons being the following: (1) The new technique is sensitive to the value of $k$: As an application, this work presents a structure for approximate halfspace range counting in $\IR^d, d\geq 4$ which occupies $O(n)$ space and solves the query in $O((n/k)^{11/\lfloor d/2\rfloor})$ time. When $k=\Theta(n)$, then the query time is $O(1)$. (2) The new technique handles colored range searching problems: As an application, the orthogonal colored range counting problem is solved. Existing structures for exact counting use $O(n^d)$ space to answer the query in $O(polylog n)$ query time. Improving these bounds substantially would require improving the best exponent of matrix multiplication. Therefore, if one is willing for an approximation, an attractive result is obtained: an $O(n polylog n)$ space data structure and an $O(polylog n)$ query time algorithm. [B] An optimal solution for approximate rectangle stabbing counting problems in $\IR^2$. This is achieved by a nontrivial reduction to planar point location. [C] Finally, an efficient solution is obtained for $3$sided orthogonal colored range counting. The result is obtained by a nontrivial combination of two different types of random sampling techniques and a reduction to noncolored range searching problem. 15:30  Exact and Approximation Algorithms for TimeWindow TSP [+] Su Jia, Jie Gao and Joseph Mitchell We study a version of the timewindow traveling salesman problem (TWTSP): given a speed bound B for a robot, a set of cities each having a time window during which it must be visited, and a shortest path for the robot to visit all cities within their respective time windows, if possible to do so. 15:45  Recognition of the Spherical Laguerre Voronoi Diagram [+] Supanut Chaidee and Kokichi Sugihara We construct an algorithm for judging whether or not a given tessellation on a sphere is a spherical Laguerre Voronoi diagram. This algorithm is based on the properties of polyhedra corresponding to the spherical Laguerre Voronoi diagram and their transformation in projective spaces. 
14:30  14:50 Yasu Hiraoka Topological Data Analysis on Materials Science: Statistical Characterization of Glass Transition 15:00  15:20 Gunnar Carlsson Topological Modeling of Complex Data 15:30  15:50 David Spivak Pixel Matrices for Big, Messy, RealWorld Data [+] Natural, realworld data does not come equipped with mathematical equations that it satisfies. A data set is just a collection of observed relationships, so it is naturally messy and probabilistic. When combining and analyzing these observed relationships, it is destructive, yet common practice, to first "normalize" the data by choosing models, fitting curves, removing outliers, or estimating parameters. It would often be preferable to forgo the cleanup step and simply combine the data sets directly. Pixel matrices are an applied categorytheoretic technique for doing just that. We will explain how pixel matrices offer a massively parallelizable method for approximating the solution set for systems of nonlinear equations, and how the same idea can be applied when working with messy data. 
14:30  15:00 Maarten Löffler Where are we Going? Uncertainty in Motion 15:00  15:30 Jeff Phillips Coresets for Uncertain Data 15:30  16:00 Yuan Li On the Arrangement of Stochastic Lines in R^{2} 

16:00  16:30 
Coffee break  
16:30  18:00 
A: Young Researchers Forum  B: Workshop 1 (continued) 5th Mini Symposium on Computational Topology, Part I 
C: Workshop 2 (continued) Geometric Computing on Uncertain data 

16:30 
Computing the Expected Area of an Induced Triangle
[+] Vissarion Fisikopoulos, Frank Staals and Constantinos Tsirogiannis Consider the following problem: given a set P of n points in the plane, compute the expected area of a triangle induced by P, that is, a triangle whose vertices are selected uniformly at random from the points in P. This problem is a special case of computing the expected area of the convex hull of k points, selected uniformly at random from P. These problems are important in computing the functional diversity in Ecology. We present a simple exact algorithm for the problem that computes the expected triangle area in O(n^{2}log n) time, and extends to the case of computing the area of the convex hull of a size k subset. Additionally, we present a (1\pm\epsilon)approximation algorithm for the case in which the ratio \rho between the furthest pair distance and the closest pair distance of the points in P is bounded. With high probability (whp.) our algorithm computes an answer in the range [(1\epsilon)A^{*},(1+\epsilon)A], where A is the true expected triangle area, in O(\frac{1}{\epsilon^{8/3}} \rho^{4}n^{5/3}log^{4/3}n) expected time. 16:45  A Geometric Approach to kSUM [+] Jean Cardinal, John Iacono and Aurélien Ooms It is known that $k$SUM can be solved using $\tilde{O}(n^{\lceil\frac{k}{2}\rceil})$ time and linear queries (here the notation $\tilde{O}$ ignores polylogarithmic factors). On the other hand, there is a point location algorithm due to Meiser that shows the existence of $\tilde{O}(n^4)$depth algebraic computation trees for $k$SUM. By streamlining Meiser's algorithm, we prove $k$SUM can be solved using $\tilde{O}(n^3)$ expected linear queries in \tilde{O}(n^{\lceil (k/2) \rceil+8}) expected time. Thus, we show that it is possible to have an algorithm with a runtime almost identical (up to the +8) to the best known algorithm but for the first time also with the number of queries on the input a polynomial that is independent of $k$. The new algorithms we present rely heavily on fundamental tools from computational geometry: $\varepsilon$nets and cuttings. A preprint is available arXiv. 17:00  Network Optimization on Partitioned Pairs of Points [+] Tyler Speaker Mayer, Gui Citovsky, Joseph Mitchell, Esther Arkin, Aritra Banik, Paz Carmi, Matthew Katz and Su Jia Given a set $S = \bigcup_{i=1}^{n}\{p_i, q_i\}$ of $n$ pairs of points in a metric space, we study the problem of computing, what we call, a {\em feasible} partition $S = S_1 \cup S_2$ such that $p_i \in S_1$ if and only $q_i \in S_2 \: \forall \: i$. The partition should optimize the cost of a {\em pair} of networks, one built on $S_1$, and one built on $S_2$. In this work we consider the network structures to be matchings, minimum spanning trees (MSTs), traveling salesman tours (TSP tours), or their bottleneck equivalents. Let $f(X)$ be some network structure computed on point set $X$ and let $\lambda(f(X))$ be the bottleneck edge of that network. For each of the aforementioned network structures we consider the objective of (1) minimizing $f(S_1) + f(S_2)$, (2) minimizing $max\{f(S_1),f(S_2)\}$, or (3) minimizing $max\{\lambda(f(S_1)), \lambda(f(S_2))\}$. Here, $\cdot$ denotes the sum of the edge lengths. We show several hardness results and an $O(1)$ approximation for every objective considered. Our results are summarized in Table \ref{results_table} and full details can be found in \cite{arkin2016Network}. 17:15  Computing the Planar Slope Number [+] Udo Hoffmann The planar slope number of a planar graph G is defined as the minimal number of slopes that is required for a straight line drawing of G. We show that determining the planar slope number is hard in the existential theory of the reals. We point out consequences for drawings that minimize the planar slope number. 
16:30  16:50 Michael Kerber Geometry Helps to Compare Persistence Diagrams 17:00  17:20 Clement Maria Zigzag Persistent Homology: Algorithms, Software and Applications 17:30  17:50 Pawel Dlotko Geometry Understanding in Higher Dimensions, the Gudhi Library 
16:30  17:00 Nancy Amato Dealing with Uncertainty in SamplingBased Motion Planning 17:00  17:30 Guy Rosman Using Coresets for Video Summaries 17:30  18:00 Don Sheehy Sampling Uncertain Manifolds 

18:45  21:00 
Social event: Skywalk observatory reception
[+] Location: Prudential Center, 52nd floor www Walking from SoCG: under 2km. Follow Kneeland / Stuart street all the way. Subway from SoCG:
Please bring ID. 

 Thursday
Thursday June 16  
Session 5A Chair: Yusu Wang 
Session 5B Chair: Marc van Kreveld 

9:00  9:20 
Avoiding the Global Sort: A Faster Contour Tree
Algorithm
[DOI]
[+] Benjamin Raichel and C. Seshadhri We revisit the classical problem of computing the contour tree of a scalar field f:M to R, where M is a triangulated simplicial mesh in R^{d}. The contour tree is a fundamental topological structure that tracks the evolution of level sets of f and has numerous applications in data analysis and visualization. All existing algorithms begin with a global sort of at least all critical values of f, which can require (roughly) Omega(n log n) time. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for nonpathological inputs. If C denotes the set of critical points in M, the running time is roughly O(sum_{v in C} log l_{v}), where l_{v} is the depth of v in the contour tree. This matches all existing upper bounds, but is a significant asymptotic improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes that are either adjacent in M or in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm. Our algorithm requires several novel ideas: partitioning M in wellbehaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. 
Applications of Incidence Bounds in Point Covering Problems
[DOI]
[+] Ingo van Duijn, Edvin Berglin, Peyman Afshani and Jesper Sindahl Nielsen In the Line Cover problem a set of n points is given and the task is to cover the points using either the minimum number of lines or at most k lines. In Curve Cover, a generalization of Line Cover, the task is to cover the points using curves with d degrees of freedom. Another generalization is the Hyperplane Cover problem where points in ddimensional space are to be covered by hyperplanes. All these problems have kernels of polynomial size, where the parameter is the minimum number of lines, curves, or hyperplanes needed. First we give a nonparameterized algorithm for both problems in O*(2^{n}) (where the O*(.) notation hides polynomial factors of n) time and polynomial space, beating a previous exponentialspace result. Combining this with incidence bounds similar to the famous SzemerediTrotter bound, we present a Curve Cover algorithm with running time O*((Ck/log k)^((d1)k)), where C is some constant. Our result improves the previous best times O*((k/1.35)^k) for Line Cover (where d=2), O*(k^(dk)) for general Curve Cover, as well as a few other bounds for covering points by parabolas or conics. We also present an algorithm for Hyperplane Cover in R^{3} with running time O*((Ck^2/log^(1/5) k)^k), improving on the previous time of O*((k^2/1.3)^k). 

9:20  9:40 
Finding Nonorientable Surfaces in 3manifolds
[DOI]
[+] Benjamin A. Burton, Arnaud De Mesmay and Uli Wagner We investigate the complexity of finding an embedded nonorientable surface of Euler genus g in a triangulated 3manifold. This problem occurs both as a natural question in lowdimensional topology, and as a first nontrivial instance of embeddability of complexes into 3manifolds. We prove that the problem is NPhard, thus adding to the relatively few hardness results that are currently known in 3manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case. 
On the Number of Maximum Empty Boxes Amidst
n Points
[DOI]
[+] Adrian Dumitrescu and Minghui Jiang We revisit the following problem (along with its higher dimensional variant): Given a set S of n points inside an axisparallel rectangle U in the plane, find a maximumarea axisparallel subrectangle that is contained in U but contains no points of S. (I) We prove that the number of maximumarea empty rectangles amidst n points in the plane is O(n log n 2^alpha(n)), where alpha(n) is the extremely slowly growing inverse of Ackermann's function. The previous best bound, O(n^{2}), is due to Naamad, Lee, and Hsu (1984). (II) For any d at least 3, we prove that the number of maximumvolume empty boxes amidst n points in R^{d} is always O(n^d) and sometimes Omega(n^floor(d/2)). This is the first superlinear lower bound derived for this problem. (III) We discuss some algorithmic aspects regarding the search for a maximum empty box in R^{3}. In particular, we present an algorithm that finds a (1epsilon)approximation of the maximum empty box amidst n points in O(epsilon^{2} n^{5/3} log^2 {n}) time. 

9:40  10:00 
Efficient Algorithms to Decide Tightness
[DOI]
[+] Bhaskar Bagchi, Benjamin A. Burton, Basudeb Datta, Nitin Singh and Jonathan Spreer Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but more efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of 3manifolds  a problem which previously was thought to be hard. In addition, for the more difficult problem of deciding tightness of 4dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all nontrivial inputs, we show that the treewidths of both the 1skeleton and the dual graph must grow too quickly for a standard treewidthbased algorithm to remain tractable. 
Coloring Points with Respect to Squares
[DOI]
[+] Eyal Ackerman, Balázs Keszegh and Mate Vizer We consider the problem of 2coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set S of points in the plane can be 2colored such that every axisparallel square that contains at least m points from S contains points of both colors. Our proof is constructive, that is, it provides a polynomialtime algorithm for obtaining such a 2coloring. By affine transformations this result immediately applies also when considering homothets of a fixed parallelogram. 

10:00  10:20 
On Expansion and Topological Overlap
[DOI]
[+] Dominic Dotterrer, Tali Kaufman and Uli Wagner We give a detailed and easily accessible proof of Gromov's Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higherdimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map X rightarrow R^{d} there exists a point p in R^{d} whose preimage intersects a positive fraction mu > 0 of the dcells of X. More generally, the conclusion holds if R^{d} is replaced by any ddimensional piecewiselinear (PL) manifold M, with a constant mu that depends only on d and on the expansion properties of X, but not on M. 
Anchored Rectangle and Square Packings
[DOI]
[+] Kevin Balas, Adrian Dumitrescu and Csaba Toth For points p_{1},...,p_{n} in the unit square [0,1]^{2}, an anchored rectangle packing consists of interiordisjoint axisaligned empty rectangles r_{1},...,r_{n} in [0,1]^{2} such that point p_{i} is a corner of the rectangle r_{i} (that is, r_{i} is anchored at p_{i}) for i=1,...,n. We show that for every set of n points in [0,1]^{2}, there is an anchored rectangle packing of area at least 7/12O(1/n), and for every n, there are point sets for which the area of every anchored rectangle packing is at most 2/3. The maximum area of an anchored square packing is always at least 5/32 and sometimes at most 7/27. The above constructive lower bounds immediately yield constantfactor approximations, of 7/12 epsilon for rectangles and 5/32 for squares, for computing anchored packings of maximum area in O(n log n) time. We prove that a simple greedy strategy achieves a 9/47approximation for anchored square packings, and 1/3 for lowerleft anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored rectangle and square packings in n^{O(1/epsilon)} and exp(poly(log (n/epsilon))) time, respectively. 

10:20  10:50 
Coffee break  
Session 6A Chair: Éric Colin de Verdière 
Session 6B Chair: Takeshi Tokuyama 

10:50  11:10 
AllPairs Minimum Cuts in NearLinear Time for
SurfaceEmbedded Graphs
[DOI]
[+] Glencora Borradaile, David Eppstein, Christian WulffNilsen and Amir Nayyeri For an undirected nvertex graph G with nonnegative edgeweights, we consider the following type of query: given two vertices s and t in G, what is the weight of a minimum stcut in G? We solve this problem in preprocessing time O(n log^{3} n) for graphs of bounded genus, giving the first subquadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and WulffNilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a GomoryHu tree for the given graph, providing a data structure with space O(n) that can answer minimumcut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is 2^{O(g^{2})}. 
Approximating Convex Shapes with Respect to
Symmetric Difference Under Homotheties
[DOI]
[+] Juyoung Yon, Sang Won Bae, SiuWing Cheng, Otfried Cheong and Bryan Wilkinson The symmetric difference is a robust operator for measuring the error of approximating one shape by another. Given two convex shapes P and C, we study the problem of minimizing the volume of their symmetric difference under all possible scalings and translations of C. We prove that the problem can be solved by convex programming. We also present a combinatorial algorithm for convex polygons in the plane that runs in O((m+n) log^{3}(m+n)) expected time, where n and m denote the number of vertices of P and C, respectively. 

11:10  11:30 
Shortest Path Embeddings of Graphs on Surfaces
[DOI]
[+] Alfredo Hubard, Vojtěch Kaluža, Arnaud de Mesmay and Martin Tancer The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding. The main question addressed in this paper is whether given a closed surface S, there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces. We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property. Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g, there exist graphs G embeddable into the orientable surface of genus g, such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G, where the probability measure is proportional to the WeilPetersson volume on moduli space. Finally, we construct a hyperbolic metric on every orientable surface S of genus g, such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O(g) shortest paths. 
Random Sampling with Removal
[DOI]
[+] Bernd Gärtner, Johannes Lengler and May Szedlak Random sampling is a classical tool in constrained optimization. Under favorable conditions, the optimal solution subject to a small subset of randomly chosen constraints violates only a small subset of the remaining constraints. Here we study the following variant that we call random sampling with removal: suppose that after sampling the subset, we remove a fixed number of constraints from the sample, according to an arbitrary rule. Is it still true that the optimal solution of the reduced sample violates only a small subset of the constraints? The question naturally comes up in situations where the solution subject to the sampled constraints is used as an approximate solution to the original problem. In this case, it makes sense to improve cost and volatility of the sample solution by removing some of the constraints that appear most restricting. At the same time, the approximation quality (measured in terms of violated constraints) should remain high. We study random sampling with removal in a generalized, completely abstract setting where we assign to each subset R of the constraints an arbitrary set V(R) of constraints disjoint from R; in applications, V(R) corresponds to the constraints violated by the optimal solution subject to only the constraints in R. Furthermore, our results are parametrized by the dimension d, i.e., we assume that every set R has a subset B of size at most d with the same set of violated constraints. This is the first time this generalized setting is studied. In this setting, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k elements. For a large range of values of k, the new upper bounds improve the previously best bounds for LPtype problems, which moreover had only been known in special cases. We show that this bound on special LPtype problems, can be derived in the much more general setting of violator spaces, and with very elementary proofs. 

11:30  11:50 
Minimum Cycle and Homology Bases of Surface Embedded Graphs
[DOI]
[+] Glencora Borradaile, Erin Wolf Chambers, Kyle Fox and Amir Nayyeri We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1dimensional (Z_{2})homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA '09] and a deterministic O(n^{3}) time algorithm [Mehlhorn and Michail, TALG '09]. For the minimum homology basis problem, we give an O(g^{3} n log n)time algorithm, improving on existing algorithms for many values of g and n. 
Maxsum Diversity via Convex Programming
[DOI] [+] Alfonso Cevallos, Friedrich Eisenbrand and Rico Zenklusen Diversity maximization is an important concept in information retrieval, computational geometry and operations research. Usually, it is a variant of the following problem: Given a ground set, constraints, and a function f that measures diversity of a subset, the task is to select a feasible subset S such that f(S) is maximized. The sumdispersion function f(S) which is the sum of the pairwise distances in S, is in this context a prominent diversification measure. The corresponding diversity maximization is the "maxsum" or "sumsum" diversification. Many recent results deal with the design of constantfactor approximation algorithms of diversification problems involving sumdispersion function under a matroid constraint. In this paper, we present a PTAS for the maxsum diversity problem under a matroid constraint for distances d(.,.) of negative type. Distances of negative type are, for example, metric distances stemming from the L_{2} and L_{1} norms, as well as the cosine or spherical, or Jaccard distance which are popular similarity metrics in web and image search. Our algorithm is based on techniques developed in geometric algorithms like metric embeddings and convex optimization. We show that one can compute a fractional solution of the usually nonconvex relaxation of the problem which yields an upper bound on the optimum integer solution. Starting from this fractional solution, we employ a deterministic rounding approach which only incurs a small loss in terms of objective, thus leading to a PTAS. This technique can be applied to other previously studied variants of the maxsum dispersion function, including combinations of diversity with linearscore maximization, improving over the previous constantfactor approximation algorithms. 

11:50  12:10 
Untangling Planar Curves
[DOI]
[+] HsienChih Chang and Jeff Erickson Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with n selfcrossings requires Theta(n^{3/2}) homotopy moves in the worst case. Our algorithm improves the best previous upper bound O(n^{2}), which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large *defect*, a topological invariant of generic closed curves introduced by Aicardi and Arnold. This lower bound also implies that Omega(n^{3/2}) degree1 reductions, seriesparallel reductions, and DeltaY transformations are required to reduce any planar graph with treewidth Omega(sqrt{n}) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs. Finally, we prove that Omega(n^{2}) homotopy moves are required in the worst case to transform one noncontractible closed curve on the torus to another; this lower bound is tight if the curve is homotopic to a simple closed curve. 
Finding Global Optimum for Truth Discovery:
Entropy Based Geometric Variance
[DOI]
[+] Hu Ding, Jing Gao and Jinhui Xu Truth Discovery is an important problem arising in data analytics related fields such as data mining, database, and big data. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. Due to its importance, the problem has been extensively studied in recent years and a number techniques have already been proposed. However, all of them are of heuristic nature and do not have any quality guarantee. In this paper, we formulate the problem as a high dimensional geometric optimization problem, called Entropy based Geometric Variance. Relying on a number of novel geometric techniques (such as LogPartition and Modified Simplex Lemma), we further discover new insights to this problem. We show, for the first time, that the truth discovery problem can be solved with guaranteed quality of solution. Particularly, we show that it is possible to achieve a (1+eps)approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications. 

12:10  12:25 
YRF Preview (for Thursday's talks)  
12:25  14:00 
Lunch  
Multimedia room open through lunch and the afternoon  
14:00  15:30 
A: Young Researchers Forum  B: Workshop 3: 5th Mini Symposium on Computational Topology, Part II [Web] [+] Organizers: Justin Curry, Pawel Dlotko, Michael Lesnick and Clement Maria Applications and algorithms for computational topology. This part focuses on practical problems in which topology is used in (large scale) engineering and life sciences computations. This includes granular and material science, fluid dynamics, electromagnetism, neurobiology and surrounding areas. We will also present recent algorithmic developments and applications of computational topology. 
C: Workshop 4: Tutorials on Ricci flow and optimal transportation [Web] [+] Organizers: David Xianfeng Gu and Na Lei This tutorial has two parts. Part I is on (surface) Ricci flow. Surface Ricci flow gives the solution to a highly nonlinear metric PDE: Yamabe's equation. The computational algorithms is based on the convex optimization, and the theoretical framework has been applied to graphics, vision, geometric modeling, networking and medical imaging fields. Part II is on Optimal transportation. Optimal mass transportation map transforms one probability measure to the other in the most economic way. This tutorial introduces a variational framework to solve the problem. The algorithm is closely related to upper envelop, power Voronoi diagram, power Delaunay triangulation in classical computational geometry. 

14:00 
On Minimum Area Homotopies
[+] Brittany Fasy, Selcuk Karakoc and Carola Wenk In this work, we will define the minimum homotopy area for closed curves and we will give a method to calculate it. The minimum homotopy area between two simple curves are defined by E. Chambers and Y. Wang, and they gave an algorithm to compute it. This work is a generalization of theirs. Our method will be first calculating it for a class of curves, namely selfoverlapping curves and then breaking a general curve into selfoverlapping subcurves. We will also give some properties of a minimum homotopy, one that minimizes the area. 14:15  Homology Localization by Hierarchical Blowups [+] Ahmed Abdelrazek Topological descriptors such as the generators of homology groups are very useful in the analysis of complex data sets. It is often desired to find the smallest such generators to help localize the interesting features. One interpretation of localization utilizes a covering of the underlying space and computes generators contained within these covers. A similar construction was later used to compute persistence homology for smaller subsets in parallel before gluing the results. In this presentation, we describe a more efficient version of this construction and discuss how it can be used to find generators within a large class of subspaces. 14:30  Certified Homology Inference [+] Nicholas Cavanna, Kirk Gardner and Donald Sheehy The goal of homology inference is to compute the shape of a space from a finite point set sampled near it. Given such a sample, one may want to know when we can reliably infer the homology of the space in question. Naturally, this requires making assumptions on the sample as well as the underlying space. Niyogi, Smale, and Weinberger showed that one can infer the homology of a smooth manifold from finite points chosen uniformly at random. Chazal and Lieutier relaxed this to include nonsmooth bounded spaces in R^d via the socalled weak feature size. Both assume good samples in the sense that there must be a sampled point within ? of every point in the space. Vin de Silva and Robert Ghrist showed how to certify if a point set contains a good sample of a shrunken version of a space assuming one can compute the distance from a point to the boundary. We show when and how these approaches can be combined in order to provide a computable inference of the homology of the domain. We do so on more general spaces in R^d, only assuming a lower bound on the weak feature size of a compact, locally contractible domain, and that we can compute the distance to the boundary. 14:45  Generalized Coverage in Homological Sensor Networks [+] Kirk Gardner, Nicholas Cavanna and Don Sheehy In their seminal work on homological sensor networks, de Silva and Ghrist showed the surprising fact that it's possible to certify the coverage of a coordinatefree sensor network even with very minimal knowledge of the space to be covered [2]. We give a new, simpler proof of the de SilvaGhrist Topological Coverage Criterion (TCC) that eliminates any assumptions about the smoothness of the boundary of the underlying space, allowing the results to be applied to much more general problems. The new proof factors the geometric, topological, and combinatorial aspects of this approach. This allows us to extend the TCC to support kcoverage, in which the domain is covered by k sensors, and weighted coverage, in which sensors have varying sensing radii. 15:00  Local Structures for Approximating Rips Filtrations [+] Aruni Choudhary, Michael Kerber and Sharath Raghvendra (Vietoris)Rips filtrations are important structures used to infer topological properties of metric spaces. Unfortunately, they pose a significant computational challenge, particularly when the data has high dimension. We present a new technique to $O(\sqrt{d})$approximate the topological information carried by the Rips filtration, with at most $n2^{O(d\log d)}$ $d$simplices per scale in the filtration. 15:15  Homology Preserving Simplification for Topbased Representations [+] Federico Iuricich, Riccardo Fellegara and Leila De Floriani Topological features provide global quantitative and qualitative information about a shape, such as the number of the connected components, and the number of holes and tunnels. These information are especially important in highdimensional data analysis, where pure geometric tools are usually not sufficient. When dealing with simplicial homology, the size of simplicial complex is the major concern, since all the algorithms available in literature are mainly affected by the number of simplices of the complex. The classical approach for computing the homology of a simplicial complex is based on the Smith Normal Form (SNF) reduction applied to the boundary matrices describing the boundary maps. This method is theoretically valid in any dimension, but it has intrinsic limitations linked to the size of matrices and to the high complexity of reduction algorithms. Other methods have been proposed for improving the performances of SNF reduction, but the only scalable approach still remains the simplification of the original complex in order to reduce its size without changing its homology. Edge contraction is from a long time a tool of choice for simplifying simplicial complexes. It has been used in computer graphics and visualization and more recently in topological data analysis for reducing the size of higher dimensional simplicial complexes. Edge contraction on its own does not preserve the homological information but a check, called link condition, has been developed for verifying whether the contraction of an edge preserves homology or not. In our work, we consider the efficient definition of a simplification algorithm, that combines an efficient topbased representation for a simplicial complex with an edge contraction simplification procedure. Our contribution is: (i) the definition of a dimensionindependent edge contraction and of a link condition for topbased representations; (ii) the implementation of an efficient algorithm for computing and simplifying a dsimplicial complex on a specific topbased representation, the Stellar tree and (iii) an experimental comparison with respect to the stateoftheart data structure for performing edge contractions, the Skeleton Blockers. 
14:00  14:20 Tamal Dey SimBa: A Tool for Approximating the Persistence of Rips Filtrations Efficiently 14:30  14:50 Matthew Wright Visualizing Multidimensional Persistent Homology 15:00  15:20 Jisu Kim R Package TDA for Statistical Inference on Topological Data Analysis 
14:00  14:45 David Gu Theories of Discrete Ricci Flow 14:45  15:30 Jie Gao Applications of Discrete Ricci Flow 

15:30  16:00 
Coffee break  
16:00  17:30 
A: Young Researchers Forum  B: Workshop 3 (continued) 5th Mini Symposium on Computational Topology, Part II 
C: Workshop 4 (continued) Tutorials on Ricci Flow and Optimal Transportation 

16:00 
Classification of Normal Curves on a Tetrahedron
[+] Clément Maria and Jonathan Spreer In this article, we give a combinatorial classification of all normal curves drawn on the boundary of a tetrahedron. We characterise normal curves in terms of intersection numbers with the edges of the tetrahedron. 16:15  Barycentric Coordinate Neighbourhoods in Riemannian Manifolds [+] Ramsay Dyer, Gert Vegter and Mathijs Wintraecken We quantify conditions that ensure that a signed measure on a Riemannian manifold has a well defined centre of mass. We then use this result to quantify the extent of a neighbourhood on which the Riemannian barycentric coordinates of a set of $n+1$ points on an $n$manifold provide a true coordinate chart, i.e., the barycentric coordinates provide a diffeomorphism between a neighbourhood of a Euclidean simplex, and a neighbourhood containing the points on the manifold. 16:30  Spectral Properties of Distance Matrices of High Dimensional Mixtures [+] JeanDaniel Boissonnat, David CohenSteiner and Alba Chiara De Vitis We use spectral analysis of the distance matrices of high dimensional mixtures to learn a mixture of distributions. Our approach focuses on highdimensional mixtures and uses concentration of measure. It applies to any distribution with concentration properties. 16:45  Towards the Analysis of Multivariate Data Based on Discrete Morse Theory [+] Sara Scaramuccia, Federico Iuricich, Claudia Landi and Leila De Floriani We propose a new algorithm for computing a Forman gradient on a CWcomplex on which a vectorvalued function is defined. We prove that our algorithm is equivalent to the stateoftheart algorithms, i.e., it retrieves a Forman gradient compatible with the multidimensional persistent homology induced by the vectorvalued function, being at the same time faster and more compact. 17:00  Transforming Hierarchical Trees on Metric Spaces [+] Mahmoodreza Jahanseir and Donald Sheehy We show how a simple metric hierarchical tree called a cover tree transforms into a more complex one called a nettree in linear time. We also propose two linear time algorithms to make a tradeoff between depth and the degree of nodes in cover trees. 17:15  Almost All Even YaoYao Graphs Are Spanners [+] Wei Zhan and Jian Li In this abstract we show that, for any integer $k\geq 42$, the YaoYao graph $\YY{2k}$ is a $t_k$spanner, with stretch factor $t_k=4.27+O(k^{1})$ when $k$ tends to infinity. Our result generalizes the best known result which asserts that all $\YY{6k}$ are spanners for $k$ large enough [Bauer and Damian, SODA'13]. 
16:00  16:20 Yongjin Lee Topological Data Analysis of Nanoporous Materials Genome Using PoreGeometry Recognition Technique 16:30  16:50 Ellen Gasparovic MultiScale Modeling for Stratified Space Data 17:00  17:20 Pablo Camara Topological Methods for Molecular Phylogenetics 
16:00  16:45 Feng Luo Theory of Optimal Mass Transportation 16:45  17:30 Na Lei Applications of Optimal Mass Transportation 

17:30  19:00 
Business meeting  
 Friday
Friday June 17  
Session 7A Chair: Wolfgang Mulzer 
Session 7B Chair: Jeff Phillips 

9:00  9:20 
Dimension Reduction Techniques for L_{p} (1<p<2),
with Applications
[DOI]
[+] Yair Bartal and LeeAd Gottlieb For Euclidean space (L_{2}), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss [Conf. in modern analysis and probability, AMS 1984], with a host of known applications. Here, we consider the problem of dimension reduction for all L_{p} spaces 1<p<2. Although strong lower bounds are known for dimension reduction in L_{1}, Ostrovsky and Rabani [JACM 2002] successfully circumvented these by presenting an L_{1} embedding that maintains fidelity in only a bounded distance range, with applications to clustering and nearest neighbor search. However, their embedding techniques are specific to L_{1} and do not naturally extend to other norms. In this paper, we apply a range of advanced techniques and produce bounded range dimension reduction embeddings for all of 1<p<2, thereby demonstrating that the approach initiated by Ostrovsky and Rabani for L_{1} can be extended to a much more general framework. We also obtain improved bounds in terms of the intrinsic dimensionality. As a result we achieve improved bounds for proximity problems including snowflake embeddings and clustering. 
On the Complexity of MinimumLink Path
Problems
[DOI]
[+] Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk and Frank Staals We revisit the minimumlink path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the minlink path's vertices or edges can be restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomialtime approximation scheme. We fully characterize the situation in 2D, and provide first results in dimensions 3 and higher for several versions of the problem. Concretely, our results resolve several open problems. We prove that computing the minimumlink diffuse reflection path, motivated by ray tracing in computer graphics, is NPhard, even for twodimensional polygonal domains with holes. This has remained an open problem [Ghosh et al. 2012] despite a large body of work on the topic. We also resolve the open problem from [Mitchell et al. 1992] mentioned in the handbook [Goodman and O'Rourke, 2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [Demaine et al. TOPP] (see Problem 22): "What is the complexity of the minimumlink path problem in 3space?" Our results imply that the problem is NPhard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS. 
9:20  9:40 
Simultaneous Nearest Neighbor Search
[DOI]
[+] Piotr Indyk, Robert Kleinberg, Sepideh Mahabadi and Yang Yuan Motivated by applications in computer vision and databases, we introduce and study the Simultaneous Nearest Neighbor Search (SNN) problem. Given a set of data points, the goal of SNN is to design a data structure that, given a *collection* of queries, finds a *collection* of close points that are *compatible* with each other. Formally, we are given k query points Q=q_{1},...,q_{k}, and a compatibility graph G with vertices in Q, and the goal is to return data points p_{1},...,p_{k} that minimize (i) the weighted sum of the distances from q_{i} to p_{i} and (ii) the weighted sum, over all edges (i,j) in the compatibility graph G, of the distances between p_{i} and p_{j}. The problem has several applications in computer vision and databases, where one wants to return a set of *consistent* answers to multiple related queries. Furthermore, it generalizes several wellstudied computational problems, including Nearest Neighbor Search, Aggregate Nearest Neighbor Search and the 0extension problem. In this paper we propose and analyze the following general twostep method for designing efficient data structures for SNN. In the first step, for each query point q_{i} we find its (approximate) nearest neighbor point p'_{i}; this can be done efficiently using existing approximate nearest neighbor structures. In the second step, we solve an offline optimization problem over sets q_{1},...,q_{k} and p'_{1},...,p'_{k}; this can be done efficiently given that k is much smaller than n. Even though p'_{1},...,p'_{k} might not constitute the optimal answers to queries q_{1},...,q_{k}, we show that, for the unweighted case, the resulting algorithm satisfies a O(log k/log log k)approximation guarantee. Furthermore, we show that the approximation factor can be in fact reduced to a constant for compatibility graphs frequently occurring in practice, e.g., 2D grids, 3D grids or planar graphs. Finally, we validate our theoretical results by preliminary experiments. In particular, we show that the *empirical approximation factor* provided by the above approach is very close to 1. 
Recognizing Weakly Simple Polygons
[DOI]
[+] Hugo Akitaya, Greg Aloupis, Jeff Erickson and Csaba Toth We present an O(n log n)time algorithm that determines whether a given planar ngon is weakly simple. This improves upon an O(n^{2} log n)time algorithm by [Chang, Erickson, and Xu, SODA, 2015]. Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question. 
9:40  10:00 
Two Approaches to Building TimeWindowed
Geometric Data Structures
[DOI]
[+] Timothy M. Chan and Simon Pratt Given a set of geometric objects each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems timewindowed decision problems, and they have been the subject of much recent attention, for instance studied by Bokal, Cabello, and Eppstein [SoCG 2015]. In this paper, we present new approaches to this class of problems that are conceptually simpler than Bokal et al.'s, and also lead to faster algorithms. For instance, we present algorithms for preprocessing for the timewindowed 2D diameter decision problem in O(n log n) time and the timewindowed 2D convex hull area decision problem in O(n alpha(n) log n) time (where alpha is the inverse Ackermann function), improving Bokal et al.'s O(n log^{2} n) and O(n log n loglog n) solutions respectively. Our first approach is to reduce timewindowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our other approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is near linear for any FIFO update sequence, in which deletions occur in the same order as insertions. We also apply these approaches to obtain the first O(n polylog n) algorithms for the timewindowed 3D diameter decision and 2D orthogonal segment intersection detection problems. 
Subexponential Algorithms for Rectilinear Steiner
Tree and Arborescence Problems
[DOI]
[+] Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh A rectilinear Steiner tree for a set T of points in the plane is a tree which connects T using horizontal and vertical lines. In the Rectilinear Steiner Tree problem, input is a set T of n points in the Euclidean plane (R^{2}) and the goal is to find an rectilinear Steiner tree for T of smallest possible total length. A rectilinear Steiner arborescence for a set T of points and root r in T is a rectilinear Steiner tree S for T such that the path in S from r to any point t in T is a shortest path. In the Rectilinear Steiner Arborescence problem the input is a set T of n points in R^{2}, and a root r in T, the task is to find an rectilinear Steiner arborescence for T, rooted at r of smallest possible total length. In this paper, we give the first subexponential time algorithms for both problems. Our algorithms are deterministic and run in 2^{O(sqrt{n}log n)} time. 
10:00  10:20 
Faster Algorithms for Computing Plurality Points
[DOI]
[+] Mark de Berg, Joachim Gudmundsson and Mehran Mehr Let V be a set of n points in R^{d}, which we call voters, where d is a fixed constant. A point p in R^{d} is preferred over another point p' in R^{d} by a voter v in V if dist(v,p) < dist(v,p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L_{2} norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V  W admits a plurality point, and to compute a socalled minimumradius plurality ball. Finally, we consider the problem in the personalized L_{1} norm, where each point v in V has a preference vector <w_{1}(v), ...,w_{d(v)}> and the distance from v to any point p in R^{d} is given by sum_{i=1}^{d} w_{i}(v) cdot x_{i}(v)x_{i}(p). For this case we can compute in O(n^{d1}) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n). 
A lower Bound on Opaque Sets
[DOI]
[+] Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi and Janos Pach It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle. 
10:20  10:40 
Tight Lower Bounds for DataDependent
LocalitySensitive Hashing
[DOI]
[+] Alexandr Andoni and Ilya Razenshteyn We prove a tight lower bound for the exponent rho for datadependent LocalitySensitive Hashing schemes, recently used to design efficient solutions for the capproximate nearest neighbor search. In particular, our lower bound matches the bound of rho<= 1/(2c1)+o(1) for the L_{1} space, obtained via the recent algorithm from [AndoniRazenshteyn, STOC'15]. In recent years it emerged that datadependent hashing is strictly superior to the classical LocalitySensitive Hashing, when the hash function is dataindependent. In the latter setting, the best exponent has been already known: for the L_{1} space, the tight bound is rho=1/c, with the upper bound from [IndykMotwani, STOC'98] and the matching lower bound from [O'DonnellWuZhou, ITCS'11]. We prove that, even if the hashing is datadependent, it must hold that rho>=1/(2c1)o(1). To prove the result, we need to formalize the exact notion of datadependent hashing that also captures the complexity of the hash functions (in addition to their collision properties). Without restricting such complexity, we would allow for obviously infeasible solutions such as the Voronoi diagram of a dataset. To preclude such solutions, we require our hash functions to be succinct. This condition is satisfied by all the known algorithmic results. 
Finding the Maximum Subset with Bounded
Convex Curvature
[DOI]
[+] Mikkel Abrahamsen and Mikkel Thorup We describe an algorithm for solving an important geometric problem arising in computeraided manufacturing. When machining a pocket in a solid piece of material such as steel using a rough tool in a milling machine, sharp convex corners of the pocket cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a tool path that maximizes the use of the rough tool. Mathematically, this boils down to the following problem. Given a simplyconnected set of points P in the plane such that the boundary of P is a curvilinear polygon consisting of n line segments and circular arcs of arbitrary radii, compute the maximum subset Q of P consisting of simplyconnected sets where the boundary of each set is a curve with bounded convex curvature. A closed curve has bounded convex curvature if, when traversed in counterclockwise direction, it turns to the left with curvature at most 1. There is no bound on the curvature where it turns to the right. The difference in the requirement to left and rightcurvature is a natural consequence of different conditions when machining convex and concave areas of the pocket. We devise an algorithm to compute the unique maximum such set Q. The algorithm runs in O(n log n) time and uses O(n) space. For the correctness of our algorithm, we prove a new generalization of the PestovIonin Theorem. This is needed to show that the output Q of our algorithm is indeed maximum in the sense that if Q' is any subset of P with a boundary of bounded convex curvature, then Q' is a subset of Q. 
10:40  11:10 
Coffee break  
Session 8A Chair: Micha Sharir 
Session 8B Chair: Nina Amenta 

11:10  11:30 
Peeling and Nibbling the Cactus:
SubexponentialTime Algorithms for Counting
Triangulations and Related Problems
[DOI]
[+] Dániel Marx and Tillmann Miltzow Given a set of n points S in the plane, a triangulation T of S is a maximal set of noncrossing segments with endpoints in S. We present an algorithm that computes the number of triangulations on a given set of n points in time n^{ (11+ o(1)) sqrt{n} }, significantly improving the previous best running time of O(2^{n} n^{2}) by Alvarez and Seidel [SoCG 2013]. Our main tool is identifying separators of size O(sqrt{n}) of a triangulation in a canonical way. The definition of the separators are based on the decomposition of the triangulation into nested layers (``cactus graphs''). Based on the above algorithm, we develop a simple and formal framework to count other noncrossing straightline graphs in n^{O(sqrt{n})} time. We demonstrate the usefulness of the framework by applying it to counting noncrossing Hamilton cycles, spanning trees, perfect matchings, 3colorable triangulations, connected graphs, cycle decompositions, quadrangulations, 3regular graphs, and more. 
On the Combinatorial Complexity of
Approximating Polytopes
[DOI]
[+] Sunil Arya, Guilherme D. da Fonseca and David Mount Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body K of diameter diam(K) is given in Euclidean ddimensional space, where d is a constant. Given an error parameter eps > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most eps diam(K). By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A wellknown result by Dudley implies that O(1/eps^{(d1)/2}) facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is Otilde(1/eps^{(d1)/2}), where Otilde conceals a polylogarithmic factor in /eps. This is an improvement upon the best known bound, which is roughly O(1/eps^{d2}). Our result is based on a novel combination of both new and old ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a widthbased variant of Barany and Larman's economical cap covering, which may be of independent interest. Finally, we use a deterministic variation of the witnesscollector technique (developed recently by Devillers et al.) in the context of our stratified construction. 
11:30  11:50 
An Improved Lower Bound on the Number of
Triangulations
[DOI]
[+] Oswin Aichholzer, Victor Alvarez, Thomas Hackl, Alexander Pilz, Bettina Speckmann and Birgit Vogtenhuber Upper and lower bounds for the number of geometric graphs of specific types on a given set of points in the plane have been intensively studied in recent years. For most classes of geometric graphs it is now known that point sets in convex position minimize their number. However, it is still unclear which point sets minimize the number of geometric triangulations; the socalled double circles are conjectured to be the minimizing sets. In this paper we prove that any set of n points in general position in the plane has at least Omega(2.631^{n}) geometric triangulations. Our result improves the previously best general lower bound of Omega(2.43^{n}) and also covers the previously best lower bound of Omega(2.63^{n}) for a fixed number of extreme points. We achieve our bound by showing and combining several new results, which are of independent interest: (1) Adding a point on the second convex layer of a given point set (of 7 or more points) at least doubles the number of triangulations. (2) Generalized configurations of points that minimize the number of triangulations have at most n/2 points on their convex hull. (3) We provide tight lower bounds for the number of triangulations of point sets with up to 15 points. These bounds further support the double circle conjecture. 
Dynamic Streaming Algorithms for EpsilonKernels
[DOI]
[+] Timothy M. Chan Introduced by Agarwal, HarPeled, and Varadarajan [J. ACM, 2004], an epsilonkernel of a point set is a coreset that can be used to approximate the width, minimum enclosing cylinder, minimum bounding box, and solve various related geometric optimization problems. Such coresets form one of the most important tools in the design of lineartime approximation algorithms in computational geometry, as well as efficient insertiononly streaming algorithms and dynamic (nonstreaming) data structures. In this paper, we continue the theme and explore dynamic streaming algorithms (in the socalled turnstile model). Andoni and Nguyen [SODA 2012] described a dynamic streaming algorithm for maintaining a (1+epsilon)approximation of the width using O(polylog U) space and update time for a point set in [U]^{d} for any constant dimension d and any constant epsilon>0. Their sketch, based on a "polynomial method", does not explicitly maintain an epsilonkernel. We extend their method to maintain an epsilonkernel, and at the same time reduce some of logarithmic factors. As an application, we obtain the first randomized dynamic streaming algorithm for the width problem (and related geometric optimization problems) that supports k outliers, using poly(k, log U) space and time. 
11:55  12:55 
Invited Talk: Jacob Fox, Discrete Geometry, Algebra, and Combinatorics
[+] Many problems in discrete and computational geometry can be viewed as finding patterns in graphs or hypergraphs which arise from geometry or algebra. Famous Ramsey, Turán, and Szemeréditype results prove the existence of certain patterns in graphs and hypergraphs under mild assumptions. We survey recent results which show much stronger/larger patterns for graphs and hypergraphs that arise from geometry or algebra. We further discuss whether the stronger results in these settings are due to geometric, algebraic, combinatorial, or topological properties of the graphs. 

12:55  14:30 
Lunch  
Workshop in Honor of Bernard Chazelle's 60th Birthday [Web]  
14:30  14:40 
Pankaj Agarwal, Opening Remarks  
14:40  15:20 
David Dobkin, Bernard's Research in the 70's
[+] As Bernard's thesis advisor, I introduced him to the field of computational geometry when he was a first year graduate student. In this talk, I survey the situation at that time, his early results and further research they have inspired. 

15:20  16:00 
Micha Sharir, From 60 BC to BC 60: Computational Geometry and Bernard (and me)
[+] In the talk I will review some significant milestones in Bernard Chazelle's work during the late 1980s and the 1990s, Including his work on cuttings, arrangements, range searching, discrepancy, and some other topics. I will mix the scientific contents with nostalgic anecdotes that highlight lighter aspects of Chazelle's otherwise deep, fundamental, and highly influential contributions to geometry. 

16:00  16:30 
Coffee break  
16:30  17:10 
Ken Clarkson, The Thrill Goes On: Bernard Yesterday and Today
[+] From the excruciatingly difficult to the achingly elegant, Bernard Chazelle's work on algorithms, especially geometric or natural ones, has been profoundly influential. I'll sketch a few examples that have been inspiring to me, including 1dimensional range queries, lowstabbing spanning trees, highorder Voronoi diagram construction, deterministic constructions, and the senergy of a system. 

17:10  18:00 
Presentation by former students of Bernard  
18:00  20:00 
BC60 evening reception
[+] Location: Jaharis Center courtyard (across street from SoCG) Please bring ID. 

 Saturday
Saturday June 18, SoCG + STOC, Hyatt Regency in Cambridge, MA  
9:00  10:45 
Workshop A: 1st International Workshop on Geometry and Machine Learning [Web] [+] Organizers: Jonathan Lenchner, Eli Packer, Jeff M. Phillips and Jinhui Xu Computational geometry plays a crucial and natural role in interacting with machine learning. Since geometric algorithms often come with quality guaranteed solutions, they are of critical importance in formalizing the effectiveness of various techniques and in developing new ones. On the other hand, problems in machine learning serve as important motivation for work central to geometric algorithms. This workshop is intended to provide a forum for those working in the fields of computational geometry, algorithms, machine learning and the various theoretical and algorithmic challenges to promote their interplay. As a joint STOC/SoCG workshop, we hope researchers who normally frequent only one of STOC or SoCG, but work in geometric algorithms for machine learning, will converge together sharing their insights and developments. 
Workshop B: Spanners: Graphs and Geometry [Web] [+] Organizers: Shiri Chechik, Michael Dinitz, and Virginia Vassilevska Williams Spanners, i.e. subgraphs which approximately preserve distances, have been studied in both graph and geometric settings for over 25 years. While there has been some limited interaction between researchers working in graphtheoretic settings and researchers working in geometric settings, work in the two communities has generally proceeded in parallel rather than in cooperation. The goal of this workshop is to bring together researchers interested in spanners (and other aspects of distance compression) in order to summarize and explore the state of the art, transition definitions and techniques between the communities, and explore questions about spanners and related objects that are of interest to both communities. 
Workshop C: Algorithms on Topologically Restricted Graphs [Web] [+] Organizers: Kenichi Kawarabayashi and Anastasios Sidiropoulos The workshop will focus on recent algorithmic advancements on problems on topologically restricted graphs, such as planar, surfaceembedded, small treewidth, minorfree graphs, and graphs of small crossing number. The goal will be to emphasize developments that are of importance in the areas of fixed parameter tractability, approximation algorithms, topological graph theory, and metric embeddings. The program will attempt to highlight developments that are of importance in all of these areas, and emphasize technical connections between them. 
Workshop D: Tutorial: Hardness of Learning [Web] [+] Organizer: Amit Daniely Proving hardness of learning problems is a key challenge in Valiant's PAC learning model. As reductions from NPhard problems do not seem to apply in this context, this area evolved somewhat separately. Traditionally, hardness of learning was proved under cryptographic assumptions. Such assumptions imply that it is hard to learn logdepth circuits, intersections of halfspaces, and more. More recently a new technique was developed for proving hardness of learning based on hardness on average of Constraint Satisfaction Problems like KSAT and KXOR. In particular, such assumptions imply that already very simple classes, like DNF formulas, are hard to learn. The tutorial will cover most central hardness of learning techniques and results, with emphasis on the aforementioned recent progress. 
9:00  9:50 Piotr Indyk Invited Talk: New Algorithms for Similarity Search in High Dimensions 9:55  10:20 Chao Chen High Dimensional Mode Estimation via Graphical Models 10:20  10:45 Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang Declutter and Resample: Towards Parameter Free Denoising 
9:00  9:15 Virginia VassilevskaWilliams Welcome 9:15  9:45 Shay Solomon A nonGeometric Approach to Geometric Spanners [+] A geometric (1 + epsilon)spanner for a point set S in the plane is a sparse subgraph of the complete Euclidean graph corresponding to S, which preserves all pairwise distances to within a factor of 1 + epsilon. This definition can be extended to higherdimensional Euclidean spaces, and more generally, to metric spaces of low intrinsic dimension. Geometric spanners have been intensively studied since the mid80s, with applications ranging from compact routing and distance oracles to robotics and machine learning. In many of these applications, the spanners should achieve additional properties besides sparseness, in particular small weight, degree and (hop)diameter. Understanding the inherent tradeoffs between these parameters is a fundamental challenge in this area. In this talk I will discuss novel nongeometric techniques to geometric spanners, and demonstrate their effectiveness in solving several longstanding open questions. The main message of my talk is somewhat surprising  the right approach to geometric spanners is often nongeometric. 9:45  10:15 Fabrizio Grandoni New FaultTolerant Preservers and Spanners [+] In this paper we study the existence and computation of sparse (pairwise) ffaulttolerant (fFT) preservers and additive spanners, i.e. subgraphs that preserve (exactly or with some small additive error) the distances between given pairs of nodes, under the presence of f edge or vertex failures. We present a variety of results in this setting, including: (1) The first subquadratic upper bounds on the size of singlesource FT preservers in directed and undirected unweighted graphs for any number of faults f. Previously such preservers where known only for f\leq 2. Our preservers can also be used to build the first subquadraticsize 2additive fFT spanners in undirected unweighted graphs. (2) A surprising lowerbound construction showing that, for example, any O(n^{2\epsilon})size spanner needs to have additive stretch at least Omega(\epsilon f), even to approximately preserve distances for a single pair of nodes in undirected unweighted graphs. This matches asymptotically known upper bounds holding for (all pairs!) fFT spanners. (3) Motivated by the above lower bound, we study the case of singlepair preservers in weighted, directed and undirected, graphs. For f\geq 2, we give a strong Omega(n^2) lower bound for the sparsity of any fFT preserver, that holds for both the directed and the undirected case. Thus, the only nontrivial results possible are in the setting f=1. For undirected weighted graphs we show that for f=1, O(n) edges are both necessary and sufficient, and we prove an extension of this theorem that shows tight bounds for any number of node pairs. For directed graphs, we show that the 1FT singlepair preserver problem is equivalent to the pairwise preserver problem in the nonfaulty setting where Theta(n) pairs are to be preserved, thus implying that the 1FT preserver sparsity is between Omega(n^{4/3}) and O(n^{3/2}). Joint work with Greg Bodwin, Merav Parter, and Virginia Vassilevska Williams 10:15  10:45 Prosenjit Bose On Spanning Properties of Various Delaunay Graphs [+] A geometric graph G is a graph whose vertices are points in the plane and whose edges are line segments weighted by the Euclidean distance between their endpoints. In this setting, a tspanner of G is a connected spanning subgraph G' with the property that for every pair of vertices x, y, the shortest path from x to y in G' has weight at most t ? 1 times the shortest path from x to y in G. The parameter t is commonly referred to as the spanning ratio or the stretch factor. Among the many beautiful properties that Delaunay graphs possess, a constant spanning ratio is one of them. We provide an overview of various results concerning the spanning ratio among other properties of different types of Delaunay graphs and their subgraphs. 
9:00  9:30 Petr Hlineny Toroidal Grid Minors, Embedding Stretch, and Crossing Number [+] We introduce a new embedding density parameter for graphs embedded on orientable surfaces, called the stretch, and approximately relate this parameter to the size of the largest possible (and nontrivial) toroidal grid which is a minor of the graph. The approximation bounds depend only on the genus and the maximum degree. We show how to efficiently compute the stretch of a given embedding and how the stretch relates to the (planar) crossing number of the embedded graph. 9:35  10:05 Daniel Lokshtanov Subexponential Parameterized Algorithms for Planar and Apexminorfree Graphs via Low Treewidth Pattern Covering [+] We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties:  $A$ induces a subgraph of $G$ of treewidth $O(\sqrt{k}\log k)$, and  for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{O(\sqrt{k}\log^2 k)}\cdot n^{O(1)})^{1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{O(\sqrt{k} \log^2 k)} n^{O(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed $k$Path, Weighted $k$Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. Based on a joint work with Fedor V. Fomin, Daniel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh 10:10  10:40 Amir Nayyeri Minimum Cuts on Surface Embedded Graphs [+] The algorithmic problem of computing minimum cuts in graphs has been the focus of many studies in the past few decades. In planar graphs, nearly linear time algorithms has been discovered for computing an stminimum cut, a global minimum cut, and the GomoryHu tree (that represents all minimum cuts). All these algorithms rely heavily on the fact that in planar graphs the dual of a cut is a cycle. Generalizing these algorithm has been challenging as this duality cease to exist in surfaces of positive genus. In this talk, I will describe algorithms for computing minimum cuts on genus g surfaces. The running time of all these algorithm are of the form $O(f(g)n\text{polylog} n)$. The key insight is computing short cycles in all homology classes and combining them to construct the dual of the minimum cut. I describe ideas for computing minimum homologous cycles and assembling them. I will explain methods from three different papers that are results of joint work with Glencora Borradaile, Jeff Erickson, David Eppstein, Kyle Fox, Christian WulffNilsen. 
1. Introduction
The PAC model. What is known about basic PAC problems 2. Proving Hardness: Learning vs. Computation Inapplicability of NPhardness techniques. Boosting vs. Hardness of Approximation 3. Hardness Under Cryptographic assumptions 4. Hardness Under Average Case assumptions 

10:45  11:10 
Coffee break  
11:10  12:10 
Invited Talk: Santosh Vempala, The Interplay of Sampling and Optimization in High Dimension
[+] In the first part of this talk, we show how simulated annealing can be used for both logconcave sampling and convex optimization by varying parameter settings. The resulting algorithm for optimization can be viewed as an interiorpoint method needing only a membership oracle and achieving the same worstcase iteration complexity as the best possible barriers. In the second part, we present a faster sampling algorithm for polytopes which achieves subquadratic mixing time. The advantage of the algorithm, called geodesic gliding, comes from using nonEuclidean geometries where effects of the boundary are milder. Roughly speaking, geodesic gliding is an efficient discretetime simulation of a stochastic differential equation on a Riemannian manifold whose metric is defined by the Hessian of a convex function. The talk is based on joint works with Ben Cousins, Adam Kalai, Yin Tat Lee and Laci Lovasz. 

12:10  14:00 
Lunch  
14:00  15:00 
Invited Talk: Timothy Chan, Computational Geometry, from Low to High Dimensions
[+] Classical exact algorithms in computational geometry usually have run times that are exponential in the dimension. Recently, slightly subquadratic results have been found for some basic problems, such as offline orthogonal range search and offline Hamming nearest neighbor search, even when the dimension goes above logarithmic, surprisingly. I will survey these recent findings (including some work in progress and a new joint work with Josh Alman and Ryan Williams). Along the way, we will see how old geometric divideandconquer ideas (variants of range trees and kd trees) can help solve nongeometric problems, such as allpairs shortest paths, Boolean matrix multiplication, and 01 integer linear programming. In the opposite direction, we will also see how nongeometric techniques (fast matrix multiplication, circuit complexity, probabilistic polynomials, and Chebyshev polynomials) can help computational geometry. The latter techniques also give new results on offline approximate nearest neighbor search. 

15:00  15:30 
Coffee break  
15:30  18:00 
Workshop A (continued) 1st International Workshop on Geometry and Machine Learning 
Workshop B (continued) Spanners: Graphs and Geometry 
Workshop C (continued) Algorithms on Topologically Restricted Graphs 
Workshop E: Geometric Representations of Graphs [Web] [+] Organizers: Steven Chaplick and Piotr Micek The study of graphs via geometric representations is a classic topic in both computational geometry and the theory of computing. In recent years, a lot of progress has been made in the study of geometric intersection graphs. Some notable solved problems include Scheinerman's conjecture, Erdos's problem on \chiboundedness of segment graphs, and the hardness of the clique problem for segment graphs. This workshop aims to gather researchers working on these topics in order to exchange the ideas for further research. It will focus more on open problems and possible approaches rather than particular known results. Some potential topics include: computational complexity of hard geometric problems; algebraic approaches to topological drawings (e.g, HananiTutte); constrained graph embedding problems; colorings of geometric intersection graphs; and approximation algorithms in geometric settings. 
15:30  16:20 Sanjoy Dasgupta Invited talk: The Geometry of Interactive Learning [+] In the usual setup of supervised learning, there is little interaction between human and machine: a human being labels a data set and then vanishes from the picture; and at some later time, a machine is started up, given that data, and told to find a good classifier. "Interactive learning" refers to scenarios in which the human engages with the machine while learning is actually taking place. This can happen in many ways, for example: 1. The machine might ask for labels of specific, highly informative points that are chosen adaptively, rather than requiring everything to be labeled in advance. 2. If prompted, the human might indicate relevant features, for instance by highlighting a few words within a document that are highly indicative of its label. 3. For tasks that are traditionally considered unsupervised, such as clustering or embedding, an iterative refinement process can be designed in which the human keeps giving feedback on the current structure until it is finally satisfactory. I will describe a general protocol for interactive learning that includes such scenarios and that admits generic learning algorithms. The central question I'll consider is: how much interaction is needed to learn well? Can interaction significantly reduce the total human effort in the learning process? This is largely an open area of research, but it is clear that the key determiner of "interaction complexity" is the geometry of the class of structures being learned. The quantities of interest are quite different from traditional parameters associated with learning, like VC dimension. 16:25  16:50 Kush R. Varshney and Karthikeyan Natesan Ramamurthy Persistent Homology of Classifier Decision Boundaries 16:50  17:15 Justin Eldridge, Mikhail Belkin, and Yusu Wang Consistent Estimation of the Graphon Cluster Tree 17:15  17:40 Hu Ding, Yu Liu, Lingxiao Huang, and Jian Li A Geometric Approach for KMeans Clustering with Distributed Dimensions 17:40  18:00 Cyril J. Stark Global Completability of Matrix Factorizations 
15:30  16:00 Shiri Chechik NearOptimal Light Spanners [+] A spanner H of a weighted undirected graph G is a "sparse" subgraph that approximately preserves distances between every pair of vertices in G. We refer to H as a kspanner (or as a spanner with stretch k) of G for some parameter k if the distance in H between every vertex pair is at most a factor k bigger than in G. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). It is wellknown that for any positive integer k, one can efficiently construct a (2k1)spanner of G with O(n^{1+1/k}) edges where n is the number of vertices [Althöfer et al. 93]. This sizestretch tradeoff is conjectured to be optimal based on a girth conjecture of Erdös. However, the current state of the art for the second measure is not yet optimal. In this talk I am going to discuss a construction for spanners with near optimal bounds with respect to the stretch, the weight and the number of edges. Based on joint work with Christian WulffNilsen. 16:00  16:30 Ljubomir Perkovic Spanners via pgon Distance Delaunay Triangulations [+] What is the smallest maximum degree that can always be achieved for a plane (i.e., with no crossing edges) spanner of a complete Euclidean graph? This is a fundamental question and the Delaunay triangulation, a wellknown plane spanner, is a natural starting point for attempts to answer it. Delaunay triangulations have, however, proven difficult to work with. Recent progress on answering the question has relied instead on Delaunay triangulations defined using alternative distance functions. Rather than using the standard Euclidean distance based on a circle, those Delaunay triangulations are defined using distances based on (regular) pgons. Delaunay triangulations defined using pgon distances have local structural properties that make them amenable to analysis. In addition to their use in bounding the degree of plane spanners, they have been used in developing geometric routing schemes. They may also help in tackling the question of determining the exact spanning ratio (i.e., stretch factor) of Delaunay triangulations. Over the past 30 years, there has been intense interest in computing the exact spanning ratio of classic (circle distance) Delaunay triangulations. Despite that, until recently the only type of Delaunay triangulation for which the answer has been known is the triangle distance Delaunay triangulation (Chew '89). It is likely that work on the spanning ratio of pgon distance Delaunay triangulations will build the bridge leading to a better understanding of the spanning ratio of classic Delaunay triangulations. In this talk, I will review a selection of recent work that rely on pgon distance Delaunay triangulations and highlight some of their properties as well as techniques that have been developed. 16:30  17:00 Greg Bodwin Understanding Additive Spanners via Distance Preservers [+] An Additive Spanner of a graph is a sparse subgraph that preserves all pairwise distances within +k error. A Distance Preserver of a graph is a sparse subgraph that exactly preserves pairwise distances within a small set P of node pairs. There have been several recent successful lines of research that have converted existing knowledge of distance preservers into a new understanding of additive spanners. In this talk, we will discuss some of the results and techniques used in this line of attack. In particular, we will overview the recent result (to appear in STOC '16) that there are no additive spanner constructions with +n^{o(1)} error and n^{4/3  eps} edges (which is proved by reduction to distance preserver lower bounds). We will also survey some of the major results and open questions in distance preservers research, and demonstrate further relationships between these problems and some of the major remaining questions in additive spanners research. 17:00  17:30 Wolfgang Mulzer Efficient Spanner Construction for Directed Transmission Graphs [+] Let P be a set of n points in the plane, each with an associated radius r(p) > 0. The transmission graph G for P has vertex set P and a directed edge from p to q if and only if q lies in the ball with radius r(p) around p. Let t > 1. A tspanner H for G is a sparse subgraph such that for any two vertices p and q connected by a path of length l in G, there is a path of length at most tl from p to q in H. Given G implicitly as points with radii, we show how to compute a tspanner for G in time O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius in P. Furthermore, we extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a bonus, it turns out that the properties of our spanner also allow us to compute a BFS tree for G and any given start vertex s in the same time. Based on joint work with Haim Kaplan, Liam Roditty and Paul Seiferth. 17:30  18:00 Michael Dinitz Approximating Spanners [+] This talk will survey recent work on approximating spanners, in which we consider the computational problem of finding the "best" spanner given an input graph. This is in contrast to the study of "universal" bounds, i.e. bounds on spanner size/quality which hold universally for all (or a defined subclass) of graphs. We will see that in some cases we can give approximation bounds even when universal bounds do not exist, and when universal bounds do exist we can sometimes optimize to find even better spanners (if they exist). 
15:30  16:00 Eric Colin de Verdiere Multicuts in Planar and BoundedGenus Graphs with Bounded Number of Terminals [+] Given an undirected, edgeweighted graph G together with pairs of vertices, called pairs of terminals, the minimum multicut problem asks for a minimumweight set of edges such that, after deleting these edges, the two terminals of each pair belong to different connected components of the graph. Relying on topological techniques, we provide a polynomialtime algorithm for this problem in the case where G$is embedded on a fixed surface of genus g (e.g., when G is planar) and has a fixed number t of terminals. The running time is a polynomial of degree O(\sqrt{g^{2}+gt}} in the input size. In the planar case, our result corrects an error in an extended abstract by Bentz [Int. Workshop on Parameterized and Exact Computation, 109119, 2012]. The minimum multicut problem is also a generalization of the multiway cut problem, a.k.a. multiterminal cut problem; even for this special case, no dedicated algorithm was known for graphs embedded on surfaces. 16:05  16:35 Robert Krauthgamer Cutting Corners Cheaply, or How to Remove Steiner Points [+] I will show how the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which answers a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, for every edgeweighted graph G=(V,E,w) and a subset of terminals $T\subset V$, there is a graph only on the terminals, denoted $G'=(T,E',w')$, which is a minor of $G$ and the shortestpath distance between any two terminals is approximately equal in $G'$ and in $G$, namely within factor $O(\log^5 T)$. Our existence proof is constructive and gives a randomized polynomialtime algorithm. Joint work with Lior Kamma and Huy L. Nguyen 16:40  17:20 Philip Klein Approximation Schemes for Planar Graphs: A Survey of Methods [+] In addressing an NPhard problem in combinatorial optimization, one way to cope is to use an {\em approximation scheme}, an algorithm that, for any given \epsilon>0, produces a solution whose value is within a 1+\epsilon factor of optimal. For many problems on graphs, obtaining such accurate approximations is NPhard if the input is allowed to be any graph but is tractable if the input graph is required to be planar. Research on polynomialtime approximation schemes for optimization problems in planar graphs goes back to the pioneering work of Lipton and Tarjan (1977) and Baker (1983). Since then, however, the scope of problems amenable to approximation has broadened considerably. In this talk I will outline some of the approaches used, especially those that have led to recent results. 17:25  17:55 Chandra Chekuri Constant Congestion Routing of Symmetric Demands [+] Routing problems in directed graphs such as the maximum edge disjoint paths problem appear quite intractable. There is a polynomialfactor lower bound on the approximation ratio that can be achieved even if constant congestion is allowed. We consider the case of symmetric demands where a demand pair st requires a directed path from s to t and a directed path from t to s. This variation appears tractable. We discuss two recent positive results on this problem including routing in planar graphs. One important motivation to consider symmetric demands is the connection to directed treewidth and directed gridminors. The goal of the talk is to highlight the connection and mention the open problems. Based on joint work with Alina Ene and Marcin Pilipczuk. 
15:30  16:00 Jean Cardinal Geometric Representations of Graphs and the Existential Theory of the Reals [+] Deciding the validity of sentences in the existential theory of the reals (ETR) amounts to checking the existence of a real solution to systems of polynomial equalities and inequalities. In the late eighties, Mnëv stated a theorem that led to a proof that the stretchability problem for pseudoline arrangements was ETRcomplete. Since then, many more natural problems in computational geometry have been proven ETRcomplete, in particular in the field of graph drawing and geometric graphs. We will describe the foundation of those proofs, some wellknown results in this vein, and recent additions to the list. 16:00  16:30 Radoslav Fulek Strong HananiTutte for Radial Drawings [+] A drawing of a graph G is radial if the vertices of G are placed on concentric circles C_1,..., C_k with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossingfree radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the variant of the HananiTutte theorem for radial planarity. Our result implies a very simple polynomialtime algorithm for radial planarity based on solving a system of linear equations over Z_2. This is a joint work with M. Pelsmajer and M. Schaefer. 16:30  17:00 Csaba Tóth Flexible Contact Representations [+] Contact graphs are easy to handle when such a representation is unique or severely constrained. We summarize recent results on highly flexible representation. Two models are considered: bodyandhinge frameworks and contact graphs of convex bodies in the plane. We show that it is strongly NPhard to decide (1) whether a given bodyandhinge framework is realizable in when the bodies are convex polygons and their contact graph is a tree; (2) whether a given tree is the contact graph of interiordisjoint unit disks in the plane. The main challenge in both cases is that any realization has a high degree of freedom, which raises several open problems about the realization space of contact representations. 17:00  17:30 Bartosz Walczak Coloring Geometric Intersection Graphs [+] 17:30  18:00 Steven Chaplick Open Problem Session 
