Back to Program overview
9:10  SOCG  Session A (AUD 4) Session Chair: John Hershberger 


On the Beer Index of Convexity and Its Variants [DOI]
[+] Martin Balko, Vít Jelínek, Pavel Valtr and Bartosz Walczak. Let S be a subset of R^{d} with finite positive Lebesgue measure. The Beer index of convexity b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio c(S) of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate a relationship between these two natural measures of convexity of S.
We show that every subset S of the plane with simply connected components satisfies b(S) <= alpha c(S) for an absolute constant alpha, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. asserting that this estimate holds for simple polygons.
We also consider higherorder generalizations of b(S). For 1 <= k <= d, the kindex of convexity b_{k}(S) of a subset S of R^{d} is the probability that the convex hull of a (k+1)tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d >= 2 there is a constant beta(d) > 0 such that every subset S of R^{d} satisfies b_{d}(S) <= beta c(S), provided b_{d}(S) exists. We provide an almost matching lower bound by showing that there is a constant gamma(d) > 0 such that for every epsilon from (0,1] there is a subset S of R^{d} of Lebesgue measure one satisfying c(S) <= epsilon and b_{d}(S) >= (gamma epsilon)/log_{2}(1/epsilon) >= (gamma c(S))/log_{2}(1/c(S)).
Tight Bounds for ConflictFree Chromatic Guarding of Orthogonal Art Galleries [DOI]
[+] Frank Hoffmann, Klaus Kriegel, Subhash Suri, Kevin Verbeek and Max Willert. The chromatic art gallery problem asks for the minimum number of "colors" t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility  two points p and q are mutually visible if the smallest axisaligned rectangle containing them lies within the polygon. Our main result establishes that for a conflictfree guarding of an orthogonal ngon, in which at least one of the colors seen by every point is unique, the number of colors is Θ(loglog n). By contrast, the best upper bound for orthogonal polygons under standard (nonorthogonal) visibility is O(log n) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is Θ(log n). Finally, our techniques also help us establish the first nontrivial lower bound of Ω(loglog n / logloglog n) for conflictfree guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.
LowQuality Dimension Reduction and HighDimensional Approximate Nearest Neighbor [DOI]
[+] Evangelos Anagnostopoulos, Ioannis Z. Emiris and Ioannis Psarros. The approximate nearest neighbor problem (epsilonANN) in Euclidean settings is a fundamental question, which has been addressed by two main approaches: Datadependent space partitioning techniques perform well when the dimension is relatively low, but are affected by the curse of dimensionality. On the other hand, locality sensitive hashing has polynomial dependence in the dimension, sublinear query time with an exponent inversely proportional to (1+epsilon)^{2}, and subquadratic space requirement.
We generalize the JohnsonLindenstrauss Lemma to define "lowquality" mappings to a Euclidean space of significantly lower dimension, such that they satisfy a requirement weaker than approximately preserving all distances or even preserving the nearest neighbor. This mapping guarantees, with high probability, that an approximate nearest neighbor lies among the k approximate nearest neighbors in the projected space. These can be efficiently retrieved while using only linear storage by a data structure, such as BBDtrees. Our overall algorithm, given n points in dimension d, achieves space usage in O(dn), preprocessing time in O(dn log n), and query time in O(d n^{rho} log n), where rho is proportional to 1  1/loglog n, for fixed epsilon in (0, 1). The dimension reduction is larger if one assumes that point sets possess some structure, namely bounded expansion rate. We implement our method and present experimental results in up to 500 dimensions and 10^{6} points, which show that the practical performance is better than predicted by the theoretical analysis. In addition, we compare our approach with E2LSH.
Restricted Isometry Property for General pNorms [DOI]
[+]
Zeyuan AllenZhu, Rati Gelashvili and Ilya Razenshteyn. The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an m x n matrix satisfies RIP of order k for the L_{p} norm, if Ax_{p} is approximately x_{p} for every x with at most k nonzero coordinates.
For every 1 <= p < infty we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this work, only the cases p = 1, 1 + 1/log(k), and 2 were studied. Interestingly, our results show that the case p=2 is a "singularity" point: the optimal number of rows m is Θ(k^{p}) for all p in [1, infty){2}, as opposed to Θ(k) for k=2.
We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss implications of our results for the Stable Sparse Recovery problem.


