Joint work with David Cohen-Steiner, Manish Mandad, Mathieu Desbrun and Leif Kobbelt.
In the first part of the talk, we present an optimal data structure to approximately answer if a query point $q$ is inside or outside of $K$. We attain logarithmic query time with storage of only $O(1/\epsilon^{(d-1)/2})$, which matches the worst-case lower bound on the complexity of any $\epsilon$-approximating polytope. Using known reductions, we obtain major improvements to approximate nearest neighbor searching.
In the second part, we show how the hierarchy can be used to construct an $\epsilon$-kernel in near-optimal time. Kernels provide an approximation to the convex hull, and therefore are on the basis of several geometric algorithms. We obtain major improvements to the complexity of other fundamental problems, such as approximate diameter, approximate bichromatic closest pair, and approximate Euclidean minimun bottleneck tree, as well as near-optimal preprocessing times to multiple data structures.
Task computability is very sensitive to the details of the model: failures (type and number of process and communication failures), communication (various forms of message passing and shared memory), and timing (relative process speeds and communication delays). However, the many possible distributed computing models can be understood through a common framework: There is an intimate relation between distributed computability and topology. Roughly speaking, the question whether a task is computable (and how fast) in a given model can be reduced to the question whether an associated geometric structure, called a simplicial complex has "holes" of certain dimensions. There are various implications of these insights. In particular, Turing computability is orthogonal to distributed computability. In distributed computing we allow for individual processes to have an infinite number of states, thus each one individually can solve the Halting problem, however, there are simple Turing-computable tasks that are not computable even in the presence of a single process crash. This talk presents an introduction to the fascinating topological perspective of distributed computing.
$\delta$-hyperbolic graphs are graphs that are close to trees from a metric point of view; we will present a few (of the many) definitions of hyperbolicity.
We will present some results relating the cop and robber game and the hyperbolicity of a graph. We show that if a graph is $\delta$-hyperbolic, then it is $(2r,r+2\delta)$-copwin for any $r$. Conversely, we show that a $(s,s')$-copwin graph (with $s>s'$) is $O(s^2)$-hyperbolic. From our approach, we deduce an $O(n^2)$ algorithm to approximate the hyperbolicity of a graph when we are given its distance matrix.
Travail en collaboration avec Rania Ibrahim, Semih Salihoglu et Maks Ovsjanikov.
In this talk we review the motivation for the Hirsch Conjecture, related to the complexity of the simplex method, we describe our constructions of counter-examples to it, and report on other attempts and progress on the question, mostly those that try to answer the diameter question by generalizing it to the world of simplicial complexes. This approach has a long history, starting by Adler and Dantzig’s definition of “abstract polytopes” which are nothing but “normal pseudo-manifolds”, but it is still (or again) an active area of research.
This is joint work with Kevin Buchin, Bart Jansen, and Gerhard Woeginger.
This is joint work with Sang Won Bae, Mark de Berg, Joachim Gudmundsson and Christos Levcopoulos.
This talk reports joint work with Karim Adiprasito, Bernd Gonska and Louis Theran.
Travail en collaboration avec Benoît Loisel.