Back to Program overview
9:30  SOCG  Session A (AUD 4) Session Chair: Antoine Vigneron 


Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings [DOI]
[+] Daniel Dadush. We give a 2^{O(n)}(1+1/eps)^{n} time and poly(n)space deterministic algorithm for computing a (1+eps)^{n} approximation to the volume of a general convex body K, which comes close to matching the (1+c/eps)^{n/2}
lower bound for volume estimation in the oracle model by Barany and
Furedi (STOC 1986, Proc. Amer. Math. Soc. 1988). This improves on the
previous results of Dadush and Vempala (Proc. Nat'l Acad. Sci. 2013),
which gave the above result only for symmetric bodies and achieved a
dependence of 2^{O(n)}(1+log^{5/2}(1/eps)/eps^{3})^{n}.
For our methods, we reduce the problem of volume estimation in K to counting lattice points in K subseteq R^{n}
(via enumeration) for a specially constructed lattice L: a socalled
thin covering of space with respect to K (more precisely, for which L + K
= R^{n} and vol_{n}(K)/det(L) = 2^{O(n)}). The trade off between time and approximation ratio is achieved by scaling down the lattice.
As our main technical contribution, we give the first deterministic 2^{O(n)}time
and poly(n)space construction of thin covering lattices for general
convex bodies. This improves on a recent construction of Alon et al
(STOC 2013) which requires exponential space and only works for
symmetric bodies. For our construction, we combine the use of the
Mellipsoid from convex geometry (Milman, C.R. Math. Acad. Sci. Paris
1986) together with lattice sparsification and densification techniques
(Dadush and Kun, SODA 2013; Rogers, J. London Math. Soc. 1950).
Optimal Deterministic Algorithms for 2d and 3d Shallow Cuttings [DOI]
[+] Timothy M. Chan and Konstantinos Tsakalidis. We present optimal
deterministic algorithms for constructing shallow cuttings in an
arrangement of lines in two dimensions or planes in three dimensions.
Our results improve the deterministic polynomialtime algorithm of
Matousek (1992) and the optimal but randomized algorithm of Ramos
(1999). This leads to efficient derandomization of previous algorithms
for numerous wellstudied problems in computational geometry, including
halfspace range reporting in 2d and 3d, k nearest neighbors search in
2d, (<= k)levels in 3d, orderk Voronoi diagrams in 2d, linear
programming with k violations in 2d, dynamic convex hulls in 3d,
dynamic nearest neighbor search in 2d, convex layers (onion peeling) in
3d, epsilonnets for halfspace ranges in 3d, and more. As a side
product we also describe an optimal deterministic algorithm for
constructing standard (nonshallow) cuttings in two dimensions, which is
arguably simpler than the known optimal algorithms by Matousek (1991)
and Chazelle (1993).
A Simpler LinearTime Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions [DOI]
[+]
Timothy M. Chan. Chazelle [FOCS'89]
gave a lineartime algorithm to compute the intersection of two convex
polyhedra in three dimensions. We present a simpler algorithm to do the
same.


SOCG  Session B (AUD 5) Session Chair: Monique Teillaud 

Approximability of the Discrete Fréchet Distance [DOI]
[+] Karl Bringmann and Wolfgang Mulzer. The Fréchet distance
is a popular and widespread distance measure for point sequences and for
curves. About two years ago, Agarwal et al [SIAM J. Comput. 2014]
presented a new (mildly) subquadratic algorithm for the discrete version
of the problem. This spawned a flurry of activity that has led to
several new algorithms and lower bounds.
In this paper, we study the approximability of the discrete Fréchet
distance. Building on a recent result by Bringmann [FOCS 2014], we
present a new conditional lower bound that strongly subquadratic
algorithms for the discrete Fréchet distance are unlikely to exist, even
in the onedimensional case and even if the solution may be
approximated up to a factor of 1.399.
This raises the question of how well we can approximate the Fréchet
distance (of two given ddimensional point sequences of length n) in
strongly subquadratic time. Previously, no general results were known.
We present the first such algorithm by analysing the approximation ratio
of a simple, lineartime greedy algorithm to be 2^{Θ(n)}. Moreover, we design an alphaapproximation algorithm that runs in time O(n log n + n^{2} / alpha), for any alpha in [1, n]. Hence, an n^{eps}approximation of the Fréchet distance can be computed in strongly subquadratic time, for any epsilon > 0.
The Hardness of Approximation of Euclidean kMeans [DOI]
[+] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy and Ali Kemal Sinop. The Euclidean kmeans
problem is a classical problem that has been extensively studied in the
theoretical computer science, machine learning and the computational
geometry communities. In this problem, we are given a set of n points in
Euclidean space R^{d}, and the goal is to choose k center points in R^{d}
so that the sum of squared distances of each point to its nearest
center is minimized. The best approximation algorithms for this problem
include a polynomial time constant factor approximation for general k
and a (1+c)approximation which runs in time poly(n) exp(k/c). At the
other extreme, the only known computational complexity result for this
problem is NPhardness [Aloise et al.'09]. The main difficulty in
obtaining hardness results stems from the Euclidean nature of the
problem, and the fact that any point in R^{d} can be a potential
center. This gap in understanding left open the intriguing possibility
that the problem might admit a PTAS for all k, d.
In this paper we provide the first hardness of approximation for the
Euclidean kmeans problem. Concretely, we show that there exists a
constant c > 0 such that it is NPhard to approximate the kmeans
objective to within a factor of (1+c). We show this via an efficient
reduction from the vertex cover problem on trianglefree graphs: given a
trianglefree graph, the goal is to choose the fewest number of
vertices which are incident on all the edges. Additionally, we give a
proof that the current best hardness results for vertex cover can be
carried over to trianglefree graphs. To show this we transform G, a
known hard vertex cover instance, by taking a graph product with a
suitably chosen graph H, and showing that the size of the (normalized)
maximum independent set is almost exactly preserved in the product graph
using a spectral analysis, which might be of independent interest.
A Fire Fighter's Problem [DOI]
[+]
Rolf Klein, Elmar Langetepe and Christos Levcopoulos. Suppose that a
circular fire spreads in the plane at unit speed. A fire fighter can
build a barrier at speed v > 1. How large must v be to ensure that
the fire can be contained, and how should the fire fighter proceed? We
provide two results. First, we analyze the natural strategy where the
fighter keeps building a barrier along the frontier of the expanding
fire. We prove that this approach contains the fire if v > v_{c}
= 2.6144... holds. Second, we show that any "spiralling" strategy must
have speed v > 1.618, the golden ratio, in order to succeed.


10:30  Coffee Break  
11:00  SOCG  Session A (AUD 4) Session Chair: Stefan Langerman 

Approximate Geometric MST Range Queries [DOI]
[+] Sunil Arya, David Mount and Eunhui Park. Range searching is a
widelyused method in computational geometry for efficiently accessing
local regions of a large data set. Typically, range searching involves
either counting or reporting the points lying within a given query
region, but it is often desirable to compute statistics that better
describe the structure of the point set lying within the region, not
just the count.
In this paper we consider the geometric minimum spanning tree (MST)
problem in the context of range searching where approximation is
allowed. We are given a set P of n points in R^{d}. The
objective is to preprocess P so that given an admissible query region Q,
it is possible to efficiently approximate the weight of the minimum
spanning tree of the subset of P lying within Q. There are two natural
sources of approximation error, first by treating Q as a fuzzy object
and second by approximating the MST weight itself. To model this, we
assume that we are given two positive real approximation parameters eps_{q} and eps_{w}. Following the typical practice in approximate range searching, the range is expressed as two shapes Q^{} and Q^{+}, where Q^{} is contained in Q which is contained in Q^{+}, and their boundaries are separated by a distance of at least eps_{q} diam(Q). Points within Q^{} must be included and points external to Q^{+} cannot be included. A weight W is a valid answer to the query if there exist subsets P' and P'' of P, such that Q^{} is contained in P' which is contained in P'' which is contained in Q^{+} and wt(MST(P')) <= W <= (1+eps_{w})
wt(MST(P'')).
In this paper, we present an efficient data structure for answering such
queries. Our approach uses simple data structures based on quadtrees,
and it can be applied whenever Q^{} and Q^{+} are compact sets of constant combinatorial complexity. It uses space O(n), and it answers queries in time O(log n + 1/(eps_{q} eps_{w})^{d + O(1)}).
The O(1) term is a small constant independent of dimension, and the
hidden constant factor in the overall running time depends on d, but not
on eps_{q} or eps_{w}. Preprocessing requires knowledge of eps_{w}, but not eps_{q}.
Maintaining Contour Trees of Dynamic Terrains [DOI]
[+] Pankaj K. Agarwal, Thomas Mølhave, Morten Revsbæk, Issam Safa, Yusu Wang and Jungwoo Yang. We study the problem
of maintaining the contour tree T of a terrain Sigma, represented as a
triangulated xymonotone surface, as the heights of its vertices vary
continuously with time. We characterize the combinatorial changes in T
and how they relate to topological changes in Sigma. We present a
kinetic data structure (KDS) for maintaining T efficiently. It maintains
certificates that fail, i.e., an event occurs, only when the heights of
two adjacent vertices become equal or two saddle vertices appear on the
same contour. Assuming that the heights of two vertices of Sigma become
equal only O(1) times and these instances can be computed in O(1) time,
the KDS processes O(kappa + n) events, where n is the number of
vertices in Sigma and kappa is the number of events at which the
combinatorial structure of T changes, and processes each event in O(log
n) time. The KDS can be extended to maintain an augmented contour tree
and a join/split tree.
Hyperorthogonal WellFolded Hilbert Curves [DOI]
[+]
Arie Bos and Herman Haverkort. Rtrees can be used to
store and query sets of point data in two or more dimensions. An easy
way to construct and maintain Rtrees for twodimensional points, due to
Kamel and Faloutsos, is to keep the points in the order in which they
appear along the Hilbert curve. The Rtree will then store bounding
boxes of points along contiguous sections of the curve, and the
efficiency of the Rtree depends on the size of the bounding boxes 
smaller is better. Since there are many different ways to generalize the
Hilbert curve to higher dimensions, this raises the question which
generalization results in the smallest bounding boxes. Familiar methods,
such as the one by Butz, can result in curve sections whose bounding
boxes are a factor Ω(2^{d/2}) larger than the volume traversed
by that section of the curve. Most of the volume bounded by such
bounding boxes would not contain any data points. In this paper we
present a new way of generalizing Hilbert's curve to higher dimensions,
which results in much tighter bounding boxes: they have at most 4 times
the volume of the part of the curve covered, independent of the number
of dimensions. Moreover, we prove that a factor 4 is asymptotically
optimal.


SOCG  Session B (AUD 5) Session Chair: Csaba Tóth 

Topological Analysis of Scalar Fields with Outliers [DOI]
[+] Mickaël Buchet, Frederic Chazal, Tamal Dey, Fengtao Fan, Steve Oudot and Yusu Wang. Given a realvalued function f defined over a manifold M embedded in R^{d},
we are interested in recovering structural information about f from the
sole information of its values on a finite sample P. Existing methods
provide approximation to the persistence diagram of f when geometric
noise and functional noise are bounded. However, they fail in the
presence of aberrant values, also called outliers, both in theory and
practice.
We propose a new algorithm that deals with outliers. We handle aberrant
functional values with a method inspired from the knearest neighbors
regression and the local median filtering, while the geometric outliers
are handled using the distance to a measure. Combined with topological
results on nested filtrations, our algorithm performs robust topological
analysis of scalar fields in a wider range of noise models than handled
by current methods. We provide theoretical guarantees and experimental
results on the quality of our approximation of the sampled scalar field.
On Computability and Triviality of Well Groups [DOI]
[+] Peter Franek and Marek Krcál. The concept of well
group in a special but important case captures homological properties of
the zero set of a continuous map f from K to R^{n} on a compact
space K that are invariant with respect to perturbations of f. The
perturbations are arbitrary continuous maps within L_{i}nfty
distance r from f for a given r > 0. The main drawback of the
approach is that the computability of well groups was shown only when
dim K = n or n = 1.
Our contribution to the theory of well groups is twofold: on the one
hand we improve on the computability issue, but on the other hand we
present a range of examples where the well groups are incomplete
invariants, that is, fail to capture certain important robust properties
of the zero set.
For the first part, we identify a computable subgroup of the well group
that is obtained by cap product with the pullback of the orientation of R^{n}
by f. In other words, well groups can be algorithmically approximated
from below. When f is smooth and dim K < 2n2, our approximation of
the (dim Kn)th well group is exact.
For the second part, we find examples of maps f, f' from K to R^{n}
with all well groups isomorphic but whose perturbations have different
zero sets. We discuss on a possible replacement of the well groups of
vector valued maps by an invariant of a better descriptive power and
computability status.
Geometric Inference on Kernel Density Estimates [DOI]
[+]
Jeff Phillips, Bei Wang and Yan Zheng. We show that
geometric inference of a point cloud can be calculated by examining its
kernel density estimate with a Gaussian kernel. This allows one to
consider kernel density estimates, which are robust to spatial noise,
subsampling, and approximate computation in comparison to raw point
sets. This is achieved by examining the sublevel sets of the kernel
distance, which isomorphically map to superlevel sets of the kernel
density estimate. We prove new properties about the kernel distance,
demonstrating stability results and allowing it to inherit
reconstruction results from recent advances in distancebased
topological reconstruction. Moreover, we provide an algorithm to
estimate its topology using weighted VietorisRips complexes.


12:00  Invited Speaker Session A (Blauwe Zaal) Session Chair: Lars Arge 

Modeling RealWorld Data Sets [DOI]
[+]
Susanne Albers. Traditionally, the
performance of algorithms is evaluated using worstcase analysis. For a
number of problems, this type of analysis gives overly pessimistic
results: Worstcase inputs are rather artificial and do not occur in
practical applications. In this lecture we review some alternative
analysis approaches leading to more realistic and robust performance
evaluations.
Specifically, we focus on the approach of modeling realworld data sets.
We report on two studies performed by the author for the problems of
selforganizing search and paging. In these settings real data sets
exhibit locality of reference. We devise mathematical models capturing
locality. Furthermore, we present combined theoretical and experimental
analyses in which the theoretically proven and experimentally observed
performance guarantees match up to very small relative errors.


13:00  Catered Lunch  
14:00  Workshop  Stochastic Geometry Session A (Blauwe Zaal) 

Welcome
Introduction to several models from stochastic geometry
[+] Pierre Calka. Stochastic geometry can be described as the study of Euclidean objects with a random behaviour. First problems in geometric probability were presented as recreational mathematics but the domain has substantially grown for 50 years, in particular because of its many applications including experimental science and especially analysis of geometric algorithms. The talk will be centered on the description of several classical models from stochastic geometry: random tessellations and in particular the PoissonVoronoi and PoissonDelaunay tessellations, random geometric graphs, random polytopes constructed as convex hulls of a random point set, etc. We will survey the basic properties of each of them and focus in particular on some of their asymptotic properties which can provide valuable information in the context of computational geometry. Introduction to the random generation of discrete structures
[+]
Philippe Duchon. In many situations, one is able to define "natural" probability distributions on some set of discrete structures that one wants to study and/or simulate. This of course includes uniform distributions on finite sets, but in many cases the distribution is defined through some invariance property. Classical examples with a geometric flavor include tilings. The talk will focus on techniques used to algorithmically simulate, exactly on approximately, such a probability distribution  that is, sample discrete structures according to some previously defined probability distribution on a finite (but large) or infinite set. 

Workshop  Computational Topology Session B (AUD 2) 

Introduction to Categories, Part I: Key Concepts [+] Vin de Silva.
What are the key ideas that make category theory interesting and
worthwhile? I will try to explain some of the following ideas:
categories, functors, natural transformations, comma categories,
universal constructions, equivalences of categories, adjunctions,
representability.
The Interleaving Distance [+]
Elizabeth Munch.
The interleaving distance arose as a metric on persistence modules.
However, through category theory, this metric can be extended to a large
class of functors which represent many useful constructions in applied
topology, including Reeb graphs, Reeb spaces, and multidimensional
persistence modules. In this talk, we will discuss the current work on
the interleaving distance through examples.


Workshop  Geometric Intersection Graphs Session C (AUD 7) 

Interval Graphs in Data Streaming
[+] Sergio Cabello. In this talk we will advocate that basic graph problems should be considered for geometric intersection graphs in the data streaming model. We will look in some detail at the interval selection problem, that is, finding a largest independent set in an interval graph, in the data streaming model. This part is joint work with Pablo PerezLantero. Towards the end of the talk I will restate a couple of unrelated problems that, I think, should get some attention. Coloring and Independent Sets of Rectangles: Recent Developments and New Challenges
[+] Parinya Chalermsook. This talk will focus on two problems on rectangle intersection graphs: (i) approximating the independence number of rectangle intersection graphs and (ii) upper bounding the chromatic number of a graph in terms of its clique number. The former question has received a lot of attention from the approximation algorithms community due to its close connections to other optimization problems, such as map labeling and network resource allocation. The latter question was raised in 1948 and there has been essentially no progress since 1960 (i.e. for about half a century.) There is a close connection between (i) and (ii). I will start by giving a survey of recent developments on both problems. Then I will present some intermediate open problems that would help in gaining further insights for (i) and (ii). These intermediate problems could be of independent interest. Intersection Graphs and Order Dimension
[+]
Stefan Felsner. Containment graphs are comparability graphs and have, for a long time, been related to the notion of order dimension. In this talk we focus on connections between intersection graphs and order dimension. The starting point of the story is the observation that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Refinements of this argument allow to distinguish between various classes of graphs that are sandwiched between grid intersection graph and bipartite permutations graphs. A construction involving grid intersection graphs is used for a new simple proof of the BrightwellTrotter Theorem. Finally we use intersection and containment graphs of triangles to show that recognition of partial orders of height two and dimension three is NPcomplete. This resolves a long standing complexity question. 

15:30  Coffee Break  
16:00  Workshop  Stochastic Geometry Session A (Blauwe Zaal) 

17:30 
Central limit theorems for random tessellations and random graphs
[+] Matthias Schulte. The topic of this talk are random tessellations and random graphs like PoissonVoronoi tessellations and the nearest neighbour graph, which play an important role in stochastic geometry. Since the exact behaviour of related quantities as the total edge length, for example, is often very hard to determine, one is interested in the asymptotic behaviour as the size of the underlying system gets large. For this situation central limit theorems are presented that allow to approximate random variables by standard Gaussian random variables if the size of the system is sufficiently large. All considered problems have in common that they are driven by an underlying Poisson point process. The central limit theorems can be deduced via general normal approximation results for random variables depending on Poisson point processes. Generalised Eden growth model and random planar trees
[+]
Sergei Zuyev. In a classical Eden growth model, a crystal on a grid extends to nearby nodes with the rate proportional to the number of already crystallised neighbours. This model is equivalent to firstpassage percolation with exponential passage time. An extension of this model is to allow a general weight for different number of crystallised neighbours. Classical subadditivity arguments allow establishing existence of a limiting shape for the most natural case of monotone rates: the more neighbours are crystallised, the sooner a boundary node crystallises too. However, a real challenge represent nonmonotone rates where all the classical approaches to establishing the shape result fail. Computer simulations suggest that even in this case a limiting shape does exist. We present partial results for such models and discuss some of their intriguing features: existence of holes, the exponential bound of their size and possible longrange structural dependence. 

Workshop  Computational Topology Session B (AUD 2) 

Introduction to Categories, Part II: Persistence via Category Theory [+] Vin de Silva. Following Liz's
presentation on interleaving, I will discuss the theory in a more
abstract way. This is joint work with Peter Bubenik and Jonathan Scott.
Topos Theory for Persistence [+]
Primoz Skraba. Persistent (co)homology has been studied from a variety of viewpoints: algorithmic, algebraic, and categorical. In this talk, I will describe a complementary approach, based on encoding the timevarying nature of the underlying topological space directly at the set level. In classical persistence, this was done by encoding the filtration with the action of a graded ring on the underlying space (multiplication by t in [CZ04]). One can generalize this by constraining how the topological space may change over time, e.g. in classical persistence it must grow and in zigzag persistence it may grow and shrink. We call these constraints, the shape of the theory of persistence. Using tools from topos theory, I will describe that if these constraints have a special structure (i.e. they form a Heyting algebra), we can automatically generate a corresponding persistence theory. No previous knowledge of topos theory is necessary and in addition to definitions and structural properties, aspects such as computation and stability will also be discussed. 

Workshop  Geometric Intersection Graphs Session C (AUD 7) 

"No k Pairwise Crossing" vs "No k Pairwise Disjoint"
[+] Andrew Suk. We will survey several problems surrounding an old conjecture which states that the number of edges in a graph drawn in the plane with no k pairwise crossing edges is at most linear in the number of vertices. We will also make comparisons to its "dual" counterpart, which is a conjecture of Pach and Tóth, stating that the number of edges in a graph drawn in the plane with no k pairwise disjoint edges is at most linear in the number of vertices. Both conjectures are still open, and in this talk, we will discuss several partial results and tools used in tackling these problems. Colorings of Geometric Intersection Graphs and Related Problems
[+] Bartosz Walczak. This talk will survey some recent results and open problems concerning proper colorings and Kkfree colorings (i.e. colorings in which every color class is required to induce a Kkfree graph) of geometric intersection graphs with bounded clique number. In particular, the following questions will be addressed: (i) In what classes of geometric intersection graphs is the (Kkfree) chromatic number bounded in terms of the clique number? (ii) How big can the (Kkfree) chromatic number be with respect to the number of vertices for other classes of geometric intersection graphs with bounded clique number? The talk will also discuss connections to other problems, in particular, to the wellknown conjecture that the number of edges in kquasiplanar graphs (i.e. graphs drawn in the plane with no k pairwise crossing edges) is linear with respect to the number of vertices. Open Problems Session