SOCG  Session B (AUD 5) Session Chair: Donald Sheehy 

Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs [DOI]
[+] Ulrich Bauer, Elizabeth Munch and Yusu Wang. The Reeb graph is a construction that studies a topological space through the lens of a real valued function. It has been commonly used in applications, however its use on real data means that it is desirable and increasingly necessary to have methods for comparison of Reeb graphs. Recently, several metrics on the set of Reeb graphs have been proposed. In this paper, we focus on two: the functional distortion distance and the interleaving distance. The former is based on the GromovHausdorff distance, while the latter utilizes the equivalence between Reeb graphs and a particular class of cosheaves. However, both are defined by constructing a nearisomorphism between the two graphs of study. In this paper, we show that the two metrics are strongly equivalent on the space of Reeb graphs. Our result also implies the bottleneck stability for persistence diagrams in terms of the Reeb graph interleaving distance.
On Generalized Heawood Inequalities for Manifolds: A Van KampenFlorestype Nonembeddability Result [DOI]
[+] Xavier Goaoc, Isaac Mabillard, Pavel Patak, Zuzana Patakova, Martin Tancer and Uli Wagner. The fact that the complete graph K_{5} does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_{n} embeds in a closed surface M if and only if (n3)(n4) is at most 6b_{1}(M), where b_{1}(M) is the first Z_{2}Betti number of M. On the other hand, Van Kampen and Flores proved that the kskeleton of the ndimensional simplex (the higherdimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2.
Two decades ago, Kuhnel conjectured that the kskeleton of the nsimplex embeds in a compact, (k1)connected 2kmanifold with kth Z_{2}Betti number b_{k} only if the following generalized Heawood inequality holds: binom{nk1}{k+1} is at most binom{2k+1}{k+1} b_{k}. This is a common generalization of the case of graphs on surfaces as well as the Van KampenFlores theorem.
In the spirit of Kuhnel's conjecture, we prove that if the kskeleton of the nsimplex embeds in a 2kmanifold with kth Z_{2}Betti number b_{k}, then n is at most 2b_{k} binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k1)connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.
Comparing Graphs via Persistence Distortion [DOI]
[+] Tamal Dey, Dayu Shi and Yusu Wang. Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graphlike, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the nonlinear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistencedistortion distance, which draws upon a topological idea. This topological perspective along with the metric space viewpoint provide a new angle to the graph matching problem. Our persistencedistortion distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a continuous distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our persistencedistortion distance robust against, for example, different discretizations of the same underlying graph.
Despite considering the input graphs as continuous spaces, that is, taking all points into account, we show that we can compute the persistencedistortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster.
Bounding Helly Numbers via Betti Numbers [DOI]
[+]
Xavier Goaoc, Pavel Patak, Zuzana Patakova, Martin Tancer and Uli Wagner. We show that very weak topological assumptions are enough to ensure the existence of a Hellytype theorem. More precisely, we show that for any nonnegative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^{d} such that the ith reduced Betti number (with Z_{2} coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every nonnegative integer i less or equal to (d1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number.
Our proofs combine homological nonembeddability results with a Ramseybased approach to build, given an arbitrary simplicial complex K, some wellbehaved chain map from C_{*}(K) to C_{*}(R^{d}). Both techniques are of independent interest.


10:30  Coffee Break  
11:00  SOCG  Session A (AUD 4) Session Chair: Csaba Tóth 

Polynomials Vanishing on Cartesian Products: The ElekesSzabó Theorem Revisited [DOI]
[+] Orit E. Raz, Micha Sharir and Frank de Zeeuw. Let F in Complex[x,y,z] be a constantdegree polynomial, and let A,B,C be sets of complex numbers with A=B=C=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special grouprelated form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}).
This result provides a unified tool for improving bounds in various Erdostype problems in combinatorial geometry, and we discuss several applications of this kind.
Bisector Energy and Few Distinct Distances [DOI]
[+] Ben Lund, Adam Sheffer and Frank de Zeeuw. We introduce the bisector energy of an npoint set P in the real plane, defined as the number of quadruples (a,b,c,d) from P such that a and b determine the same perpendicular bisector as c and d. If no line or circle contains M(n) points of P, then we prove that the bisector energy is O(M(n)^{2/5}n^{12/5} + M(n)n^{2}). We also prove the lower bound M(n)n^{2}, which matches our upper bound when M(n) is large. We use our upper bound on the bisector energy to obtain two rather different results:
(i) If P determines O(n / sqrt(log n)) distinct distances, then for any 0 < a < 1/4, either there exists a line or circle that contains n^{a} points of P, or there exist n^{8/5  12a/5} distinct lines that contain sqrt(log n) points of P. This result provides new information on a conjecture of Erdös regarding the structure of point sets with few distinct distances.
(ii) If no line or circle contains M(n) points of P, then the number of distinct perpendicular bisectors determined by P is min{M(n)^{2/5}n^{8/5}, M(n)^{1}n^{2}}). This appears to be the first higherdimensional example in a framework for studying the expansion properties of polynomials and rational functions over the real numbers, initiated by Elekes and Ronyai.
Incidences between Points and Lines in Three Dimensions [DOI]
[+] Micha Sharir and Noam Solomon. We give a fairly elementary and simple proof that shows that the number of incidences between m points and n lines in R^{3}, so that no plane contains more than s lines, is O(m^{1/2}n^{3/4} + m^{2/3}n^{1/3}s^{1/3} + m + n) (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between m and n).
This bound, originally obtained by Guth and Katz as a major step in their solution of Erdos's distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth. The present paper presents a different and simpler derivation, with better bounds than those in Guth, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.
The Number of UnitArea Triangles in the Plane: Theme and Variations [DOI]
[+] Orit E. Raz and Micha Sharir. We show that the number of unitarea triangles determined by a set S of n points in the plane is O(n^{20/9}), improving the earlier bound O(n^{9/4}) of Apfelbaum and Sharir. We also consider two special cases of this problem: (i) We show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unitarea triangles that S spans can be Ω(n^{2}), for any triple of lines (it is always O(n^{2}) in this case). (ii) We show that if S is a convex grid of the form A x B, where A, B are convex sets of n^{1/2} real numbers each (i.e., the sequences of differences of consecutive elements of A and of B are both strictly increasing), then S determines O(n^{31/14}) unitarea triangles.
On the Number of Rich Lines in Truly High Dimensional Sets [DOI]
[+] Zeev Dvir and Sivakanth Gopi. We prove a new upper bound on the number of rrich lines (lines with at least r points) in a 'truly' ddimensional configuration of points v_{1},...,v_{n} over the complex numbers. More formally, we show that, if the number of rrich lines is significantly larger than n^{2}/r^{d} then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor r^{d} can be replaced with a tight r^{d+1}. If true, this would generalize the classic SzemerediTrotter theorem which gives a bound of n^{2}/r^{3} on the number of rrich lines in a planar configuration. This conjecture was shown to hold in R^{3} in the seminal work of Guth and Katz and was also recently proved over R^{4} (under some additional restrictions) by Solomon and Sharir. For the special case of arithmetic progressions (r collinear points that are evenly distanced) we give a bound that is tight up to lower order terms, showing that a ddimensional grid achieves the largest number of rterm progressions.
The main ingredient in the proof is a new method to find a low degree polynomial that vanishes on many of the rich lines. Unlike previous applications of the polynomial method, we do not find this polynomial by interpolation. The starting observation is that the degree r2 Veronese embedding takes rcollinear points to r linearly dependent images. Hence, each collinear rtuple of points, gives us a dependent rtuple of images. We then use the designmatrix method of Barak et al. to convert these 'local' linear dependencies into a global one, showing that all the images lie in a hyperplane. This then translates into a low degree polynomial vanishing on the original set.
Realization Spaces of Arrangements of Convex Bodies [DOI]
[+]
Michael Gene Dobbins, Andreas Holmsen and Alfredo Hubard. We introduce combinatorial types of arrangements of convex bodies, extending order types of point sets to arrangements of convex bodies, and study their realization spaces. Our main results witness a tradeoff between the combinatorial complexity of the bodies and the topological complexity of their realization space. On one hand, we show that every combinatorial type can be realized by an arrangement of convex bodies and (under mild assumptions) its realization space is contractible. On the other hand, we prove a universality theorem that says that the restriction of the realization space to arrangements of convex polygons with a bounded number of vertices can have the homotopy type of any primary semialgebraic set.


