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 