SOCG  Session B (AUD 5) Session Chair: Antoine Vigneron 

Computing Teichmüller Maps between Polygons [DOI]
[+] Mayank Goswami, Xianfeng Gu, Vamsi Pritham Pingali and Gaurish Telang. By the Riemann mapping theorem, one can bijectively map the interior of an ngon P to that of another ngon Q conformally (i.e., in an angle preserving manner). However, when this map is extended to the boundary it need not necessarily map the vertices of P to those of Q. For many applications it is important to find the "best" vertexpreserving mapping between two polygons, i.e., one that minimizes the maximum angle distortion (the socalled dilatation). Such maps exist, are unique, and are known as extremal quasiconformal maps or Teichmüller maps.
There are many efficient ways to approximate conformal maps, and the recent breakthrough result by Bishop computes a (1+epsilon)approximation of the Riemann map in linear time. However, only heuristics have been studied in the case of Teichmüller maps.
We present two results in this paper. One studies the problem in the continuous setting and another in the discrete setting.
In the continuous setting, we solve the problem of finding a finite time procedure for approximating Teichmüller maps. Our construction is via an iterative procedure that is proven to converge in O(poly(1/epsilon)) iterations to a (1+epsilon)approximation of the Teichmuller map. Our method uses a reduction of the polygon mapping problem to the marked sphere problem, thus solving a more general problem.
In the discrete setting, we reduce the problem of finding an approximation algorithm for computing Teichmüller maps to two basic subroutines, namely, computing discrete 1) compositions and 2) inverses of discretely represented quasiconformal maps. Assuming finitetime solvers for these subroutines we provide a (1+epsilon)approximation algorithm.
Online Coloring between Two Lines [DOI]
[+] Stefan Felsner, Piotr Micek and Torsten Ueckerdt. We study online colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axisaligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an online algorithm coloring graphs given by convex sets between two lines that uses O(w^{3}) colors on graphs with maximum clique size w.
In contrast intersection graphs of segments attached to a single line may force any online coloring algorithm to use an arbitrary number of colors even when w=2.
The leftof relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class C of posets obtained from convex sets between two lines with some other classes of posets: all 2dimensional posets and all posets of height 2 are in C but there is a 3dimensional poset of height 3 that does not belong to C.
We also show that the online coloring problem for curves between two lines is as hard as the online chain partition problem for arbitrary posets.
Building Efficient and Compact Data Structures for Simplicial Complexes [DOI]
[+] JeanDaniel Boissonnat, Karthik C. S. and Sébastien Tavenas. The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called Maximal Simplex Tree (MxST) and Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.
Shortest Path to a Segment and Quickest Visibility Queries [DOI]
[+] Esther Arkin, Alon Efrat, Christian Knauer, Joseph Mitchell, Valentin Polishchuk, Gunter Rote, Lena Schlipf and Topi Talvitie. We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the wellknown shortestpathtoapoint query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortestpathtoapoint queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.
Trajectory Grouping Structure under Geodesic Distance [DOI]
[+] Irina Kostitsyna, Marc Van Kreveld, Maarten Löffler, Bettina Speckmann and Frank Staals. In recent years trajectory data has become one of the main types of geographic data, and hence algorithmic tools to handle large quantities of trajectories are essential. A single trajectory is typically represented as a sequence of timestamped points in the plane. In a collection of trajectories one wants to detect maximal groups of moving entities and their behaviour (merges and splits) over time. This information can be summarized in the trajectory grouping structure.
Significantly extending the work of Buchin et al. [WADS 2013] into a realistic setting, we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly epsilon, where epsilon is the threshold distance that determines whether two entities are close enough to be in one group. In case the n entities move in a simple polygon along trajectories with tau vertices each we give an O(tau n^{2}) upper bound, which is tight in the worst case. In case of wellspaced obstacles we give an O(tau(n^{2} + m lambda_{4}(n))) upper bound, where m is the total complexity of the obstacles, and lambda_{s}(n) denotes the maximum length of a DavenportSchinzel sequence of n symbols of order s. In case of general obstacles we give an O(tau min(n^{2} + m^{3} lambda_{4}(n), n^{2}m^{2})) upper bound. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.
From Proximity to Utility: A Voronoi Partition of Pareto Optima [DOI]
[+]
HsienChih Chang, Sariel HarPeled and Benjamin Raichel. We present an extension of Voronoi diagrams where not only the distance to the site is taken into account when considering which site the client is going to use, but additional attributes (i.e., prices or weights) are also considered. A cell in this diagram is then the loci of all clients that consider the same set of sites to be relevant. In particular, the precise site a client might use from this candidate set depends on parameters that might change between usages, and the candidate set lists all of the relevant sites. The resulting diagram is significantly more expressive than Voronoi diagrams, but naturally has the drawback that its complexity, even in the plane, might be quite high. Nevertheless, we show that if the attributes of the sites are drawn from the same distribution (note that the locations are fixed), then the expected complexity of the candidate diagram is near linear. To this end, we derive several new technical results, which are of independent interest.


13:00  Catered Lunch  
14:00  Business meeting Session A (Blauwe Zaal) 

15:30  Coffee Break  
16:00  
16:15  Bus Transfer  
17:15  Boat Tours and Guided Tours  
19:15  Reception and Dinner at Orangerie  
22:30  Bus Transfer 