Publications

Technical Reports

  • J. Giesen, L. Kühne. A parallel algorithm for computing the flow complex, [CGL-TR-89], November 2013

    We present a parallel algorithm and its implementation for computing the entire Hasse diagram of the flow complex of a point cloud in Euclidean space. Known algorithms for computing the flow complex in two and three dimensions compute the geometric realization of the flow complex and need to compute the Delaunay triangulation of the point cloud first. Our algorithm computes less information, namely only the Hasse diagram of the flow complex that is augmented with enough geometric information to allow the same topological multi-scale analysis of point cloud data as the alpha shape filtration without computing the Delaunay triangulation explicitly. We show experimental results for medium dimensions that demonstrate that our algorithm scales well with the number of available cores on a multicore architecture.

  • S. Stich, B. Gärtner. Random Pursuit in Hilbert Space, [CGL-TR-88], November 2013


    We define and analyze Random Pursuit (RP) -- a random walk in a Hilbert space. RP is defined by iterative projections onto randomly selected hyperplanes. This process originates from several applications in derivative-free optimization. In this report we study convergence in the induced norm. We present our results in a unifying way that allows to apply them in various settings. Especially, we recover the previously known convergence results from two applications.
  • C. Müller, S. Stich, B. Gärtner. Matrix-valued Iterative Random Projections, [CGL-TR-87], November 2013


    We analyze a matrix valued stochastic process with discrete time steps. The process originates from a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (D. Leventhal and A. S. Lewis., Optimization 60(3), 329--245, 2011). We do not only show convergence rates for summary statistics like trace and Frobenius norm but also study the expected convergence of the full eigenvalue spectrum.
  • J-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay triangulations of manifolds. [INRIA RR-8389,hal-00879133], [CGL-TR-86], October 2013


    We present an algorithmic framework for producing Delaunay triangulations of manifolds. The input to the algorithm is a set of sample points together with coordinate patches indexed by those points. The transition functions between nearby coordinate patches are required to be bi-Lipschitz with a constant close to 1. The primary novelty of the framework is that it can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. The output is a manifold simplicial complex that is the Delaunay complex of a perturbed set of points on the manifold. The guarantee of a manifold output complex demands no smoothness requirement on the transition functions, beyond the bi-Lipschitz constraint. In the smooth setting, when the transition functions are defined by common coordinate charts, such as the exponential map on a Riemannian manifold, the output manifold is homeomorphic to the original manifold, when the sampling is sufficiently dense.
  • J-D. Boissonnat, R. Dyer, A. Ghosh. The Stability of Delaunay Triangulations [INRIA RR-8276 , hal-00807050], [CGL-TR-85], April 2013


    This is a revised version of the first part of CGL-TR-25. We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of $\delta$-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged.
  • J-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay stability via perturbations [hal-00806107], [CGL-TR-84], March 2013


    We present an algorithm that takes as input a finite point set in Euclidean space, and performs a perturbation that guarantees that the Delaunay triangulation of the resulting perturbed point set has quantifiable stability with respect to the metric and the point positions. There is also a guarantee on the quality of the simplices: they cannot be too flat. The algorithm provides an alternative tool to the weighting or refinement methods to remove poorly shaped simplices in Delaunay triangulations of arbitrary dimension, but in addition it provides a guarantee of stability for the resulting triangulation.
  • J-D. Boissonnat, T. Dey, C. Maria. The Compressed Annotation Matrix: an Efficient Data Structure for Computing Persistent Cohomology,[CGL-TR-83], April 2013


    The persistent homology with coefficients in a field F coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substancially the amount of matrix operations. In addition, we propose heuristics to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology. Presented at ESA 2013.
  • F. Chazal, C. Labruère, M. Glisse, B. Michel, Optimal rates of convergence for persistence diagrams in topological Data Analysis, Arxiv 1394-1423, [CGL-TR-82], June 2013.


    Computational topology has recently seen an important development toward data analysis, giving birth to Topological Data Analysis. Persistent homology appears as a fundamental tool in this field. We show that the use of persistent homology can be naturally considered in general statistical frameworks. We establish convergence rates of persistence diagrams associated to data randomly sampled from any compact metric space to a well defined limit diagram encoding the topological features of the support of the measure from which the data have been sampled. Our approach relies on a recent and deep stability result for persistence that allows to relate our problem to support estimation problems (with respect to the Gromov-Hausdorff distance). Some numerical experiments are performed in various contexts to illustrate our results.
  • F. Chazal, J. Sun, Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure, Arxiv abs/1305.1172 [CGL-TR-81] , June 2013.

    In many real-world applications data appear to be sampled around 1-dimensional filamentary structures that can be seen as topological metric graphs. In this paper we address the metric reconstruction problem of such filamentary structures from data sampled around them. We prove that they can be approximated, with respect to the Gromov-Hausdorff distance by well-chosen Reeb graphs (and some of their variants) and we provide an efficient and easy to implement algorithm to compute such approximations in almost linear time. We illustrate the performances of our algorithm on a few data sets.

  • B. Gärtner, C. Müller, S. Stich. Variable Metric Random Pursuit: Experimental Validation, [CGL-TR-80], November 2013

    We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an approximate solution by repeated optimization over randomly chosen one-dimensional subspaces. The distribution of search directions is dictated by the chosen metric. Variable Metric RP uses novel variants of a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (D. Leventhal and A. S. Lewis., Optimization 60(3), 329--245, 2011). We here present (i) a refined analysis of the expected single step progress of RP algorithms and their global convergence on (strictly) convex functions and (ii) novel convergence bounds for V-RP on quadratic functions. We also quantify how well the employed metric needs to match the local geometry of the function in order for the RP algorithms to converge with the best possible rate on strongly convex functions. Our theoretical results are accompanied by extensive numerical experiments, comparing V-RP with the derivative-free schemes CMA-ES, Implicit Filtering, Nelder-Mead, NEWUOA, Pattern-Search and Nesterov's gradient-free algorithms.

  • Oren Salzman, Dan Halperin. Asymptotically near-optimal RRT for fast, high-quality, motion planning, [CGL-TR-79], November 2013.
    We present Lower Bound Tree-RRT (LBT-RRT), a single-query sampling-based algorithm that is asymptotically near-optimal. Namely, the solution extracted from LBT-RRT converges to a solution that is within an approximation factor of 1+epsilon of the optimal solution. Our algorithm allows for a continuous interpolation between the fast RRT algorithm and the asymptotically optimal RRT* and RRG algorithms. When the approximation factor is 1 (i.e., no approximation is allowed), LBT-RRT behaves like the RRT* algorithm. When the approximation factor is unbounded, LBT-RRT behaves like the RRT algorithm. In between, LBT-RRT is shown to produce paths that have higher quality than RRT would produce and run faster than RRT* would run. and a second, auxiliary tree, which we call the lower-bound tree. The combination of the two trees, which is faster to maintain than the tree maintained by RRT*, efficiently guarantee asymptotic near-optimality. We suggest to use LBT-RRT for high-quality, anytime motion planning. We demonstrate the performance of the algorithm for scenarios ranging from 3 to 12 degrees of freedom and show that even for small approximation factors, the algorithm produces high-quality solutions (comparable to RRT*) with little runtime overhead when compared to RRT.
    http://acg.cs.tau.ac.il/projects/LBT-RRT/project-page


  • I.Z. Emiris, D. Nicolopoulos. Randomized kd-trees for Approximate Nearest Neighbor Search, [CGL-TR-78.pdf], November 2013.

    We implement Randomized kd-trees in CGAL for approximate Nearest-Neighbor Search, based on the corresponding algorithms of the FLANN library. The input points are preprocessed into several tree data structures by modifying standard kd-trees: the trees adapt to the pointset by assigning higher probability in splitting along coordinates of high variance. The feature extends the 4.3 CGAL dD Spatial Searching functionality and introduces a new splitting rule extending the Splitter base class. It supports k nearest point searching. Our Randomized kd-trees are competitive to the FLANN implementation, and faster than CGAL kd-trees for high dimensions; we show tests in dimension 128.

  • I.Z. Emiris, I. Psarros, K. Chanseau Saint-Germain. Approximate Nearest Neighbor Search for Points on Lower-dimensional Flats, [CGL-TR-77.pdf], November 2013.

    In order to improve efficiency in Approximate Nearest Neighbor search, we exploit the structure of the input data by considering points that are distributed almost uniformly on flats of varying, lower dimension, where these flats are distributed uniformly within a bounding sphere. We exploit an existing mapping that transforms the (approximate) Nearest Flat search to a (approximate) Nearest point search; however there is an additive error as well when queries lie very close to flats. We achieve expected query time logarithmic in the number of flats when the ambient space dimension is fixed; this is squared when bounding complexity with high probability under mild assumptions. This work extends [CGL-TR-29, Sect.3] which considered collinear points. We also introduce a CGAL-based implementation and corroborate our theoretical results with experimental evidence. Our software is faster than CGAL kd-trees: e.g. for 5K points in 55 dimensions, or 30K points in 20 dimensions, with both sets lying on 2-dimensional flats, our code is about 5 times faster.

  • I.Z. Emiris, V. Fisikopoulos. Algorithms for volume approximation of convex bodies, [CGL-TR-76], November 2013.

    We survey results on the fundamental problem of computing the volume of d-dimensional convex bodies, with emphasis on randomized poly-time approximation algorithms for bodies represented by a membership oracle. We implement and experimentally study efficient algorithms for approximating the volume of polytopes given as an intersection of halfspaces, by developing efficient hit-and-run methods. Our emphasis is to exploit the geometry of the problem so as to improve runtime (or accuracy) for general dimensional polytopes. Our method handles skinny polytopes by applying appropriate rounding based on computing the minimum enclosing ellipsoid of a point sample. Our publicly available C++ software handles polytopes in dimensions substantially larger than exact volume computation software can do, e.g., it approximates the volume of d-dimensional cubes with at least 3 correct digits, for d up to 100, in about 20 min, whereas VINCI does not seem able to handle d-cubes for $d>20$. Our code also produces the best known approximations to the volume of Birkhoff polytopes of order beyond 10 within 4 hours; up to order 10, their volume has been exactly computed by specialized parallel software in a sequential time of years. Furthermore, uniform sampling
    is of independent interest in several machine learning applications such as sampling contingency tables and learning the p-value.

  • I.Z. Emiris, V. Fisikopoulos, B. Gärtner . Efficient edge skeleton computation for polytopes defined by oracles, [CGL-TR-75], November 2013.

    In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. whose complexity depends polynomially in the input and output sizes. It is thus important to identify polytope constructions for which total poly-time algorithms can be obtained. We offer the first total poly-time algorithm for computing the edge-skeleton (including vertex enumeration) of a polytope given by an optimization (aka LP) or a separation oracle, where we are also given a superset of its edge directions. All complexity bounds refer to the (oracle) Turing machine model. We also offer a workspace efficient variant of our algorithm by employing reverse search. We consider two main applications, where we obtain (weakly) total poly-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer an alternative approach removing the exponential dependence on the dimension in the complexity.

  • I.Z. Emiris, V. Fisikopoulos, L. Penaranda. High Dimensional Predicates: Update on Algorithms and Software, [CGL-TR-74], November 2013.

    Determinant predicates are the core procedures in many important geometric algorithms and become the bottleneck as the dimension of computation space grows. We study the sequences of determinants that appear in geometric algorithms so as to speed-up each predicate by using information from previously computed ones. In our technical report of October 2012 [CGL-TR-27] we proposed, implemented and experimentally evaluated algorithms for determinants in incremental convex hull and point location; we also presented an extended version of hashing determinants for a sequence of convex hull operations, and a CGAL submission of its implementation. In this report, we present an update on this work by proposing a dynamic determinant method for the gift wrapping convex hull algorithm, we present experiments on convex hulls for a real practical scenario, and give an update on our CGAL submission.
  • E. Ehsanfar, D. Feldman, C. Sohler. Orthogonal Range Clustering, [ CGL-TR-73.pdf], November 2013

    In this report, we explain the general idea and the notation of a fast technique that lead an approximation for orthogonal range clustering using coreset constructions. Given a range space (X, R) and a set P in X of n points in d-space, the goal of orthogonal range clustering is to find a k-clustering C of the points within any arbitrary range Q in R. For computing an approximation for C, we construct a weighted summary S of the points within Q by preprocess the points into a datastructure. We then show that the cost of clustering based on the summary has only a tinny different with the cost of the clustering for the original point set. For yielding summary S in a canonical approach, we modify the datastructure by small coreset constructions namely coreset plugins. Then for any range query Q, we analyze the process to compute an approximate clustering using this modified datastructure.

  • B. Gärtner, C. Helbling, Y. Ota, T. Takahashi. Large Shadows from Sparse Inequalities, [CGL-TR-72], November 2013

    The d-dimensional Goldfarb cube is a polytope with the property that all its 2d vertices appear on some shadow of it (projection onto a 2-dimensional plane). The Goldfarb cube is the solution set of a system of 2d linear inequalities with at most 3 variables per inequality. We show in this paper that the d-dimensional Klee-Minty cube — constructed from inequalities with at most 2 variables per inequality — also has a shadow with 2d vertices. In contrast, with one variable per inequality, the size of the shadow is bounded by 2d.

  • H. Tyagi, B. Gärtner. Continuum armed bandit problem of few variables in high dimensions, [CGL-TR-71], November 2013

    We consider the stochastic and adversarial settings of continuum armed bandits where the arms are indexed by [0,1]^d. The reward functions r:[0,1]^d -> R are assumed to intrinsically depend on at most k coordinate variables implying r(x_1,..,x_d) = g(x_{i_1},..,x_{i_k}) for distinct and unknown i_1,..,i_k from {1,..,d} and some locally Holder continuous g:[0,1]^k -> R with exponent 0 < alpha <= 1. Firstly, assuming (i_1,..,i_k) to be fixed across time, we propose a simple modification of the CAB1 algorithm where we construct the discrete set of sampling points to obtain a bound of O(n^((alpha+k)/(2*alpha+k)) (log n)^((alpha)/(2*alpha+k)) C(k,d)) on the regret, with C(k,d) depending at most polynomially in k and sub-logarithmically in d. The construction is based on creating partitions of {1,..,d} into k disjoint subsets and is probabilistic, hence our result holds with high probability. Secondly we extend our results to also handle the more general case where (i_1,...,i_k) can change over time and derive regret bounds for the same.

  • D. Feldman, A. Munteanu, C. Sohler. Smallest enclosing ball for probabilistic data, [CGL-TR-70], November 2013

    We deal with the smallest enclosing ball problem subject to probabilistic data. In our setting, any of n points may not or may occur at one of finitely many locations, following its own discrete probability distribution. The objective is therefore considered to be a random variable and we aim at finding a center minimizing the expected maximum distance to the points according to their distributions. Our main contribution presented in this report is to develop the first (1+ε)-approximation algorithm for the probabilistic smallest enclosing ball problem with extensions to the streaming setting.

  • H. Fichtenberger, M. Schmidt. PROBI: A Heuristic for the probabilistic $k$-median problem, [CGL-TR-69], November 2013

    We develop the heuristic PROBI for the probabilistic Euclidean k-median problem based on a coreset construction in [CGL-TR-02]. Our algorithm computes a summary of the data and then uses an adapted version of k-means++ by Arthur and Vassilvitskii to compute a good solution on
    the summary. The summary is maintained in a data stream, so PROBI can be used in a data stream setting on very large data sets.
    We experimentally evaluate the quality of the summary and of the computed solution and compare the running time to state of the art data stream clustering algorithms.

  • D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier. Homological Reconstruction and Simplification in R³, [CGL-TR-68], November 2013

    We consider the problem of deciding whether the persistent homology group of a simplicial pair (K, L) can be realized as the homology H∗(X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R³.
    As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S³ within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.

  • J. Giesen, L. Kühne, S. Laue. Sketching the Support of a Probability Measure, [CGL-TR 67], November 2013

    We want to sketch the support of a probability measure on Euclidean space from samples that have been drawn from the measure. This problem is closely related to certain manifold learning problems, where one assumes that the sample points are drawn from a manifold that is embedded in Euclidean space. Here we propose to sketch the support of the probability measure (that does not need to be a manifold) by some gradient flow complex, or more precisely by its Hasse diagram. The gradient flow is defined with respect to the distance function to the sample points. We prove that a gradient flow complex (that can be computed) is homotopy equivalent to the support of the measure for sufficiently dense samplings, and demonstrate the feasibility of our approach on real world data sets.

  • J. Giesen, S. Laue, J. Mueller. Compressing Support Vector Machines, [CGL-TR 66], November 2013

    A support vector machine is an optimization problem that takes as input n feature vectors of length m. Hence, to store the input memory of size O(nm) is needed. We show how to construct another support vector machine whose input are n feature vectors of total size only O(n log n) that are derived from the original feature vectors by a random projection. Here, we do not assume that the data matrix is sparse or of low rank. Instead, we rely on the weaker assumption that the solution is sparse. We also provide an algorithm for recovering an approximate solution to the original problem from an optimal solution to the compressed problem, where the approximation factor depends on the compression ratio. The original feature vectors can be streamed from secondary memory, e.g., from tape or hard drive, to fast main
    memory and compressed on the fly into the new feature vectors. With this compression scheme the memory requirement for the support vector machine can be reduced from O(nm) to O (n + m) log n . Reducing the memory requirement becomes beneficial when the original feature vectors do not fit into main memory. In this case state-of-the-art iterative solvers need to access the slower secondary memory repeatedly, which can be avoided if the compressed feature vectors fit into main memory.

  • M. Buchet, F. Chazal, S. Oudot, and D. Sheehy. Efficient and Robust Persistent Homology for Measures, CGL-TR-65, November 2013.

    We extend the notion of the distance to a measure from Euclidean space to probability measures on general metric spaces as a way to do topological data analysis in a way that is robust to noise and outliers. We then give an efficient way to approximate the sublevel sets of this function by a union of metric balls and extend previous results on sparse Rips filtrations to this setting. This robust and efficient approach to topological data analysis is illustrated with several examples from an implementation.

  • G. Miller and D. Sheehy. A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations, [CGL-TR 64], November 2013.

    We describe a new algorithm for computing the Voronoi diagram of a set of n points in constant-dimensional Euclidean space. The running time of our algorithm is O( f log n log s) where f is the output complexity of the Voronoi diagram and s is the spread of the input, the ratio of largest to smallest pairwise distances. Despite the simplicity of the algorithm and its analysis, it improves on the state of the art for all inputs with polynomial spread and near-linear output size. The key idea is to first build the Voronoi diagram of a superset of the input points using ideas from Voronoi refinement mesh generation. Then, the extra points are removed in a straightforward way that allows the total work to be bounded in terms of the output complexity, yielding the output sensitive bound. The removal only involves local flips and is inspired by kinetic data structures.

  • S. Oudot and D. Sheehy. Zigzag Zoology: Rips-like zigzags for Homology Inference, [CGL-TR 63], November 2013.

    For points sampled near a compact set X, the persistence barcode of the Rips filtration built from the sample contains information about the homology of X as long as X satisfies some geometric assumptions. The Rips filtration is prohibitively large, however zigzag persistence can be used to keep the size linear. We present several species of Rips-like zigzags and compare them with respect to the signal-to-noise ratio, a measure of how well the underlying homology is represented in the persistence barcode relative to the noise in the barcode at the relevant scales. Some of these Rips-like zigzags have been available as part of the Dionysus library for several years while others are new. Interestingly, we show that some species of Rips zigzags will exhibit less noise than the (non-zigzag) Rips filtration itself. Thus, Rips zigzags can offer improvements in both size complexity and signal-to-noise ratio.

    Along the way, we develop new techniques for manipulating and comparing persistence barcodes from zigzag modules. We give methods for reversing arrows and removing spaces from a zigzag while controlling the changes occurring in its barcode. We also discuss factoring zigzags and a kind of interleaving of two zigzags that allows their barcodes to be compared. These techniques were developed to provide our theoretical analysis of the signal-to-noise ratio of Rips-like zigzags, but they are of independent interest as they apply to zigzag modules generally.

  • G. Miller, D. Sheehy, and A. Velingker. A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs, [CGL-TR 62], November 2013.

    We present a new algorithm that produces the 1-dimensional skeleton of a Delaunay mesh for point sets in any dimension with guaranteed optimal mesh size and quality. Our comparison based algorithm runs in time O(2^{O( d)}(n log n + m)), where n is the input size, m is the output point set size, and d is the ambient dimension. The constants only depend the desired element quality bounds. To gain this new efficiency the algorithm only maintains the neighbors of each point in the mesh. Thus if one only wants the neighbors structure of a reduced mesh then the algorithm will return with a size O(2^{O( d)}( n)) graph in O(2^{O( d)}(n log n)) time.

  • D. Sheehy. Geometric Separators and the Parabolic Lift, [CGL-TR 61], November 2013.

    A geometric separator for a set U of n geometric objects (usually balls) is a small (sublinear in n) subset whose removal disconnects the intersection graph of U into roughly equal sized parts. These separators provide a natural way to do divide and conquer in geometric settings. A particularly nice geometric separator algorithm originally introduced by Miller and Thurston has three steps: compute a centerpoint in a space of one dimension higher than the input, compute a conformal transformation that ``centers'' the centerpoint, and finally, use the computed transformation to sample a sphere in the original space. The output separator is the subset of S intersecting this sphere. It is both simple and elegant. We show that a change of perspective (literally) can make this algorithm even simpler by eliminating the entire middle step. By computing the centerpoint of the points lifted onto a paraboloid rather than using the stereographic map as in the original method, one can sample the desired sphere directly, without computing the conformal transformation.

  • Ramsay Dyer, Gert Vegter, and Mathijs Wintraecken, Intrinsic simplices in Riemannian manifolds, [CGL-TR-60], October 2013.

    We study a natural definition of geometric simplices in Riemannian manifolds of arbitrary dimension n. Given a finite set of vertices in a convex neighbourhood on the manifold, these geometric simplices are defined using Karcher means: the minimum of the function on M given by the weighted sum of squared distances to the vertices. The weights are the barycentric coordinates. In this way the barycentric coordinates of the standard Euclidean simplex are mapped smoothly to the manifold. Our contribution is to articlulate conditions that guarantee that this map is a smooth embedding. If it is not, we say the Riemannian simplex is degenerate. Quality measures for the ``thickness'' or ``fatness'' of Euclidean simplices can be adapted to apply to these Riemannian simplices. For manifolds of dimension 2, the simplex is non-degenerate if it has a positive quality measure, as in the Euclidean case. However when the dimension is greater than two, non-degeneracy can be guaranteed only when the quality exceeds a positive bound that depends on the size of the simplex and local bounds on the sectonal curvatures. This result provides a general tool and represents a step towards specific sampling conditions for triangulating manifolds.
  • Philipp Lucas, Lars Kühne, Joachim Giesen, Sclow Plots: Visualizing Empty Space [CGL-TR-59], October 2013

    Scatter plots are mostly used for correlation analysis, but are also a useful tool for understanding the distribution of high-dimensional point cloud data. An important characteristic of such distributions are clusters, and scatter plots have been used successfully to identify clusters in data. Another characteristic of point cloud data that has received less attention so far are regions that contain no or only very few data points. We show that augmenting scatter plots by projections of flow lines along the gradient vector field of the distance function to the point cloud reveals such empty regions or voids. The augmented scatter plots, that we call sclow plots, enable a much better understanding of the geometry underlying the point cloud than traditional scatter plots. We demonstrate the feasibility of our approach on synthetic and real world data sets.
  • F. Cazals and T. Dreyfus and S. Sachdeva and N. Shah, Greedy Geometric Algorithms for Collection of Balls with Applications to Geometric Approximation and Molecular Coarse-Graining,[CGL-TR-58], September 2013.
    Choosing balls which best approximate a 3D object is a non trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object O defined by a union of n balls with k<n balls defining a region S subset of O. This solution is further used to construct an outer approximation enclosing the initial shape, and an interpolated approximation sandwiched between the inner and outer approximations. The inner approximation problem is reduced to a geometric generalization of weighted max k-cover, solved with the greedy strategy which achieves the classical 1-1/e lower bound. The outer approximation is reduced to exploiting the partition of the boundary of O by the Apollonius Voronoi diagram of the balls defining the inner approximation. Implementation-wise, we present robust software incorporating the calculation of the exact Delaunay triangulation of points with degree two algebraic coordinates, of the exact medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. Application-wise, we exhibit accurate coarse-grain molecular models using a number of balls 20 times smaller than the number of atoms, a key requirement to simulate crowded cellular environments.
  • F. Cazals and J. Qin and A. Roth, Refined Analysis of Transitions on RNA Landscapes, CGL-TR-57, September 2013. Energy landscape of RNA molecules are instrumental to predict the stable secondary structures, and the folding intermediates yielding them. In particular, transition analysis carried out so far for two neighboring conformations corresponding to local minima are based on the notion of saddle height, namely the lowest energy of a saddle found on paths joining these two conformations. However, a route through a saddle realizing the saddle height may not be favored if it features high energy gradients.In this work, we therefore explore a broader class of transitions. First, given a Boltzmann sampling of a RNA landscape, possibly non connected, we develop an algorithm to connect it, based on two ingredients, namely an algorithm reporting nearest neighbors in a (non Euclidean) metric space, and an iterative strategy a-la Kruskal to bridge the gaps between the connected components of the initial sampling. Second, we apply our construction of sampled based Morse-Smale diagram to analyze the connected landscape, reporting in particular a broader class of index one saddles than those found in previous work. Using the connexions between local minima and these index one saddle, we enumerate a broader class of transition paths, and exhibit in particular paths reaching elevation higher than the saddle height, yet, with more moderate energy gradient.

  • F. Cazals and C. Mueller and C. Robert and A. Roth, Towards Morse theory for point cloud data, CGL-TR-56, September 2013.
    Morse theory provides a powerful framework to study the topology of a manifold from a function defined on it, but discrete constructions have remained elusive due to the difficulty of translating smooth concepts to the discrete setting. Consider the problem of approximating the Morse-Smale (MS) complex of a Morse function from a point cloud and an associated nearest neighbor graph (NNG). While following the constructive proof of the Morse homology theorem, we present novel concepts for critical points of any index, and the associated Morse-Smale diagram. Our framework has three key advantages. First, it requires elementary data structures and operations, and is thus suitable for high-dimensional data processing. Second, it is gradient free, which makes it suitable to investigate functions whose gradient is unknown or expensive to compute. Third, in case of under-sampling and even if the exact (unknown) MS diagram is not found, the output conveys information in terms of ambiguous flow, and the Morse theoretical version of topological persistence, which consists in canceling critical points by flow reversal, applies. On the experimental side, we present a comprehensive analysis of a large panel of bi-variate and tri-variate Morse functions whose Morse-Smale diagrams are known perfectly, and show that these diagrams are recovered perfectly. In a broader perspective, we see our framework as a first step to study complex dynamical systems from mere samplings consisting of point clouds.
  • K. Solovey, O. Salzman, and D. Halperin. Discrete RRT for Exploration of Implicit Roadmaps in Multi-Robot Motion Planning [CGL-TR-55], October 2013

    We present a sampling-based framework for multi-robot motion planning which incorporates an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaption of the celebrated RRT algorithm, for the discrete case of a graph. By rapidly exploring the high-dimensional configuration space represented by the implicit roadmap, dRRT is able to reach subproblems where minimal coordination between the robots is required. Integrating the implicit representation of the roadmap, the dRRT algorithm, and techniques that are tailored for such subproblems on the implicit roadmap allows us to solve multi-robot problems while exploring only a small portion of the configuration space. We demonstrate our approach experimentally on scenarios of up to 48 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.
    http://acg.cs.tau.ac.il/projects/drrt/drrt
  • Efi Fogel and Dan Halperin, Polyhedral Assembly Partitioning with Infinite Translations or The Importance of Being Exact [CGL-TR-54], September 2013

    Assembly partitioning with an infinite translation is the application of an infinite translation to partition an assembled product into two complementing subsets of parts, referred to as a subassemblies, each treated as a rigid body. We present an exact implementation of an efficient algorithm, based on the general framework designed by Halperin, Latombe, and Wilson, to obtain such a motion and subassemblies given an assembly of polyhedra in R3. We do not assume general position.
    Namely, we can handle degenerate input, and we produce exact results. As often occurs, motions that partition a given assembly or subassembly might be isolated in the infinite space of motions. Any perturbation of the input or of intermediate results, caused by, for example, imprecision, might result with dismissal of valid partitioning-motions. In the extreme case where there is only a finite number of valid partitioning-motions, as occurs in the assembly shown to the right, no motion may be found, even though such exists. Proper handling requires significant enhancements applied to the original algorithmic framework.
    The implementation is based on software components that have been developed and introduced only recently. They paved the way to a complete, efficient, and elegant implementation. Additional information about some of these components is available at Arrangement of Geodesic Arcs on a Sphere.
    http://acg.cs.tau.ac.il/projects/internal-projects/assembly-partitioning/project-page

  • D.Atariah, S. Ghosh, G. Rote, On the Parameterization and the Geometry of the Configuration Space of a Single Planar Robot, [CGL-TR 53], August 2013

    Abstract: Translating and rotating planar polygonal robots are studied in the literature for decades. An integral part of this study is the configuration space which corresponds to the work space. In the context of motion planning problems, the boundary between the free and forbidden parts of the configuration space plays a major role. In this report we find an explicit parameterization of the boundary of the forbidden space. Using this parameterization we detail several geometrical properties of the various elements which constitute this boundary. In addition, this parameterization enables us to visualize these elements.
    This entry contains both a conference paper and the extended technical report.

  • D.Atariah, G. Rote, Configuration Space Visualization, [CGL-TR 52], December 2012

    Abstract: Based on a simple parameterization of contact surfaces, we visualize both the workspace and the corresponding config- uration space of a planar polygonal robot that moves amid planar polygonal obstacles.
  • F. Cazals, E. Ehsanfar, D. Halperin, R. van de Weijgaert, Report on Heterogeneous and Missing Data, Technical report [CGL-TR 51], October 2012


    Abstract: We give a survey of the main approaches that are commonly used for dealing with missing and heterogeneous data in different geometric contexts.

  • L. Kühne, J. Giesen, Z. Zhang, S. Ha, K. Mueller, A Data-Driven Approach to Hue-Preserving Color-Blending, Technical report [CGL-TR 50] , October 2012

    Abstract: Color mapping and semitransparent layering play an important role in many visualization scenarios, such as information visualization and volume rendering. The combination of color and transparency is still dominated by standard alpha-compositing using the Porter-Duff over operator which can result in false colors with deceiving impact on the visualization. Other more advanced methods have also been proposed, but the problem is still far from being solved. Here we present an alternative to these existing methods specifically devised to avoid false colors and preserve visual depth ordering. Our approach is data driven and follows the recently formulated knowledge-assisted visualization (KAV) paradigm. Preference data, that have been gathered in web-based user surveys, are used to train a support-vector machine model for automatically predicting an optimized hue-preserving blending. We have applied the resulting model to both volume rendering and a specific information visualization technique, illustrative parallel coordinate plots. Comparative renderings show a significant improvement over previous approaches in the sense that false colors are completely removed and important properties such as depth ordering and blending vividness are better preserved. Due to the generality of the defined data-driven blending operator, it can be easily integrated also into other visualization frameworks.

  • J. Giesen, Sören Laue, J. Mueller, Basis Expansions for Support Vector Machines, Technical report [CGL-TR 49] , October 2012

    Abstract: Recently, it has been pointed out by Chapelle that there is no reason not to consider training Support Vector Machines (SVMs) in the primal, although training SVMs is still almost exclusively introduced using the dual formulation. Here we explore the use of kernels in the primal formulation of SVMs on some set $\Omega$. Working in the primal shifts the focus from kernels on $\Omega$ to orthonormal bases of Hilbert spaces of functions on $\Omega$. Such basis functions can be derived from a kernel on $\Omega$, but in general the basis function view offers more flexibility. We discuss two examples of this added flexibility, namely non-uniformity and incremental construction of basis functions.

  • A. Bansal, F. Cazals, N. Malod-Dognin, Characterizing the Morphology of Protein Binding Patches, Technical report [CGL-TR 48] , October 2012

    Abstract: Let the patch of a partner in a protein complex be the collection of atoms accounting for the interaction. To improve our understanding of the structure-function relationship, we present a patch model decoupling the topological and geometric properties. While the geometry is classically encoded by the atomic positions, the topology is recorded in a graph encoding the relative position of concentric shells partitioning the interface atoms. The topological - geometric duality provides the basis of a generic dynamic programming based algorithm comparing patches at the shell level, which may favor topological or geometric features. On the biological side, we address four questions, using 249 co-crystallized heterodimers organized in biological families: (i) we dissect geometric versus topological properties of patches (ii) we show that our encoding is effective to carry out atomic resolution comparison of patches (iii) we use our comparison algorithms to infer specificity related information amidst a database of complexes (iv) we exhibit a descriptor outperforming its contenders to predict the binding affinities of the affinity benchmark, a key problem for the analysis of transitions on energy landscapes.

  • Y. Brise and B. Gaertner, Convergence Rate of the DIRECT Algorithm, Technical Report [CGL-TR 47], October 2012

    Abstract: The {DIRECT} algorithm is a deterministic sampling method for Lipschitz continuous function optimization. We give the first quantitative analysis of the convergence rate of DIRECT. We show that, in $\mathbb{R}^d$, $O(d^{2d+2} \frac{1}{\epsilon^{2d}})$ function evaluations are sufficient to guarantee an absolute error in function value not larger than $\epsilon$. Dropping Lipschitz continuity the same bound applies to the sampling distance from the location of the global minimum, with an even better hidden constant.

  • S. Stich and C. Mueller, On spectral invariance of Randomized Hessian and Covariance Matrix Adaptation schemes, Technical Report [CGL-TR 46], October 2012

    Abstract: We evaluate the performance of several gradient-free variable-metric continuous optimization schemes on a specific set of quadratic functions. We revisit a randomized Hessian approximation scheme (D. Leventhal and A. S. Lewis. Randomized Hessian estimation and directional search, 2011), discuss its theoretical underpinnings, and introduce a novel, numerically stable implementation of the scheme (RH). For comparison we also consider closely related Covariance Matrix Adaptation (CMA) schemes. A key goal of this study is to elucidate the influence of the distribution of eigenvalues of quadratic functions on the convergence properties of the different variable-metric schemes. For this purpose we introduce a class of quadratic functions with parameterizable spectra.

  • A. v. Dziegielewski, M. Hemmer and E. Schoemer, High Quality Conservative Surface Mesh Generation for Swept Volumes, Technical Report [CGL-TR 45], October 2012

    Abstract: We present a novel, efficient and flexible scheme to generate a high quality mesh that approximates the outer boundary of a swept volume. This is an updated and expanded version of Technical Report [CGL-TR-05].
    http://acg.cs.tau.ac.il/projects/swept-volume/project-page

  • S. Stich and C. Mueller and B. Gaertner, Variable Metric Random Pursuit, Technical Report CGL-TR-44.pdf, October 2012.

    Abstract: We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an approximate solution by repeated optimization over randomly chosen one-dimensional subspaces. The distribution of search directions is dictated by the chosen metric. Variable Metric RP uses novel variants of a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (D. Leventhal and A. S. Lewis., Optimization 60(3), 329--245, 2011). We here present (i) a refined analysis of the expected single step progress of RP algorithms and their global convergence on (strictly) convex functions and (ii) novel convergence bounds for V-RP on convex quadratic functions. We also quantify how well the employed metric needs to match the local geometry of the function in order for the RP algorithms to converge with the best possible rate on strongly convex functions. Our theoretical results are accompanied by illustrative experiments on Nesterov's worst case function and quadratic functions with (inverse) sigmoidal eigenvalue distributions.

  • G. Vegter and M.H.M.J.Wintraecken, A conceptual take on invariants of low-dimensional manifolds found by integration, Technical Report CGL-TR-43.pdf, October 2012.

    Abstract: An elementary proof of the fact that the Euler characteristic is the only topological invariant of a surface that can be found by integration (using Gauss-Bonnet) is given. A similar method is also applied to three dimensional manifolds.

  • G. Vegter and M.H.M.J.Wintraecken, On the extrinsic nature of triangulations, Technical Report CGL-TR-42.pdf , October 2012.

    Abstract: The extrinsic nature of the complexity of triangulations and more generally approximations in higher codimension is exhibited.

  • D. Shaharabani, O. Salzman, P. K. Agarwal and D. Halperin, Sparsification of Motion-Planning Roadmaps by Edge Contraction, (arXiv:1209.4463), Technical Report [CGL-TR-41], October 2012

    Abstract: We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction—the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.
    http://acg.cs.tau.ac.il/projects/rsec/project-page

  • O. Salzman, M. Hemmer and Dan Halperin, On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages, (arXiv:1202.5249), Technical Report [CGL-TR 40] , October 2012

    Abstract: We extend our study of Motion Planning via Manifold Samples (MMS), a general algorithmic framework that combines geometric methods for the exact and complete analysis of low-dimensional configuration spaces with sampling-based approaches that are appropriate for higher dimensions. The framework explores the configuration space by taking samples that are entire low-dimensional manifolds of the configuration space capturing its connectivity much better than isolated point samples. The contributions of this paper are as follows: (i) We present a recursive application of MMS in a six-dimensional configuration space, enabling the coordination of two polygonal robots translating and rotating amidst polygonal obstacles. In the adduced experiments for the more demanding test cases MMS clearly outperforms PRM, with over 20-fold speedup in a coordination-tight setting. (ii) A probabilistic completeness proof for the most prevalent case, namely MMS with samples that are affine subspaces. (iii) A closer examination of the test cases reveals that MMS has, in comparison to standard sampling-based algorithms, a significant advantage in scenarios containing high-dimensional narrow passages. This provokes a novel characterization of narrow passages which attempts to capture their dimensionality, an attribute that had been (to a large extent) unattended in previous definitions.
    http://acg.cs.tau.ac.il/projects/mms/project-page

  • K. Solovey and D. Halperin, k-Color Multi-Robot Motion Planning, (arXiv:1202.6174), Technical Report [CGL-TR-39], October 2012

    Abstract: We present a simple and natural extension of the multi-robot motion planning problem where the robots are partitioned into groups (colors), such that in each group the robots are interchangeable. Every robot is no longer required to move to a specific target, but rather to some target placement that is assigned to its group. We call this problem k-color multi-robot motion planning and provide a sampling-based algorithm specifically designed for solving it. At the heart of the algorithm is a novel technique where the k-color problem is reduced to several discrete multi-robot motion planning problems. These reductions amplify basic samples into massive collections of free placements and paths for the robots. We demonstrate the performance of the algorithm by an implementation for the case of disc robots in the plane and show that it successfully and efficiently copes with a variety of challenging scenarios, involving many robots, while a simplified version of this algorithm, that can be viewed as an extension of a prevalent sampling-based algorithm for the k-color case, fails even on simple scenarios. Interestingly, our algorithm outperforms a state-of-the-art implementation for the standard multi-robot problem, in which each robot has a distinct color.
    http://acg.cs.tau.ac.il/projects/kcolor/k-color-multi-robot-motion-planning

  • E. Fogel, M. Hemmer, A.Porat and D. Halperin, Lines Through Segments in 3D Space, Technical Report [CGL-TR-38], October 2012

    Abstract: Given a set S of n line segments in three-dimensional space, finding all the lines that simultaneously intersect at least four line segments in S is a fundamental problem that arises in a variety of domains. We refer to this problem as the lines-through-segments problem, or LTS for short. We present an efficient output-sensitive algorithm and its implementation to solve the LTS problem. The implementation is exact and properly handles all degenerate cases. To the best of our knowledge, this is the first algorithm (and implementation) for the LTS problem that is (i) output sensitive and (ii) handles all degenerate cases. The algorithm runs in O((n^3 + I)log n) time, where I is the output size, and requires O(n log n + J) working space, where J is the maximum number of output elements that intersect two fixed line segments; I and J are bounded by O(n^4) and O(n^2), respectively. We use CGAL arrangements and in particular its support for two-dimensional arrangements in the plane and on the sphere in our implementation. The efficiency of our implementation stems in part from careful crafting of the algebraic tools needed in the computation. We also report on the performance of our algorithm and its implementation compared to others.
    http://acg.cs.tau.ac.il/projects/lts/project-page

  • M. Hemmer, M. Kleinbort and D. Halperin, Improved Implementation of Point Location in General Two-Dimensional Subdivisions, (arXiv:1205.5434), Technical Report [CGL-TR-37] , October 2012

    Abstract: We present a major revamp of the point-location data structure for general two-dimensional subdivisions via randomized incremental construction, implemented in CGAL, the Computational Geometry Algorithms Library. We can now guarantee that the constructed directed acyclic graph G is of linear size and provides logarithmic query time. Via the construction of the Voronoi diagram for a given point set S of size n, this also enables nearest-neighbor queries in guaranteed O(log n) time. Another major innovation is the support of general unbounded subdivisions as well as subdivisions of two-dimensional parametric surfaces such as spheres, tori, cylinders. The implementation is exact, complete, and general, i.e., it can also handle non-linear subdivisions. Like the previous version, the data structure supports modifications of the subdivision, such as insertions and deletions of edges, after the initial preprocessing. A major challenge is to retain the expected O(n log n) preprocessing time while providing the above (deterministic) space and query-time guarantees. We describe an efficient preprocessing algorithm, which explicitly verifies the length L of the longest query path in O(n log n) time. However, instead of using L, our implementation is based on the depth D of G. Although we prove that the worst case ratio of D and L is Theta(n/log n), we conjecture, based on our experimental results, that this solution achieves expected O(n log n) preprocessing time.
    http://acg.cs.tau.ac.il/projects/lppl/guaranteed-logarithmic-planar-point-location

  • F. Chazal, V. de Silva, S. Oudot, Persistence Stability for Geometric complexes, ( arXiv:1207.3885), Technical Report [CGL-TR-36] , October 2012.

    Abstract: In this paper we study the properties of the homology of different geometric filtered complexes (such as Cech, Vietoris-Rips and witness complexes) built on top of precompact spaces. Using recent developments in the theory of topological persistence we provide simple and natural proofs of the stability of the persistent homology of such complexes with respect to the Gromov--Hausdorff distance. We also exhibit a few noteworthy properties of the homology of the Rips and Cech complexes built on top of compact spaces.

  • F. Chazal, V. de Silva, M. Glisse, S. Oudot, The Structure and Stability of Persistence Modules, ( arXiv:1207.3674), Technical Report [CGL-TR-35] , October 2012.

    Abstract: We give a self-contained treatment of the theory of persistence modules indexed over the real line. We give new proofs of the standard results. Persistence diagrams are constructed using measure theory. Linear algebra lemmas are simplified using a new notation for calculations on quiver representations. We show that the stringent finiteness conditions required by traditional methods are not necessary to prove the existence and stability of the persistence diagram. We introduce weaker hypotheses for taming persistence modules, which are met in practice and are strong enough for the theory still to work. The constructions and proofs enabled by our framework are, we claim, cleaner and simpler.

  • M. Aanjaneya, F. Chazal, D. Chen, M. Glisse, L. J. Guibas, D. Morozov, Metric Graph Reconstruction from Noisy Data, (to appear in Intern. Journal on Computational Geometry and Applications 2012), Technical Report [CGL-TR-34] , October 2012.

    Abstract: Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs. Building on the notions of correspondence and Gromov-Hausdorff distance in metric geometry, we describe a model for such data sets as an approximation of an underlying metric graph. We present a novel algorithm that takes as an input such a data set, and outputs the underlying metric graph with guarantees. We also implement the algorithm, and evaluate its performance on a variety of real world data sets.

  • Donald Sheehy. A Multicover Nerve for Geometric Inference , Technical Report [CGL-TR-33] , October 2012.

    Abstract: We show that filtering the barycentric decomposition of a Cech complex by the cardinality of the vertices captures precisely the topology of k-covered regions among a collection of balls for all values of k. Moreover, we relate this result to the Vietoris-Rips complex to get an approximation in terms of the persistent homology.

  • Donald Sheehy. New Bounds on the Size of Optimal Meshes , Technical Report [CGL-TR-32] , October 2012.

    Abstract: We give tight bounds on the complexity of Delaunay Refinement meshes in terms of a geometric property of the input.

  • Donald Sheehy. Linear-Size Approximations to the Vietoris-Rips Filtration , Technical Report [CGL-TR-31] , October 2012.

    Abstract: Given a finite metric space of bounded doubling dimension, we give a linear-size filtered simplicial complex that has a persistence diagram that is provably close to that of the Vietoris-Rips filtration.

  • Sivaraman Balakrishnan, Alessandro Rinaldo, Aarti Singh, Donald R. Sheehy and Larry Wasserman. Minimax Rates for Homology Inference , Technical Report [CGL-TR-30] , October 2012.

    Abstract: We prove matching upper and lower bounds on the minimax sampling rate necessary to infer the homology of submanifolds in R^n under a variety of noise models.

  • Ioannis Emiris, Alexandros Konstantinakis-Karmis, Dimitri Nicolopoulos, Emmanouil Thanos-Filis. Data structures for Approximate Nearest neighbor search , Technical Report CGL-TR-29.pdf, October 2012.

    Abstract: We discuss data-structures and algorithms for three related questions in approximate Nearest-Neighbor Searching (NNS). For dimensions 3-5, we implement an improved Approximate Voronoi Diagram, based on the work of Arya, Malamatos, and Mount. This is the first implementation of the method and we show it is competitive to state-of-the-art NNS libraries. For high dimensions (e.g. 50 and beyond), we implement randomized kd-trees in CGAL, based on the corresponding algorithms of the FLANN library, and show they are competitive to FLANN and faster than CGAL kd-trees. Lastly, we study structured data, namely points almost aligned on unknown lines. We show that NNS queries take expected time proportional to loglog(n), where n denotes the number of points, when there are polylog(n) lines, uniformly distributed in a sphere, and the space dimension is fixed.

  • Ioannis Emiris, Vissarion Fisikopoulos, Christos Konaxis, Luis Penaranda: An oracle-based, output-sensitive algorithm for projections of resultant polytopes , Technical Report CGL-TR-28.pdf , October 2012.

    Abstract: We compute (projections of) the resultant polytope by designing an efficient vertex oracle, which is called once per vertex and facet of the output polytope. The oracle reduces to a regular triangulation. Resultants are fundamental in system solving and in implicitizing parametric (hyper)surfaces. Their polytope is a Minkowski summand of the secondary polytope, but our method avoids computing the latter because it is typically too large. We obtain V- and H-representations as well as a triangulation of the resultant polytope. Our method applies to polytopes represented by oracles, and leads to a fast computation of polytope approximation. Our publicly-available software is based upon the experimental CGAL package "triangulation". It computes instances of 6- or 7-d polytopes with 23K or 500 vertices, resp., within 2hrs, and is faster than tropical geometry software up to dimension 6.

  • Ioannis Emiris, Vissarion Fisikopoulos, Luis Penaranda: High-dimensional predicates: Algorithms and software , Technical Report CGL-TR-27.pdf , October 2012.

    Abstract: We implement linear algebra techniques to exploit structural properties of determinantal predicates, namely in the case of sequences of determinants where the corresponding matrices change by one row or column. In particular, we optimize sequences of Orientation predicates for convex hull computations and point location, and show an asymptotic quadratic and linear complexity, respectively, and practical speedups of up to 4x and 78x in dimension 4-12. Our second contribution focuses on hashing minors when computing regular triangulations, where the matrix entries that change belong to a single row or column. This accelerates execution up to 100x in constructing resultant polytopes. This package has been submitted to CGAL.

  • Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh : Constructing intrinsic Delaunay triangulations of submanifolds, Technical Report [CGL-TR-26], October 2012.

    Abstract: We describe an algorithm to construct an intrinsic Delaunay triangulation of a smooth closed submanifold of Euclidean space.

  • Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh : Delaunay-type structures for manifolds I: Stability, Technical Report [ CGL-TR-25 ], October 2012.

    Abstract: We introduce a parameterised notion of genericity for Delaunay complexes and show that a bound on the genericity yields a bound on the quality of the Delaunay simplices and on the stability of the Delaunay complex under perturbations of the points or the metric.

  • Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Steve Oudot : Equating the witness and restricted Delaunay complexes, Technical Report CGL-TR-24 , October 2011.

    Abstract: This work provides an analysis of the reasons why the restricted Delaunay and witness complexes fail to include each other. From this, a new set of conditions naturally arises under which the two complexes are equal.

  • Christian Sohler, David Woodruff: Subspace Embeddings for the L1-norm with Applications. Technical Report CGL-TR-23, to appear.

    Abstract: We develop new oblivious embeddings for subspaces of L1 and use them to obtain improved streaming algorithms for L1-regression.

  • Claire Caillerie, Bertrand Michel: Model selection for simplicial approximation, Technical Report CGL-TR-22 , October 2011.

  • Frederic Chazal, Leonidas Guibas, Steve Oudot, Primoz Skraba: Persistence-Based Clustering in Riemannian Manifolds, Technical Report CGL-TR-21 , October 2011.

  • Frederic Chazal, David Cohen-Steiner, Quentin Merigot: Geometric Inference for Probability Measures, Technical Report CGL-TR-20 , October 2011.

    Abstract: We extend the framework of distance functions to compact sets for geometric inference to distance-like functions to probability measures.

  • Frederic Chazal, Daniel Chen, Leonidas Guibas, Xiaoye Jiang, Christian Sommer: Data-Driven Trajectory Smoothing, Technical Report CGL-TR-19 , October 2011.

    Abstract: Motivated by the increasing availability of large collections of noisy GPS traces, we present a new data-driven framework for smoothing trajectory data. Our approach makes use of the gradient of distance-like functions to embeddings of the data in higher dimensional spaces.

  • Claire Caillerie, Frederic Chazal, Jerome Dedecker, Bertrand Michel: Deconvolution for the Wasserstein metric and geometric inference, Technical Report CGL-TR-18 , October 2011.

    Abstract: We we consider a slight modification of the classical kernel deconvolution estimator, we give a consistency result and rates of convergence for this estimator and we applied our results to geometric inference problems.

  • Gerard Biau, Frederic Chazal, David Cohen-Steiner, Luc Devroye, Carlos Rodriguez: A Weighted k-Nearest Neighbor Density Estimate for Geometric Inference, Technical Report CGL-TR-17 , October 2011.

    Abstract: We introduce and study the convergence of a family density estimate built using distance-to-measure functions.

  • Jean-Daniel Boissonnat, Arijit Ghosh: Triangulating Smooth Submanifolds with Light Scaffolding, Technical Report CGL-TR-16 , October 2011.

    Abstract: We propose an algorithm to sample and mesh a submanifold of positive reach embedded in Rd.

  • Jean-Daniel Boissonnat, Arijit Ghosh: Manifold Reconstruction Using Tangential Delaunay Complexes, Technical Report CGL-TR-15 , October 2011.

    Abstract: We provide the first algorithm that can reconstruct a smooth submanifold with a complexity that depends only linearly on the ambient

  • Ioannis Emiris, Vissarion Fisikopoulos, Luis Penaranda: Optimizing the computation of sequences of determinantal predicates, Technical Report CGL-TR-14, October 2011.

    Abstract: We exploit the similarity between encountered matrices so as to optimize computation of a sequence of determinantal predicates, such as Orientation, inSphere, Volume. We develop a method that hashes intermediate computations, and implement it in the context of CGAL triangulations, obtaining a speedup of about 2 in computing silhouettes of the secondary polytope.

  • Christian L. Muller: Finding maximizing Euclidean TSP tours for the Hame-Hyytia-Hakula conjecture, Technical Report CGL-TR-13 , October 2011.

    Abstract: In this report we disprove the Hame-Hyytia-Hakula conjecture by enumerating a number of counterexamples. These instances have been identified using gradient-free variable-metric optimization methods

  • R. van de Weygaert, G. Vegter, P. Pranav, B. Jones, H. Edelsbrunner et al. : Alpha, Betti and the Megaparsec Universe: on the Homology and Topology of the Cosmic Web , Technical Report CGL-TR-12 , October 2011.

  • R. van de Weygaert, P. Pranav, B. Jones, G. Vegter, H. Edelsbrunner, M. Wintraecken et al. : Probing Dark Energy with Alpha Shapes and Betti Numbers , Technical Report CGL-TR-11 , October 2011.

  • Mathijs H.M.J. Wintraecken and Gert Vegter: On the Complexity of Polyhedral Approximations of Submanifolds of Euclidean Spaces , Technical Report CGL-TR-10 , October 2011.

  • Sebastian U. Stich, Christian L. Muller, and Bernd Gartner: Optimization of Convex Functions with Random Pursuit, Technical Report CGL-TR-09 , October 2011.

    Abstract: We consider unconstrained randomized optimization of convex objective functions. We analyze the Random Pursuit algorithm, which iteratively computes an approximate solution to the optimization problem by repeated optimization over a randomly chosen one-dimensional subspace. This randomized method only uses zeroth-order information about the objective function and does not need any problem-specific parametrization.

  • Ioannis Emiris, Vissarion Fisikopoulos, Christos Konaxis: An output-sensitive algorithm for computing projections of resultant polytopes, Technical Report CGL-TR-08, October 2011.

    Abstract: We design an incremental, output-sensitive algorithm to compute the Newton polytope of the resultant, or its orthogonal projection along a given direction. The resultant polytope is a Minkowski summand of the secondary polytope of a pointset. We develop a CGAL-based implementation, and show its efficiency in up to 7 or 8 dimensions.

  • Frederic Cazals, Christine Andrea Roth: Investigating the Energy Landscape of Macro-molecular Systems: Data Generation Software Overview, Technical Report CGL-TR-07 , October 2011.

    Abstract: Sampling the energy landscape of a macro-molecular system using molecular dynamics (MD) is a non trivial task due to the numerous parameters and steps involved in preparing the system of interest. In this report, we present three software tools (two python scripts and one C++ program) automating the generation of MD simulations and the calculation of normal modes.

  • Oren Salzman, Michael Hemmer, Barak Raveh, and Dan Halperin: Motion Planning via Manifold Samples, Technical Report CGL-TR-06 , October 2011.

    Abstract: We present a general and modular algorithmic framework for path planning of robots. Our framework combines geometric methods for exact and complete analysis of low-dimensional configuration spaces, together with sampling-based approaches that are appropriate for higher dimensions.
    http://acg.cs.tau.ac.il/projects/mms/project-page

  • Andreas von Dziegielewski and Michael Hemmer: High Quality Surface Mesh Generation for Swept Volumes, Technical Report CGL-TR-05 , October 2011.

    Abstract: We present a novel and efficient technique to generate a high quality mesh that approximates the outer boundary of a swept volume. See CGL-TR-45 for an updated and expanded version
    http://acg.cs.tau.ac.il/projects/swept-volume/project-page

  • Barak Raveh, Nir London, Lior Zimmerman and Ora Schueler-Furman: Rosetta FlexPepDock ab-initio: Simultaneous Folding, Docking and Refinement of Peptides onto Their Receptors, Technical Report CGL-TR-04 , October 2011.

    Abstract: We present Rosetta FlexPepDock? ab-initio, a protocol for simultaneous docking and de-novo folding of peptides, starting from an approximate specification of the peptide binding site.

  • Eric Berberich, Michael Kerber, Dan Halperin and Roza Pogalnikova: Deconstructing Approximate Offsets, Technical Report CGL-TR-03 , October 2011.

    Abstract: We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance epsilon in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius?
    http://acg.cs.tau.ac.il/projects/internal-projects/deconstructing-approximate-offsets/deconstructing-minkowski-sums-the-case-of-approximate-offsets

  • Christiane Lammersen, Melanie Schmidt, Christian Sohler: Probabilistic k-median, Technical Report CGL-TR-02, October 2011.

    Abstract: We develop the first coreset construction for probabilistic data.

  • Frederic Cazals, Frederic Chazal, Christiane Lammersen, Ioannis Z. Emiris, Bernd Gartner, Joachim Giesen, Charis Malamatos, Gunter Rote: Handling High-Dimensional Data, Technical Report No. CGL-TR-01, April 2011.

    Abstract: We give a survey and assessment of methods that are commonly used for dealing with high-dimensional data, mainly from the database community.

Theses (PhD and MSc)

  • PhD, Christine Andrea Roth, Investigating energy landscapes with applications to macro-molecular flexibility, INRIA - ABS. (Tentative defense schedule: Spring 2014)
  • PhD, Vissarion Fisikopoulos, Efficient computation of substructures of general-dimensional polytopes, NKUA (Tentative defense date: Spring 2014)
  • MSc, Christian Helbling, Extreme Points in Medium and High Dimensions, ETHZ, 2010
  • MSc, Philipp Lucas, Sclow Plots: Visualizing Empty Space, FSU 2013
  • MSc, Lars Kuehne, A Data-Driven Approach to Hue-Preserving Color-Blending, FSU 2012
  • MSc, Asaf Porat, Lines Tangent to Four Polytopes in three-dimensional space, TAU, 2012, MSc-Porat-2012.pdf
  • MSc, Roza Pogalnikova, Deconstruction of Approximate Offsets via Minkowski Sums, TAU, 2012, MSc-Pogalnikova-2012.pdf
  • MSc, Oren Salzman, Motion Planning via Manifold Samples, TAU, 2012, MSc-Salzman-2011.pdf
  • MSc, Clement Maria, Construction of witness complexes, MPRI, 2011
  • MSc, David de Laat, Upper Bounds on the Optimal Meshing Error of Manifolds in Higher Codimension, RUG, September 2011.
  • MSc, Alexandros Konstantinakis-Karmis, Implementing Approximate Voronoi Diagrams for Approximate NNS, NKUA 2012 MSc-Konstantinakis-2012.pdf.
  • MSc, Emmanouil Thanos-Filis, Exploiting the Structure of the Data in Approximate NNS, NKUA 2012, MSc-Thanos-2012.pdf.
  • MSc, Dimitri Nicolopoulos, Approximate nearest neighbors in high dimensions using randomized kd-trees, NKUA 2013.

Public Reports (Deliverables)

  • D1.4: Report on Software Prototypes ([[http://cgl.uni-jena.de/pub/Publications/WebHome/

    Publications

    Technical Reports

  • J. Giesen, L. Kühne. A parallel algorithm for computing the flow complex, [CGL-TR-89], November 2013

    We present a parallel algorithm and its implementation for computing the entire Hasse diagram of the flow complex of a point cloud in Euclidean space. Known algorithms for computing the flow complex in two and three dimensions compute the geometric realization of the flow complex and need to compute the Delaunay triangulation of the point cloud first. Our algorithm computes less information, namely only the Hasse diagram of the flow complex that is augmented with enough geometric information to allow the same topological multi-scale analysis of point cloud data as the alpha shape filtration without computing the Delaunay triangulation explicitly. We show experimental results for medium dimensions that demonstrate that our algorithm scales well with the number of available cores on a multicore architecture.

  • S. Stich, B. Gärtner. Random Pursuit in Hilbert Space, [CGL-TR-88], November 2013
    We define and analyze Random Pursuit (RP) -- a random walk in a Hilbert space. RP is defined by iterative projections onto randomly selected hyperplanes. This process originates from several applications in derivative-free optimization. In this report we study convergence in the induced norm. We present our results in a unifying way that allows to apply them in various settings. Especially, we recover the previously known convergence results from two applications.

  • C. Müller, S. Stich, B. Gärtner. Matrix-valued Iterative Random Projections, [CGL-TR-87], November 2013
    We analyze a matrix valued stochastic process with discrete time steps. The process originates from a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (D. Leventhal and A. S. Lewis., Optimization 60(3), 329--245, 2011). We do not only show convergence rates for summary statistics like trace and Frobenius norm but also study the expected convergence of the full eigenvalue spectrum.

  • J-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay triangulations of manifolds. [INRIA RR-8389,hal-00879133], [CGL-TR-86], October 2013
    We present an algorithmic framework for producing Delaunay triangulations of manifolds. The input to the algorithm is a set of sample points together with coordinate patches indexed by those points. The transition functions between nearby coordinate patches are required to be bi-Lipschitz with a constant close to 1. The primary novelty of the framework is that it can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. The output is a manifold simplicial complex that is the Delaunay complex of a perturbed set of points on the manifold. The guarantee of a manifold output complex demands no smoothness requirement on the transition functions, beyond the bi-Lipschitz constraint. In the smooth setting, when the transition functions are defined by common coordinate charts, such as the exponential map on a Riemannian manifold, the output manifold is homeomorphic to the original manifold, when the sampling is sufficiently dense.

  • J-D. Boissonnat, R. Dyer, A. Ghosh. The Stability of Delaunay Triangulations [INRIA RR-8276 , hal-00807050], [CGL-TR-85], April 2013
    This is a revised version of the first part of CGL-TR-25. We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of $\delta$-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged.

  • J-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay stability via perturbations [hal-00806107], [CGL-TR-84], March 2013
    We present an algorithm that takes as input a finite point set in Euclidean space, and performs a perturbation that guarantees that the Delaunay triangulation of the resulting perturbed point set has quantifiable stability with respect to the metric and the point positions. There is also a guarantee on the quality of the simplices: they cannot be too flat. The algorithm provides an alternative tool to the weighting or refinement methods to remove poorly shaped simplices in Delaunay triangulations of arbitrary dimension, but in addition it provides a guarantee of stability for the resulting triangulation.

  • J-D. Boissonnat, T. Dey, C. Maria. The Compressed Annotation Matrix: an Efficient Data Structure for Computing Persistent Cohomology,[CGL-TR-83], April 2013
    The persistent homology with coefficients in a field F coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substancially the amount of matrix operations. In addition, we propose heuristics to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology. Presented at ESA 2013.

  • F. Chazal, C. Labruère, M. Glisse, B. Michel, Optimal rates of convergence for persistence diagrams in topological Data Analysis, Arxiv 1394-1423, [CGL-TR-82], June 2013.
    Computational topology has recently seen an important development toward data analysis, giving birth to Topological Data Analysis. Persistent homology appears as a fundamental tool in this field. We show that the use of persistent homology can be naturally considered in general statistical frameworks. We establish convergence rates of persistence diagrams associated to data randomly sampled from any compact metric space to a well defined limit diagram encoding the topological features of the support of the measure from which the data have been sampled. Our approach relies on a recent and deep stability result for persistence that allows to relate our problem to support estimation problems (with respect to the Gromov-Hausdorff distance). Some numerical experiments are performed in various contexts to illustrate our results.

  • F. Chazal, J. Sun, Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure, Arxiv abs/1305.1172 [CGL-TR-81] , June 2013.

    In many real-world applications data appear to be sampled around 1-dimensional filamentary structures that can be seen as topological metric graphs. In this paper we address the metric reconstruction problem of such filamentary structures from data sampled around them. We prove that they can be approximated, with respect to the Gromov-Hausdorff distance by well-chosen Reeb graphs (and some of their variants) and we provide an efficient and easy to implement algorithm to compute such approximations in almost linear time. We illustrate the performances of our algorithm on a few data sets.

  • B. Gärtner, C. Müller, S. Stich. Variable Metric Random Pursuit: Experimental Validation, [CGL-TR-80], November 2013

    We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an approximate solution by repeated optimization over randomly chosen one-dimensional subspaces. The distribution of search directions is dictated by the chosen metric. Variable Metric RP uses novel variants of a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (D. Leventhal and A. S. Lewis., Optimization 60(3), 329--245, 2011). We here present (i) a refined analysis of the expected single step progress of RP algorithms and their global convergence on (strictly) convex functions and (ii) novel convergence bounds for V-RP on quadratic functions. We also quantify how well the employed metric needs to match the local geometry of the function in order for the RP algorithms to converge with the best possible rate on strongly convex functions. Our theoretical results are accompanied by extensive numerical experiments, comparing V-RP with the derivative-free schemes CMA-ES, Implicit Filtering, Nelder-Mead, NEWUOA, Pattern-Search and Nesterov's gradient-free algorithms.

  • Oren Salzman, Dan Halperin. Asymptotically near-optimal RRT for fast, high-quality, motion planning, [CGL-TR-79], November 2013.
    We present Lower Bound Tree-RRT (LBT-RRT), a single-query sampling-based algorithm that is asymptotically near-optimal. Namely, the solution extracted from LBT-RRT converges to a solution that is within an approximation factor of 1+epsilon of the optimal solution. Our algorithm allows for a continuous interpolation between the fast RRT algorithm and the asymptotically optimal RRT* and RRG algorithms. When the approximation factor is 1 (i.e., no approximation is allowed), LBT-RRT behaves like the RRT* algorithm. When the approximation factor is unbounded, LBT-RRT behaves like the RRT algorithm. In between, LBT-RRT is shown to produce paths that have higher quality than RRT would produce and run faster than RRT* would run. and a second, auxiliary tree, which we call the lower-bound tree. The combination of the two trees, which is faster to maintain than the tree maintained by RRT*, efficiently guarantee asymptotic near-optimality. We suggest to use LBT-RRT for high-quality, anytime motion planning. We demonstrate the performance of the algorithm for scenarios ranging from 3 to 12 degrees of freedom and show that even for small approximation factors, the algorithm produces high-quality solutions (comparable to RRT*) with little runtime overhead when compared to RRT.
    http://acg.cs.tau.ac.il/projects/LBT-RRT/project-page

  • I.Z. Emiris, D. Nicolopoulos. Randomized kd-trees for Approximate Nearest Neighbor Search, [CGL-TR-78.pdf], November 2013.

    We implement Randomized kd-trees in CGAL for approximate Nearest-Neighbor Search, based on the corresponding algorithms of the FLANN library. The input points are preprocessed into several tree data structures by modifying standard kd-trees: the trees adapt to the pointset by assigning higher probability in splitting along coordinates of high variance. The feature extends the 4.3 CGAL dD Spatial Searching functionality and introduces a new splitting rule extending the Splitter base class. It supports k nearest point searching. Our Randomized kd-trees are competitive to the FLANN implementation, and faster than CGAL kd-trees for high dimensions; we show tests in dimension 128.

  • I.Z. Emiris, I. Psarros, K. Chanseau Saint-Germain. Approximate Nearest Neighbor Search for Points on Lower-dimensional Flats, [CGL-TR-77.pdf], November 2013.

    In order to improve efficiency in Approximate Nearest Neighbor search, we exploit the structure of the input data by considering points that are distributed almost uniformly on flats of varying, lower dimension, where these flats are distributed uniformly within a bounding sphere. We exploit an existing mapping that transforms the (approximate) Nearest Flat search to a (approximate) Nearest point search; however there is an additive error as well when queries lie very close to flats. We achieve expected query time logarithmic in the number of flats when the ambient space dimension is fixed; this is squared when bounding complexity with high probability under mild assumptions. This work extends [CGL-TR-29, Sect.3] which considered collinear points. We also introduce a CGAL-based implementation and corroborate our theoretical results with experimental evidence. Our software is faster than CGAL kd-trees: e.g. for 5K points in 55 dimensions, or 30K points in 20 dimensions, with both sets lying on 2-dimensional flats, our code is about 5 times faster.

  • I.Z. Emiris, V. Fisikopoulos. Algorithms for volume approximation of convex bodies, [CGL-TR-76], November 2013.

    We survey results on the fundamental problem of computing the volume of d-dimensional convex bodies, with emphasis on randomized poly-time approximation algorithms for bodies represented by a membership oracle. We implement and experimentally study efficient algorithms for approximating the volume of polytopes given as an intersection of halfspaces, by developing efficient hit-and-run methods. Our emphasis is to exploit the geometry of the problem so as to improve runtime (or accuracy) for general dimensional polytopes. Our method handles skinny polytopes by applying appropriate rounding based on computing the minimum enclosing ellipsoid of a point sample. Our publicly available C++ software handles polytopes in dimensions substantially larger than exact volume computation software can do, e.g., it approximates the volume of d-dimensional cubes with at least 3 correct digits, for d up to 100, in about 20 min, whereas VINCI does not seem able to handle d-cubes for $d>20$. Our code also produces the best known approximations to the volume of Birkhoff polytopes of order beyond 10 within 4 hours; up to order 10, their volume has been exactly computed by specialized parallel software in a sequential time of years. Furthermore, uniform sampling
    is of independent interest in several machine learning applications such as sampling contingency tables and learning the p-value.

  • I.Z. Emiris, V. Fisikopoulos, B. Gärtner . Efficient edge skeleton computation for polytopes defined by oracles, [CGL-TR-75], November 2013.

    In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. whose complexity depends polynomially in the input and output sizes. It is thus important to identify polytope constructions for which total poly-time algorithms can be obtained. We offer the first total poly-time algorithm for computing the edge-skeleton (including vertex enumeration) of a polytope given by an optimization (aka LP) or a separation oracle, where we are also given a superset of its edge directions. All complexity bounds refer to the (oracle) Turing machine model. We also offer a workspace efficient variant of our algorithm by employing reverse search. We consider two main applications, where we obtain (weakly) total poly-time algorithms: Signed Minkowski sums of convex polytopes, where polytopes can be subtracted provided the signed sum is a convex polytope, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming, where we offer an alternative approach removing the exponential dependence on the dimension in the complexity.

  • I.Z. Emiris, V. Fisikopoulos, L. Penaranda. High Dimensional Predicates: Update on Algorithms and Software, [CGL-TR-74], November 2013.

    Determinant predicates are the core procedures in many important geometric algorithms and become the bottleneck as the dimension of computation space grows. We study the sequences of determinants that appear in geometric algorithms so as to speed-up each predicate by using information from previously computed ones. In our technical report of October 2012 [CGL-TR-27] we proposed, implemented and experimentally evaluated algorithms for determinants in incremental convex hull and point location; we also presented an extended version of hashing determinants for a sequence of convex hull operations, and a CGAL submission of its implementation. In this report, we present an update on this work by proposing a dynamic determinant method for the gift wrapping convex hull algorithm, we present experiments on convex hulls for a real practical scenario, and give an update on our CGAL submission.
  • E. Ehsanfar, D. Feldman, C. Sohler. Orthogonal Range Clustering, [ CGL-TR-73.pdf], November 2013

    In this report, we explain the general idea and the notation of a fast technique that lead an approximation for orthogonal range clustering using coreset constructions. Given a range space (X, R) and a set P in X of n points in d-space, the goal of orthogonal range clustering is to find a k-clustering C of the points within any arbitrary range Q in R. For computing an approximation for C, we construct a weighted summary S of the points within Q by preprocess the points into a datastructure. We then show that the cost of clustering based on the summary has only a tinny different with the cost of the clustering for the original point set. For yielding summary S in a canonical approach, we modify the datastructure by small coreset constructions namely coreset plugins. Then for any range query Q, we analyze the process to compute an approximate clustering using this modified datastructure.

  • B. Gärtner, C. Helbling, Y. Ota, T. Takahashi. Large Shadows from Sparse Inequalities, [CGL-TR-72], November 2013

    The d-dimensional Goldfarb cube is a polytope with the property that all its 2d vertices appear on some shadow of it (projection onto a 2-dimensional plane). The Goldfarb cube is the solution set of a system of 2d linear inequalities with at most 3 variables per inequality. We show in this paper that the d-dimensional Klee-Minty cube — constructed from inequalities with at most 2 variables per inequality — also has a shadow with 2d vertices. In contrast, with one variable per inequality, the size of the shadow is bounded by 2d.

  • H. Tyagi, B. Gärtner. Continuum armed bandit problem of few variables in high dimensions, [CGL-TR-71], November 2013

    We consider the stochastic and adversarial settings of continuum armed bandits where the arms are indexed by [0,1]^d. The reward functions r:[0,1]^d -> R are assumed to intrinsically depend on at most k coordinate variables implying r(x_1,..,x_d) = g(x_{i_1},..,x_{i_k}) for distinct and unknown i_1,..,i_k from {1,..,d} and some locally Holder continuous g:[0,1]^k -> R with exponent 0 < alpha <= 1. Firstly, assuming (i_1,..,i_k) to be fixed across time, we propose a simple modification of the CAB1 algorithm where we construct the discrete set of sampling points to obtain a bound of O(n^((alpha+k)/(2*alpha+k)) (log n)^((alpha)/(2*alpha+k)) C(k,d)) on the regret, with C(k,d) depending at most polynomially in k and sub-logarithmically in d. The construction is based on creating partitions of {1,..,d} into k disjoint subsets and is probabilistic, hence our result holds with high probability. Secondly we extend our results to also handle the more general case where (i_1,...,i_k) can change over time and derive regret bounds for the same.

  • D. Feldman, A. Munteanu, C. Sohler. Smallest enclosing ball for probabilistic data, [CGL-TR-70], November 2013

    We deal with the smallest enclosing ball problem subject to probabilistic data. In our setting, any of n points may not or may occur at one of finitely many locations, following its own discrete probability distribution. The objective is therefore considered to be a random variable and we aim at finding a center minimizing the expected maximum distance to the points according to their distributions. Our main contribution presented in this report is to develop the first (1+ε)-approximation algorithm for the probabilistic smallest enclosing ball problem with extensions to the streaming setting.

  • H. Fichtenberger, M. Schmidt. PROBI: A Heuristic for the probabilistic $k$-median problem, [CGL-TR-69], November 2013

    We develop the heuristic PROBI for the probabilistic Euclidean k-median problem based on a coreset construction in [CGL-TR-02]. Our algorithm computes a summary of the data and then uses an adapted version of k-means++ by Arthur and Vassilvitskii to compute a good solution on
    the summary. The summary is maintained in a data stream, so PROBI can be used in a data stream setting on very large data sets.
    We experimentally evaluate the quality of the summary and of the computed solution and compare the running time to state of the art data stream clustering algorithms.

  • D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier. Homological Reconstruction and Simplification in R³, [CGL-TR-68], November 2013

    We consider the problem of deciding whether the persistent homology group of a simplicial pair (K, L) can be realized as the homology H∗(X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R³.
    As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S³ within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.

  • J. Giesen, L. Kühne, S. Laue. Sketching the Support of a Probability Measure, [CGL-TR 67], November 2013

    We want to sketch the support of a probability measure on Euclidean space from samples that have been drawn from the measure. This problem is closely related to certain manifold learning problems, where one assumes that the sample points are drawn from a manifold that is embedded in Euclidean space. Here we propose to sketch the support of the probability measure (that does not need to be a manifold) by some gradient flow complex, or more precisely by its Hasse diagram. The gradient flow is defined with respect to the distance function to the sample points. We prove that a gradient flow complex (that can be computed) is homotopy equivalent to the support of the measure for sufficiently dense samplings, and demonstrate the feasibility of our approach on real world data sets.

  • J. Giesen, S. Laue, J. Mueller. Compressing Support Vector Machines, [CGL-TR 66], November 2013

    A support vector machine is an optimization problem that takes as input n feature vectors of length m. Hence, to store the input memory of size O(nm) is needed. We show how to construct another support vector machine whose input are n feature vectors of total size only O(n log n) that are derived from the original feature vectors by a random projection. Here, we do not assume that the data matrix is sparse or of low rank. Instead, we rely on the weaker assumption that the solution is sparse. We also provide an algorithm for recovering an approximate solution to the original problem from an optimal solution to the compressed problem, where the approximation factor depends on the compression ratio. The original feature vectors can be streamed from secondary memory, e.g., from tape or hard drive, to fast main
    memory and compressed on the fly into the new feature vectors. With this compression scheme the memory requirement for the support vector machine can be reduced from O(nm) to O (n + m) log n . Reducing the memory requirement becomes beneficial when the original feature vectors do not fit into main memory. In this case state-of-the-art iterative solvers need to access the slower secondary memory repeatedly, which can be avoided if the compressed feature vectors fit into main memory.

  • M. Buchet, F. Chazal, S. Oudot, and D. Sheehy. Efficient and Robust Persistent Homology for Measures, CGL-TR-65, November 2013.

    We extend the notion of the distance to a measure from Euclidean space to probability measures on general metric spaces as a way to do topological data analysis in a way that is robust to noise and outliers. We then give an efficient way to approximate the sublevel sets of this function by a union of metric balls and extend previous results on sparse Rips filtrations to this setting. This robust and efficient approach to topological data analysis is illustrated with several examples from an implementation.

  • G. Miller and D. Sheehy. A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations, [CGL-TR 64], November 2013.

    We describe a new algorithm for computing the Voronoi diagram of a set of n points in constant-dimensional Euclidean space. The running time of our algorithm is O( f log n log s) where f is the output complexity of the Voronoi diagram and s is the spread of the input, the ratio of largest to smallest pairwise distances. Despite the simplicity of the algorithm and its analysis, it improves on the state of the art for all inputs with polynomial spread and near-linear output size. The key idea is to first build the Voronoi diagram of a superset of the input points using ideas from Voronoi refinement mesh generation. Then, the extra points are removed in a straightforward way that allows the total work to be bounded in terms of the output complexity, yielding the output sensitive bound. The removal only involves local flips and is inspired by kinetic data structures.

  • S. Oudot and D. Sheehy. Zigzag Zoology: Rips-like zigzags for Homology Inference, [CGL-TR 63], November 2013.

    For points sampled near a compact set X, the persistence barcode of the Rips filtration built from the sample contains information about the homology of X as long as X satisfies some geometric assumptions. The Rips filtration is prohibitively large, however zigzag persistence can be used to keep the size linear. We present several species of Rips-like zigzags and compare them with respect to the signal-to-noise ratio, a measure of how well the underlying homology is represented in the persistence barcode relative to the noise in the barcode at the relevant scales. Some of these Rips-like zigzags have been available as part of the Dionysus library for several years while others are new. Interestingly, we show that some species of Rips zigzags will exhibit less noise than the (non-zigzag) Rips filtration itself. Thus, Rips zigzags can offer improvements in both size complexity and signal-to-noise ratio.

    Along the way, we develop new techniques for manipulating and comparing persistence barcodes from zigzag modules. We give methods for reversing arrows and removing spaces from a zigzag while controlling the changes occurring in its barcode. We also discuss factoring zigzags and a kind of interleaving of two zigzags that allows their barcodes to be compared. These techniques were developed to provide our theoretical analysis of the signal-to-noise ratio of Rips-like zigzags, but they are of independent interest as they apply to zigzag modules generally.

  • G. Miller, D. Sheehy, and A. Velingker. A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs, [CGL-TR 62], November 2013.

    We present a new algorithm that produces the 1-dimensional skeleton of a Delaunay mesh for point sets in any dimension with guaranteed optimal mesh size and quality. Our comparison based algorithm runs in time O(2^{O( d)}(n log n + m)), where n is the input size, m is the output point set size, and d is the ambient dimension. The constants only depend the desired element quality bounds. To gain this new efficiency the algorithm only maintains the neighbors of each point in the mesh. Thus if one only wants the neighbors structure of a reduced mesh then the algorithm will return with a size O(2^{O( d)}( n)) graph in O(2^{O( d)}(n log n)) time.

  • D. Sheehy. Geometric Separators and the Parabolic Lift, [CGL-TR 61], November 2013.

    A geometric separator for a set U of n geometric objects (usually balls) is a small (sublinear in n) subset whose removal disconnects the intersection graph of U into roughly equal sized parts. These separators provide a natural way to do divide and conquer in geometric settings. A particularly nice geometric separator algorithm originally introduced by Miller and Thurston has three steps: compute a centerpoint in a space of one dimension higher than the input, compute a conformal transformation that ``centers'' the centerpoint, and finally, use the computed transformation to sample a sphere in the original space. The output separator is the subset of S intersecting this sphere. It is both simple and elegant. We show that a change of perspective (literally) can make this algorithm even simpler by eliminating the entire middle step. By computing the centerpoint of the points lifted onto a paraboloid rather than using the stereographic map as in the original method, one can sample the desired sphere directly, without computing the conformal transformation.

  • Ramsay Dyer, Gert Vegter, and Mathijs Wintraecken, Intrinsic simplices in Riemannian manifolds, [CGL-TR-60], October 2013.

    We study a natural definition of geometric simplices in Riemannian manifolds of arbitrary dimension n. Given a finite set of vertices in a convex neighbourhood on the manifold, these geometric simplices are defined using Karcher means: the minimum of the function on M given by the weighted sum of squared distances to the vertices. The weights are the barycentric coordinates. In this way the barycentric coordinates of the standard Euclidean simplex are mapped smoothly to the manifold. Our contribution is to articlulate conditions that guarantee that this map is a smooth embedding. If it is not, we say the Riemannian simplex is degenerate. Quality measures for the ``thickness'' or ``fatness'' of Euclidean simplices can be adapted to apply to these Riemannian simplices. For manifolds of dimension 2, the simplex is non-degenerate if it has a positive quality measure, as in the Euclidean case. However when the dimension is greater than two, non-degeneracy can be guaranteed only when the quality exceeds a positive bound that depends on the size of the simplex and local bounds on the sectonal curvatures. This result provides a general tool and represents a step towards specific sampling conditions for triangulating manifolds.
  • Philipp Lucas, Lars Kühne, Joachim Giesen, Sclow Plots: Visualizing Empty Space [CGL-TR-59], October 2013

    Scatter plots are mostly used for correlation analysis, but are also a useful tool for understanding the distribution of high-dimensional point cloud data. An important characteristic of such distributions are clusters, and scatter plots have been used successfully to identify clusters in data. Another characteristic of point cloud data that has received less attention so far are regions that contain no or only very few data points. We show that augmenting scatter plots by projections of flow lines along the gradient vector field of the distance function to the point cloud reveals such empty regions or voids. The augmented scatter plots, that we call sclow plots, enable a much better understanding of the geometry underlying the point cloud than traditional scatter plots. We demonstrate the feasibility of our approach on synthetic and real world data sets.
  • F. Cazals and T. Dreyfus and S. Sachdeva and N. Shah, Greedy Geometric Algorithms for Collection of Balls with Applications to Geometric Approximation and Molecular Coarse-Graining,[CGL-TR-58], September 2013.
    Choosing balls which best approximate a 3D object is a non trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object O defined by a union of n balls with k<n balls defining a region S subset of O. This solution is further used to construct an outer approximation enclosing the initial shape, and an interpolated approximation sandwiched between the inner and outer approximations. The inner approximation problem is reduced to a geometric generalization of weighted max k-cover, solved with the greedy strategy which achieves the classical 1-1/e lower bound. The outer approximation is reduced to exploiting the partition of the boundary of O by the Apollonius Voronoi diagram of the balls defining the inner approximation. Implementation-wise, we present robust software incorporating the calculation of the exact Delaunay triangulation of points with degree two algebraic coordinates, of the exact medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. Application-wise, we exhibit accurate coarse-grain molecular models using a number of balls 20 times smaller than the number of atoms, a key requirement to simulate crowded cellular environments.
  • F. Cazals and J. Qin and A. Roth, Refined Analysis of Transitions on RNA Landscapes, CGL-TR-57, September 2013. Energy landscape of RNA molecules are instrumental to predict the stable secondary structures, and the folding intermediates yielding them. In particular, transition analysis carried out so far for two neighboring conformations corresponding to local minima are based on the notion of saddle height, namely the lowest energy of a saddle found on paths joining these two conformations. However, a route through a saddle realizing the saddle height may not be favored if it features high energy gradients.In this work, we therefore explore a broader class of transitions. First, given a Boltzmann sampling of a RNA landscape, possibly non connected, we develop an algorithm to connect it, based on two ingredients, namely an algorithm reporting nearest neighbors in a (non Euclidean) metric space, and an iterative strategy a-la Kruskal to bridge the gaps between the connected components of the initial sampling. Second, we apply our construction of sampled based Morse-Smale diagram to analyze the connected landscape, reporting in particular a broader class of index one saddles than those found in previous work. Using the connexions between local minima and these index one saddle, we enumerate a broader class of transition paths, and exhibit in particular paths reaching elevation higher than the saddle height, yet, with more moderate energy gradient.

  • F. Cazals and C. Mueller and C. Robert and A. Roth, Towards Morse theory for point cloud data, CGL-TR-56, September 2013.
    Morse theory provides a powerful framework to study the topology of a manifold from a function defined on it, but discrete constructions have remained elusive due to the difficulty of translating smooth concepts to the discrete setting. Consider the problem of approximating the Morse-Smale (MS) complex of a Morse function from a point cloud and an associated nearest neighbor graph (NNG). While following the constructive proof of the Morse homology theorem, we present novel concepts for critical points of any index, and the associated Morse-Smale diagram. Our framework has three key advantages. First, it requires elementary data structures and operations, and is thus suitable for high-dimensional data processing. Second, it is gradient free, which makes it suitable to investigate functions whose gradient is unknown or expensive to compute. Third, in case of under-sampling and even if the exact (unknown) MS diagram is not found, the output conveys information in terms of ambiguous flow, and the Morse theoretical version of topological persistence, which consists in canceling critical points by flow reversal, applies. On the experimental side, we present a comprehensive analysis of a large panel of bi-variate and tri-variate Morse functions whose Morse-Smale diagrams are known perfectly, and show that these diagrams are recovered perfectly. In a broader perspective, we see our framework as a first step to study complex dynamical systems from mere samplings consisting of point clouds.
  • K. Solovey, O. Salzman, and D. Halperin. Discrete RRT for Exploration of Implicit Roadmaps in Multi-Robot Motion Planning [CGL-TR-55], October 2013

    We present a sampling-based framework for multi-robot motion planning which incorporates an implicit representation of a roadmap with a novel approach for pathfinding in geometrically embedded graphs. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaption of the celebrated RRT algorithm, for the discrete case of a graph. By rapidly exploring the high-dimensional configuration space represented by the implicit roadmap, dRRT is able to reach subproblems where minimal coordination between the robots is required. Integrating the implicit representation of the roadmap, the dRRT algorithm, and techniques that are tailored for such subproblems on the implicit roadmap allows us to solve multi-robot problems while exploring only a small portion of the configuration space. We demonstrate our approach experimentally on scenarios of up to 48 degrees of freedom where our algorithm is faster by a factor of at least ten when compared to existing algorithms that we are aware of.
    http://acg.cs.tau.ac.il/projects/drrt/drrt
  • Efi Fogel and Dan Halperin, Polyhedral Assembly Partitioning with Infinite Translations or The Importance of Being Exact [CGL-TR-54], September 2013

    Assembly partitioning with an infinite translation is the application of an infinite translation to partition an assembled product into two complementing subsets of parts, referred to as a subassemblies, each treated as a rigid body. We present an exact implementation of an efficient algorithm, based on the general framework designed by Halperin, Latombe, and Wilson, to obtain such a motion and subassemblies given an assembly of polyhedra in R3. We do not assume general position.
    Namely, we can handle degenerate input, and we produce exact results. As often occurs, motions that partition a given assembly or subassembly might be isolated in the infinite space of motions. Any perturbation of the input or of intermediate results, caused by, for example, imprecision, might result with dismissal of valid partitioning-motions. In the extreme case where there is only a finite number of valid partitioning-motions, as occurs in the assembly shown to the right, no motion may be found, even though such exists. Proper handling requires significant enhancements applied to the original algorithmic framework.
    The implementation is based on software components that have been developed and introduced only recently. They paved the way to a complete, efficient, and elegant implementation. Additional information about some of these components is available at Arrangement of Geodesic Arcs on a Sphere.
    http://acg.cs.tau.ac.il/projects/internal-projects/assembly-partitioning/project-page

  • D.Atariah, S. Ghosh, G. Rote, On the Parameterization and the Geometry of the Configuration Space of a Single Planar Robot, [CGL-TR 53], August 2013

    Abstract: Translating and rotating planar polygonal robots are studied in the literature for decades. An integral part of this study is the configuration space which corresponds to the work space. In the context of motion planning problems, the boundary between the free and forbidden parts of the configuration space plays a major role. In this report we find an explicit parameterization of the boundary of the forbidden space. Using this parameterization we detail several geometrical properties of the various elements which constitute this boundary. In addition, this parameterization enables us to visualize these elements.
    This entry contains both a conference paper and the extended technical report.

  • D.Atariah, G. Rote, Configuration Space Visualization, [CGL-TR 52], December 2012

    Abstract: Based on a simple parameterization of contact surfaces, we visualize both the workspace and the corresponding config- uration space of a planar polygonal robot that moves amid planar polygonal obstacles.
  • F. Cazals, E. Ehsanfar, D. Halperin, R. van de Weijgaert, Report on Heterogeneous and Missing Data, Technical report [CGL-TR 51], October 2012


    Abstract: We give a survey of the main approaches that are commonly used for dealing with missing and heterogeneous data in different geometric contexts.

  • L. Kühne, J. Giesen, Z. Zhang, S. Ha, K. Mueller, A Data-Driven Approach to Hue-Preserving Color-Blending, Technical report [CGL-TR 50] , October 2012

    Abstract: Color mapping and semitransparent layering play an important role in many visualization scenarios, such as information visualization and volume rendering. The combination of color and transparency is still dominated by standard alpha-compositing using the Porter-Duff over operator which can result in false colors with deceiving impact on the visualization. Other more advanced methods have also been proposed, but the problem is still far from being solved. Here we present an alternative to these existing methods specifically devised to avoid false colors and preserve visual depth ordering. Our approach is data driven and follows the recently formulated knowledge-assisted visualization (KAV) paradigm. Preference data, that have been gathered in web-based user surveys, are used to train a support-vector machine model for automatically predicting an optimized hue-preserving blending. We have applied the resulting model to both volume rendering and a specific information visualization technique, illustrative parallel coordinate plots. Comparative renderings show a significant improvement over previous approaches in the sense that false colors are completely removed and important properties such as depth ordering and blending vividness are better preserved. Due to the generality of the defined data-driven blending operator, it can be easily integrated also into other visualization frameworks.

  • J. Giesen, Sören Laue, J. Mueller, Basis Expansions for Support Vector Machines, Technical report [CGL-TR 49] , October 2012

    Abstract: Recently, it has been pointed out by Chapelle that there is no reason not to consider training Support Vector Machines (SVMs) in the primal, although training SVMs is still almost exclusively introduced using the dual formulation. Here we explore the use of kernels in the primal formulation of SVMs on some set $\Omega$. Working in the primal shifts the focus from kernels on $\Omega$ to orthonormal bases of Hilbert spaces of functions on $\Omega$. Such basis functions can be derived from a kernel on $\Omega$, but in general the basis function view offers more flexibility. We discuss two examples of this added flexibility, namely non-uniformity and incremental construction of basis functions.

  • A. Bansal, F. Cazals, N. Malod-Dognin, Characterizing the Morphology of Protein Binding Patches, Technical report [CGL-TR 48] , October 2012

    Abstract: Let the patch of a partner in a protein complex be the collection of atoms accounting for the interaction. To improve our understanding of the structure-function relationship, we present a patch model decoupling the topological and geometric properties. While the geometry is classically encoded by the atomic positions, the topology is recorded in a graph encoding the relative position of concentric shells partitioning the interface atoms. The topological - geometric duality provides the basis of a generic dynamic programming based algorithm comparing patches at the shell level, which may favor topological or geometric features. On the biological side, we address four questions, using 249 co-crystallized heterodimers organized in biological families: (i) we dissect geometric versus topological properties of patches (ii) we show that our encoding is effective to carry out atomic resolution comparison of patches (iii) we use our comparison algorithms to infer specificity related information amidst a database of complexes (iv) we exhibit a descriptor outperforming its contenders to predict the binding affinities of the affinity benchmark, a key problem for the analysis of transitions on energy landscapes.

  • Y. Brise and B. Gaertner, Convergence Rate of the DIRECT Algorithm, Technical Report [CGL-TR 47], October 2012

    Abstract: The {DIRECT} algorithm is a deterministic sampling method for Lipschitz continuous function optimization. We give the first quantitative analysis of the convergence rate of DIRECT. We show that, in $\mathbb{R}^d$, $O(d^{2d+2} \frac{1}{\epsilon^{2d}})$ function evaluations are sufficient to guarantee an absolute error in function value not larger than $\epsilon$. Dropping Lipschitz continuity the same bound applies to the sampling distance from the location of the global minimum, with an even better hidden constant.

  • S. Stich and C. Mueller, On spectral invariance of Randomized Hessian and Covariance Matrix Adaptation schemes, Technical Report [CGL-TR 46], October 2012

    Abstract: We evaluate the performance of several gradient-free variable-metric continuous optimization schemes on a specific set of quadratic functions. We revisit a randomized Hessian approximation scheme (D. Leventhal and A. S. Lewis. Randomized Hessian estimation and directional search, 2011), discuss its theoretical underpinnings, and introduce a novel, numerically stable implementation of the scheme (RH). For comparison we also consider closely related Covariance Matrix Adaptation (CMA) schemes. A key goal of this study is to elucidate the influence of the distribution of eigenvalues of quadratic functions on the convergence properties of the different variable-metric schemes. For this purpose we introduce a class of quadratic functions with parameterizable spectra.

  • A. v. Dziegielewski, M. Hemmer and E. Schoemer, High Quality Conservative Surface Mesh Generation for Swept Volumes, Technical Report [CGL-TR 45], October 2012

    Abstract: We present a novel, efficient and flexible scheme to generate a high quality mesh that approximates the outer boundary of a swept volume. This is an updated and expanded version of Technical Report [CGL-TR-05].
    http://acg.cs.tau.ac.il/projects/swept-volume/project-page

  • S. Stich and C. Mueller and B. Gaertner, Variable Metric Random Pursuit, Technical Report CGL-TR-44.pdf, October 2012.

    Abstract: We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an approximate solution by repeated optimization over randomly chosen one-dimensional subspaces. The distribution of search directions is dictated by the chosen metric. Variable Metric RP uses novel variants of a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (D. Leventhal and A. S. Lewis., Optimization 60(3), 329--245, 2011). We here present (i) a refined analysis of the expected single step progress of RP algorithms and their global convergence on (strictly) convex functions and (ii) novel convergence bounds for V-RP on convex quadratic functions. We also quantify how well the employed metric needs to match the local geometry of the function in order for the RP algorithms to converge with the best possible rate on strongly convex functions. Our theoretical results are accompanied by illustrative experiments on Nesterov's worst case function and quadratic functions with (inverse) sigmoidal eigenvalue distributions.

  • G. Vegter and M.H.M.J.Wintraecken, A conceptual take on invariants of low-dimensional manifolds found by integration, Technical Report CGL-TR-43.pdf, October 2012.

    Abstract: An elementary proof of the fact that the Euler characteristic is the only topological invariant of a surface that can be found by integration (using Gauss-Bonnet) is given. A similar method is also applied to three dimensional manifolds.

  • G. Vegter and M.H.M.J.Wintraecken, On the extrinsic nature of triangulations, Technical Report CGL-TR-42.pdf , October 2012.

    Abstract: The extrinsic nature of the complexity of triangulations and more generally approximations in higher codimension is exhibited.

  • D. Shaharabani, O. Salzman, P. K. Agarwal and D. Halperin, Sparsification of Motion-Planning Roadmaps by Edge Contraction, (arXiv:1209.4463), Technical Report [CGL-TR-41], October 2012

    Abstract: We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction—the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.
    http://acg.cs.tau.ac.il/projects/rsec/project-page

  • O. Salzman, M. Hemmer and Dan Halperin, On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages, (arXiv:1202.5249), Technical Report [CGL-TR 40] , October 2012

    Abstract: We extend our study of Motion Planning via Manifold Samples (MMS), a general algorithmic framework that combines geometric methods for the exact and complete analysis of low-dimensional configuration spaces with sampling-based approaches that are appropriate for higher dimensions. The framework explores the configuration space by taking samples that are entire low-dimensional manifolds of the configuration space capturing its connectivity much better than isolated point samples. The contributions of this paper are as follows: (i) We present a recursive application of MMS in a six-dimensional configuration space, enabling the coordination of two polygonal robots translating and rotating amidst polygonal obstacles. In the adduced experiments for the more demanding test cases MMS clearly outperforms PRM, with over 20-fold speedup in a coordination-tight setting. (ii) A probabilistic completeness proof for the most prevalent case, namely MMS with samples that are affine subspaces. (iii) A closer examination of the test cases reveals that MMS has, in comparison to standard sampling-based algorithms, a significant advantage in scenarios containing high-dimensional narrow passages. This provokes a novel characterization of narrow passages which attempts to capture their dimensionality, an attribute that had been (to a large extent) unattended in previous definitions.
    http://acg.cs.tau.ac.il/projects/mms/project-page

  • K. Solovey and D. Halperin, k-Color Multi-Robot Motion Planning, (arXiv:1202.6174), Technical Report [CGL-TR-39], October 2012

    Abstract: We present a simple and natural extension of the multi-robot motion planning problem where the robots are partitioned into groups (colors), such that in each group the robots are interchangeable. Every robot is no longer required to move to a specific target, but rather to some target placement that is assigned to its group. We call this problem k-color multi-robot motion planning and provide a sampling-based algorithm specifically designed for solving it. At the heart of the algorithm is a novel technique where the k-color problem is reduced to several discrete multi-robot motion planning problems. These reductions amplify basic samples into massive collections of free placements and paths for the robots. We demonstrate the performance of the algorithm by an implementation for the case of disc robots in the plane and show that it successfully and efficiently copes with a variety of challenging scenarios, involving many robots, while a simplified version of this algorithm, that can be viewed as an extension of a prevalent sampling-based algorithm for the k-color case, fails even on simple scenarios. Interestingly, our algorithm outperforms a state-of-the-art implementation for the standard multi-robot problem, in which each robot has a distinct color.
    http://acg.cs.tau.ac.il/projects/kcolor/k-color-multi-robot-motion-planning

  • E. Fogel, M. Hemmer, A.Porat and D. Halperin, Lines Through Segments in 3D Space, Technical Report [CGL-TR-38], October 2012

    Abstract: Given a set S of n line segments in three-dimensional space, finding all the lines that simultaneously intersect at least four line segments in S is a fundamental problem that arises in a variety of domains. We refer to this problem as the lines-through-segments problem, or LTS for short. We present an efficient output-sensitive algorithm and its implementation to solve the LTS problem. The implementation is exact and properly handles all degenerate cases. To the best of our knowledge, this is the first algorithm (and implementation) for the LTS problem that is (i) output sensitive and (ii) handles all degenerate cases. The algorithm runs in O((n^3 + I)log n) time, where I is the output size, and requires O(n log n + J) working space, where J is the maximum number of output elements that intersect two fixed line segments; I and J are bounded by O(n^4) and O(n^2), respectively. We use CGAL arrangements and in particular its support for two-dimensional arrangements in the plane and on the sphere in our implementation. The efficiency of our implementation stems in part from careful crafting of the algebraic tools needed in the computation. We also report on the performance of our algorithm and its implementation compared to others.
    http://acg.cs.tau.ac.il/projects/lts/project-page

  • M. Hemmer, M. Kleinbort and D. Halperin, Improved Implementation of Point Location in General Two-Dimensional Subdivisions, (arXiv:1205.5434), Technical Report [CGL-TR-37] , October 2012

    Abstract: We present a major revamp of the point-location data structure for general two-dimensional subdivisions via randomized incremental construction, implemented in CGAL, the Computational Geometry Algorithms Library. We can now guarantee that the constructed directed acyclic graph G is of linear size and provides logarithmic query time. Via the construction of the Voronoi diagram for a given point set S of size n, this also enables nearest-neighbor queries in guaranteed O(log n) time. Another major innovation is the support of general unbounded subdivisions as well as subdivisions of two-dimensional parametric surfaces such as spheres, tori, cylinders. The implementation is exact, complete, and general, i.e., it can also handle non-linear subdivisions. Like the previous version, the data structure supports modifications of the subdivision, such as insertions and deletions of edges, after the initial preprocessing. A major challenge is to retain the expected O(n log n) preprocessing time while providing the above (deterministic) space and query-time guarantees. We describe an efficient preprocessing algorithm, which explicitly verifies the length L of the longest query path in O(n log n) time. However, instead of using L, our implementation is based on the depth D of G. Although we prove that the worst case ratio of D and L is Theta(n/log n), we conjecture, based on our experimental results, that this solution achieves expected O(n log n) preprocessing time.
    http://acg.cs.tau.ac.il/projects/lppl/guaranteed-logarithmic-planar-point-location

  • F. Chazal, V. de Silva, S. Oudot, Persistence Stability for Geometric complexes, ( arXiv:1207.3885), Technical Report [CGL-TR-36] , October 2012.

    Abstract: In this paper we study the properties of the homology of different geometric filtered complexes (such as Cech, Vietoris-Rips and witness complexes) built on top of precompact spaces. Using recent developments in the theory of topological persistence we provide simple and natural proofs of the stability of the persistent homology of such complexes with respect to the Gromov--Hausdorff distance. We also exhibit a few noteworthy properties of the homology of the Rips and Cech complexes built on top of compact spaces.

  • F. Chazal, V. de Silva, M. Glisse, S. Oudot, The Structure and Stability of Persistence Modules, ( arXiv:1207.3674), Technical Report [CGL-TR-35] , October 2012.

    Abstract: We give a self-contained treatment of the theory of persistence modules indexed over the real line. We give new proofs of the standard results. Persistence diagrams are constructed using measure theory. Linear algebra lemmas are simplified using a new notation for calculations on quiver representations. We show that the stringent finiteness conditions required by traditional methods are not necessary to prove the existence and stability of the persistence diagram. We introduce weaker hypotheses for taming persistence modules, which are met in practice and are strong enough for the theory still to work. The constructions and proofs enabled by our framework are, we claim, cleaner and simpler.

  • M. Aanjaneya, F. Chazal, D. Chen, M. Glisse, L. J. Guibas, D. Morozov, Metric Graph Reconstruction from Noisy Data, (to appear in Intern. Journal on Computational Geometry and Applications 2012), Technical Report [CGL-TR-34] , October 2012.

    Abstract: Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs. Building on the notions of correspondence and Gromov-Hausdorff distance in metric geometry, we describe a model for such data sets as an approximation of an underlying metric graph. We present a novel algorithm that takes as an input such a data set, and outputs the underlying metric graph with guarantees. We also implement the algorithm, and evaluate its performance on a variety of real world data sets.

  • Donald Sheehy. A Multicover Nerve for Geometric Inference , Technical Report [CGL-TR-33] , October 2012.

    Abstract: We show that filtering the barycentric decomposition of a Cech complex by the cardinality of the vertices captures precisely the topology of k-covered regions among a collection of balls for all values of k. Moreover, we relate this result to the Vietoris-Rips complex to get an approximation in terms of the persistent homology.

  • Donald Sheehy. New Bounds on the Size of Optimal Meshes , Technical Report [CGL-TR-32] , October 2012.

    Abstract: We give tight bounds on the complexity of Delaunay Refinement meshes in terms of a geometric property of the input.

  • Donald Sheehy. Linear-Size Approximations to the Vietoris-Rips Filtration , Technical Report [CGL-TR-31] , October 2012.

    Abstract: Given a finite metric space of bounded doubling dimension, we give a linear-size filtered simplicial complex that has a persistence diagram that is provably close to that of the Vietoris-Rips filtration.

  • Sivaraman Balakrishnan, Alessandro Rinaldo, Aarti Singh, Donald R. Sheehy and Larry Wasserman. Minimax Rates for Homology Inference , Technical Report [CGL-TR-30] , October 2012.

    Abstract: We prove matching upper and lower bounds on the minimax sampling rate necessary to infer the homology of submanifolds in R^n under a variety of noise models.

  • Ioannis Emiris, Alexandros Konstantinakis-Karmis, Dimitri Nicolopoulos, Emmanouil Thanos-Filis. Data structures for Approximate Nearest neighbor search , Technical Report CGL-TR-29.pdf, October 2012.

    Abstract: We discuss data-structures and algorithms for three related questions in approximate Nearest-Neighbor Searching (NNS). For dimensions 3-5, we implement an improved Approximate Voronoi Diagram, based on the work of Arya, Malamatos, and Mount. This is the first implementation of the method and we show it is competitive to state-of-the-art NNS libraries. For high dimensions (e.g. 50 and beyond), we implement randomized kd-trees in CGAL, based on the corresponding algorithms of the FLANN library, and show they are competitive to FLANN and faster than CGAL kd-trees. Lastly, we study structured data, namely points almost aligned on unknown lines. We show that NNS queries take expected time proportional to loglog(n), where n denotes the number of points, when there are polylog(n) lines, uniformly distributed in a sphere, and the space dimension is fixed.

  • Ioannis Emiris, Vissarion Fisikopoulos, Christos Konaxis, Luis Penaranda: An oracle-based, output-sensitive algorithm for projections of resultant polytopes , Technical Report CGL-TR-28.pdf , October 2012.

    Abstract: We compute (projections of) the resultant polytope by designing an efficient vertex oracle, which is called once per vertex and facet of the output polytope. The oracle reduces to a regular triangulation. Resultants are fundamental in system solving and in implicitizing parametric (hyper)surfaces. Their polytope is a Minkowski summand of the secondary polytope, but our method avoids computing the latter because it is typically too large. We obtain V- and H-representations as well as a triangulation of the resultant polytope. Our method applies to polytopes represented by oracles, and leads to a fast computation of polytope approximation. Our publicly-available software is based upon the experimental CGAL package "triangulation". It computes instances of 6- or 7-d polytopes with 23K or 500 vertices, resp., within 2hrs, and is faster than tropical geometry software up to dimension 6.

  • Ioannis Emiris, Vissarion Fisikopoulos, Luis Penaranda: High-dimensional predicates: Algorithms and software , Technical Report CGL-TR-27.pdf , October 2012.

    Abstract: We implement linear algebra techniques to exploit structural properties of determinantal predicates, namely in the case of sequences of determinants where the corresponding matrices change by one row or column. In particular, we optimize sequences of Orientation predicates for convex hull computations and point location, and show an asymptotic quadratic and linear complexity, respectively, and practical speedups of up to 4x and 78x in dimension 4-12. Our second contribution focuses on hashing minors when computing regular triangulations, where the matrix entries that change belong to a single row or column. This accelerates execution up to 100x in constructing resultant polytopes. This package has been submitted to CGAL.

  • Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh : Constructing intrinsic Delaunay triangulations of submanifolds, Technical Report [CGL-TR-26], October 2012.

    Abstract: We describe an algorithm to construct an intrinsic Delaunay triangulation of a smooth closed submanifold of Euclidean space.

  • Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh : Delaunay-type structures for manifolds I: Stability, Technical Report [ CGL-TR-25 ], October 2012.

    Abstract: We introduce a parameterised notion of genericity for Delaunay complexes and show that a bound on the genericity yields a bound on the quality of the Delaunay simplices and on the stability of the Delaunay complex under perturbations of the points or the metric.

  • Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Steve Oudot : Equating the witness and restricted Delaunay complexes, Technical Report CGL-TR-24 , October 2011.

    Abstract: This work provides an analysis of the reasons why the restricted Delaunay and witness complexes fail to include each other. From this, a new set of conditions naturally arises under which the two complexes are equal.

  • Christian Sohler, David Woodruff: Subspace Embeddings for the L1-norm with Applications. Technical Report CGL-TR-23, to appear.

    Abstract: We develop new oblivious embeddings for subspaces of L1 and use them to obtain improved streaming algorithms for L1-regression.

  • Claire Caillerie, Bertrand Michel: Model selection for simplicial approximation, Technical Report CGL-TR-22 , October 2011.

  • Frederic Chazal, Leonidas Guibas, Steve Oudot, Primoz Skraba: Persistence-Based Clustering in Riemannian Manifolds, Technical Report CGL-TR-21 , October 2011.

  • Frederic Chazal, David Cohen-Steiner, Quentin Merigot: Geometric Inference for Probability Measures, Technical Report CGL-TR-20 , October 2011.

    Abstract: We extend the framework of distance functions to compact sets for geometric inference to distance-like functions to probability measures.

  • Frederic Chazal, Daniel Chen, Leonidas Guibas, Xiaoye Jiang, Christian Sommer: Data-Driven Trajectory Smoothing, Technical Report CGL-TR-19 , October 2011.

    Abstract: Motivated by the increasing availability of large collections of noisy GPS traces, we present a new data-driven framework for smoothing trajectory data. Our approach makes use of the gradient of distance-like functions to embeddings of the data in higher dimensional spaces.

  • Claire Caillerie, Frederic Chazal, Jerome Dedecker, Bertrand Michel: Deconvolution for the Wasserstein metric and geometric inference, Technical Report CGL-TR-18 , October 2011.

    Abstract: We we consider a slight modification of the classical kernel deconvolution estimator, we give a consistency result and rates of convergence for this estimator and we applied our results to geometric inference problems.

  • Gerard Biau, Frederic Chazal, David Cohen-Steiner, Luc Devroye, Carlos Rodriguez: A Weighted k-Nearest Neighbor Density Estimate for Geometric Inference, Technical Report CGL-TR-17 , October 2011.

    Abstract: We introduce and study the convergence of a family density estimate built using distance-to-measure functions.

  • Jean-Daniel Boissonnat, Arijit Ghosh: Triangulating Smooth Submanifolds with Light Scaffolding, Technical Report CGL-TR-16 , October 2011.

    Abstract: We propose an algorithm to sample and mesh a submanifold of positive reach embedded in Rd.

  • Jean-Daniel Boissonnat, Arijit Ghosh: Manifold Reconstruction Using Tangential Delaunay Complexes, Technical Report CGL-TR-15 , October 2011.

    Abstract: We provide the first algorithm that can reconstruct a smooth submanifold with a complexity that depends only linearly on the ambient

  • Ioannis Emiris, Vissarion Fisikopoulos, Luis Penaranda: Optimizing the computation of sequences of determinantal predicates, Technical Report CGL-TR-14, October 2011.

    Abstract: We exploit the similarity between encountered matrices so as to optimize computation of a sequence of determinantal predicates, such as Orientation, inSphere, Volume. We develop a method that hashes intermediate computations, and implement it in the context of CGAL triangulations, obtaining a speedup of about 2 in computing silhouettes of the secondary polytope.

  • Christian L. Muller: Finding maximizing Euclidean TSP tours for the Hame-Hyytia-Hakula conjecture, Technical Report CGL-TR-13 , October 2011.

    Abstract: In this report we disprove the Hame-Hyytia-Hakula conjecture by enumerating a number of counterexamples. These instances have been identified using gradient-free variable-metric optimization methods

  • R. van de Weygaert, G. Vegter, P. Pranav, B. Jones, H. Edelsbrunner et al. : Alpha, Betti and the Megaparsec Universe: on the Homology and Topology of the Cosmic Web , Technical Report CGL-TR-12 , October 2011.

  • R. van de Weygaert, P. Pranav, B. Jones, G. Vegter, H. Edelsbrunner, M. Wintraecken et al. : Probing Dark Energy with Alpha Shapes and Betti Numbers , Technical Report CGL-TR-11 , October 2011.

  • Mathijs H.M.J. Wintraecken and Gert Vegter: On the Complexity of Polyhedral Approximations of Submanifolds of Euclidean Spaces , Technical Report CGL-TR-10 , October 2011.

  • Sebastian U. Stich, Christian L. Muller, and Bernd Gartner: Optimization of Convex Functions with Random Pursuit, Technical Report CGL-TR-09 , October 2011.

    Abstract: We consider unconstrained randomized optimization of convex objective functions. We analyze the Random Pursuit algorithm, which iteratively computes an approximate solution to the optimization problem by repeated optimization over a randomly chosen one-dimensional subspace. This randomized method only uses zeroth-order information about the objective function and does not need any problem-specific parametrization.

  • Ioannis Emiris, Vissarion Fisikopoulos, Christos Konaxis: An output-sensitive algorithm for computing projections of resultant polytopes, Technical Report CGL-TR-08, October 2011.

    Abstract: We design an incremental, output-sensitive algorithm to compute the Newton polytope of the resultant, or its orthogonal projection along a given direction. The resultant polytope is a Minkowski summand of the secondary polytope of a pointset. We develop a CGAL-based implementation, and show its efficiency in up to 7 or 8 dimensions.

  • Frederic Cazals, Christine Andrea Roth: Investigating the Energy Landscape of Macro-molecular Systems: Data Generation Software Overview, Technical Report CGL-TR-07 , October 2011.

    Abstract: Sampling the energy landscape of a macro-molecular system using molecular dynamics (MD) is a non trivial task due to the numerous parameters and steps involved in preparing the system of interest. In this report, we present three software tools (two python scripts and one C++ program) automating the generation of MD simulations and the calculation of normal modes.

  • Oren Salzman, Michael Hemmer, Barak Raveh, and Dan Halperin: Motion Planning via Manifold Samples, Technical Report CGL-TR-06 , October 2011.

    Abstract: We present a general and modular algorithmic framework for path planning of robots. Our framework combines geometric methods for exact and complete analysis of low-dimensional configuration spaces, together with sampling-based approaches that are appropriate for higher dimensions.
    http://acg.cs.tau.ac.il/projects/mms/project-page

  • Andreas von Dziegielewski and Michael Hemmer: High Quality Surface Mesh Generation for Swept Volumes, Technical Report CGL-TR-05 , October 2011.

    Abstract: We present a novel and efficient technique to generate a high quality mesh that approximates the outer boundary of a swept volume. See CGL-TR-45 for an updated and expanded version
    http://acg.cs.tau.ac.il/projects/swept-volume/project-page

  • Barak Raveh, Nir London, Lior Zimmerman and Ora Schueler-Furman: Rosetta FlexPepDock ab-initio: Simultaneous Folding, Docking and Refinement of Peptides onto Their Receptors, Technical Report CGL-TR-04 , October 2011.

    Abstract: We present Rosetta FlexPepDock? ab-initio, a protocol for simultaneous docking and de-novo folding of peptides, starting from an approximate specification of the peptide binding site.

  • Eric Berberich, Michael Kerber, Dan Halperin and Roza Pogalnikova: Deconstructing Approximate Offsets, Technical Report CGL-TR-03 , October 2011.

    Abstract: We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance epsilon in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius?
    http://acg.cs.tau.ac.il/projects/internal-projects/deconstructing-approximate-offsets/deconstructing-minkowski-sums-the-case-of-approximate-offsets

  • Christiane Lammersen, Melanie Schmidt, Christian Sohler: Probabilistic k-median, Technical Report CGL-TR-02, October 2011.

    Abstract: We develop the first coreset construction for probabilistic data.

  • Frederic Cazals, Frederic Chazal, Christiane Lammersen, Ioannis Z. Emiris, Bernd Gartner, Joachim Giesen, Charis Malamatos, Gunter Rote: Handling High-Dimensional Data, Technical Report No. CGL-TR-01, April 2011.

    Abstract: We give a survey and assessment of methods that are commonly used for dealing with high-dimensional data, mainly from the database community.

Theses (PhD and MSc)

  • PhD, Christine Andrea Roth, Investigating energy landscapes with applications to macro-molecular flexibility, INRIA - ABS. (Tentative defense schedule: Spring 2014)
  • PhD, Vissarion Fisikopoulos, Efficient computation of substructures of general-dimensional polytopes, NKUA (Tentative defense date: Spring 2014)
  • MSc, Christian Helbling, Extreme Points in Medium and High Dimensions, ETHZ, 2010
  • MSc, Philipp Lucas, Sclow Plots: Visualizing Empty Space, FSU 2013
  • MSc, Lars Kuehne, A Data-Driven Approach to Hue-Preserving Color-Blending, FSU 2012
  • MSc, Asaf Porat, Lines Tangent to Four Polytopes in three-dimensional space, TAU, 2012, MSc-Porat-2012.pdf
  • MSc, Roza Pogalnikova, Deconstruction of Approximate Offsets via Minkowski Sums, TAU, 2012, MSc-Pogalnikova-2012.pdf
  • MSc, Oren Salzman, Motion Planning via Manifold Samples, TAU, 2012, MSc-Salzman-2011.pdf
  • MSc, Clement Maria, Construction of witness complexes, MPRI, 2011
  • MSc, David de Laat, Upper Bounds on the Optimal Meshing Error of Manifolds in Higher Codimension, RUG, September 2011.
  • MSc, Alexandros Konstantinakis-Karmis, Implementing Approximate Voronoi Diagrams for Approximate NNS, NKUA 2012 MSc-Konstantinakis-2012.pdf.
  • MSc, Emmanouil Thanos-Filis, Exploiting the Structure of the Data in Approximate NNS, NKUA 2012, MSc-Thanos-2012.pdf.
  • MSc, Dimitri Nicolopoulos, Approximate nearest neighbors in high dimensions using randomized kd-trees, NKUA 2013.

Public Reports (Deliverables)

Topic attachments
I Attachment Action Size Date Who Comment
pdfpdf CGL-TR-01.pdf manage 236.7 K 14 Oct 2011 - 22:53 JoachimGiesen CGL-TR-01: Report on handling high-dimensional data
pdfpdf CGL-TR-02.pdf manage 378.4 K 01 Oct 2011 - 14:22 ChristianSohler  
pdfpdf CGL-TR-03.pdf manage 1081.0 K 01 Oct 2011 - 19:10 MichaelHemmer CGL-TR-03: Deconstructing Approximate Offsets
pdfpdf CGL-TR-04.pdf manage 2097.6 K 01 Oct 2011 - 19:11 MichaelHemmer CGL-TR-04: Rosetta FlexPepDock? ab-initio: Simultaneous Folding, Docking and Refinement of Peptides onto Their Receptors
pdfpdf CGL-TR-05.pdf manage 1214.3 K 01 Oct 2011 - 19:13 MichaelHemmer CGL-TR-05: High Quality Surface Mesh Generation for Swept Volumes (updated by CGL-TR-45)
pdfpdf CGL-TR-06.pdf manage 723.0 K 01 Oct 2011 - 19:14 MichaelHemmer CGL-TR-06: Motion Planning via Manifold Samples
pdfpdf CGL-TR-07.pdf manage 1242.8 K 09 Oct 2011 - 20:24 FredericCazals Tech report CGL-TR-07
pdfpdf CGL-TR-08.pdf manage 499.0 K 11 Oct 2011 - 00:58 IoannisEmiris An output-sensitive algorithm for computing projections of resultant polytopes (Update in TR 28)
pdfpdf CGL-TR-09.pdf manage 840.4 K 07 Oct 2011 - 13:38 BerndGaertner Optimization with Random Pursuit
pdfpdf CGL-TR-10.pdf manage 387.1 K 14 Oct 2011 - 15:33 GertVegter CGL-TR-10: On the Complexity of Polyhedral Approximations of Submanifolds of Euclidean Spaces
pdfpdf CGL-TR-11.pdf manage 458.8 K 14 Oct 2011 - 15:34 GertVegter CGL-TR-11: Probing Dark Energy with Alpha Shapes and Betti Numbers
pdfpdf CGL-TR-12.pdf manage 2366.4 K 14 Oct 2011 - 15:35 GertVegter CGL-TR-12: Alpha, Betti and the Megaparsec Universe: on the Homology and Topology of the Cosmic Web
pdfpdf CGL-TR-13.pdf manage 515.7 K 08 Oct 2011 - 18:58 BerndGaertner Using CMA-ES to refute a conjecture for Euclidean TSP
pdfpdf CGL-TR-14.pdf manage 383.2 K 12 Oct 2011 - 02:25 IoannisEmiris Optimizing the computation of sequences of determinantal predicates (Updated in TR 74)
pdfpdf CGL-TR-15.pdf manage 441.4 K 08 Oct 2011 - 21:40 JeanDanielBoissonnat Manifold Reconstruction Using the Tangential Complex
pdfpdf CGL-TR-16.pdf manage 400.7 K 08 Oct 2011 - 21:43 JeanDanielBoissonnat Sampling and meshing smooth manifolds
pdfpdf CGL-TR-17.pdf manage 881.5 K 10 Oct 2011 - 05:58 FredChazal CGL-TR-17: A Weighted k-Nearest Neighbor Density Estimate for Geometric Inference
pdfpdf CGL-TR-18.pdf manage 4278.7 K 10 Oct 2011 - 06:32 FredChazal CGL-TR-18: Deconvolution for the Wasserstein metric and geometric inference
pdfpdf CGL-TR-19.pdf manage 1587.6 K 10 Oct 2011 - 06:56 FredChazal CGL-TR-19: Data-Driven Trajectory Smoothing
pdfpdf CGL-TR-20.pdf manage 613.8 K 10 Oct 2011 - 07:08 FredChazal Geometric Inference for Probability Measures
pdfpdf CGL-TR-21.pdf manage 6011.6 K 10 Oct 2011 - 14:51 FredChazal CGL-TR-21: Persistence-Based Clustering in Riemannian Manifolds
pdfpdf CGL-TR-22.pdf manage 1080.8 K 10 Oct 2011 - 15:50 FredChazal CGL-TR-22: Model selection for simplicial approximation
pdfpdf CGL-TR-24.pdf manage 425.1 K 10 Oct 2011 - 20:56 JeanDanielBoissonnat equating witness and restricted Delaunay complexes
pdfpdf CGL-TR-25.pdf manage 630.6 K 15 Jun 2012 - 15:23 RamsayDyer? CGL-TR-25: Delaunay-type structures for manifolds I: Stability
pdfpdf CGL-TR-26.pdf manage 1060.4 K 11 Dec 2012 - 12:13 RamsayDyer? CGL-TR-26: Constructing intrinsic Delaunay triangulations of submanifolds
pdfpdf CGL-TR-27.pdf manage 268.0 K 12 Oct 2012 - 14:00 IoannisEmiris High Dimensional Predicates: Algorithms and Software (Updated in TR 74)
pdfpdf CGL-TR-28.pdf manage 803.9 K 15 Oct 2012 - 10:32 IoannisEmiris An oracle-based, output-sensitive algorithm for projections of resultant polytopes
pdfpdf CGL-TR-29.pdf manage 1419.5 K 20 Nov 2012 - 12:51 IoannisEmiris Data structures for approximate nearest neighbor search (Update in TR 77 and TR 78)
pdfpdf CGL-TR-30.pdf manage 2704.7 K 03 Dec 2012 - 09:41 DonSheehy? CGL-TR-30: Minimax Rates for Homlogy Inference
pdfpdf CGL-TR-31.pdf manage 857.0 K 03 Dec 2012 - 09:45 DonSheehy? CGL-TR-31
pdfpdf CGL-TR-32.pdf manage 1434.0 K 03 Dec 2012 - 09:45 DonSheehy? CGL-TR-32
pdfpdf CGL-TR-33.pdf manage 422.3 K 03 Dec 2012 - 09:46 DonSheehy? CGL-TR-33
pdfpdf CGL-TR-34.pdf manage 1434.6 K 11 Dec 2012 - 14:22 FredChazal CGL-TR-34
pdfpdf CGL-TR-35.pdf manage 851.4 K 11 Dec 2012 - 14:18 FredChazal CGL-RR-35
pdfpdf CGL-TR-36.pdf manage 442.6 K 11 Dec 2012 - 14:18 FredChazal CGL-RR-36
pdfpdf CGL-TR-37.pdf manage 652.2 K 21 Oct 2012 - 16:51 MichaelHemmer CGL-TR-37: Improved Implementation of Point Location in General Two-Dimensional Subdivisions
pdfpdf CGL-TR-38.pdf manage 903.6 K 21 Oct 2012 - 16:50 MichaelHemmer CGL-TR-38: Lines Through Segments in 3D Space
pdfpdf CGL-TR-39.pdf manage 441.1 K 21 Oct 2012 - 16:50 MichaelHemmer CGL-TR-39: k-Color Multi-Robot Motion Planning
pdfpdf CGL-TR-40.pdf manage 619.6 K 21 Oct 2012 - 16:49 MichaelHemmer CGL-TR-40: On the Power of Manifold Samples in Exploring Configuration Spaces
pdfpdf CGL-TR-41.pdf manage 921.9 K 21 Oct 2012 - 16:49 MichaelHemmer CGL-TR-41: Sparsification of Motion-Planning Roadmaps by Edge Contraction
pdfpdf CGL-TR-42.pdf manage 100.7 K 18 Oct 2012 - 14:20 MathijsWintraecken? CGL-TR-42:On the extrinsic nature of triangulations
pdfpdf CGL-TR-43.pdf manage 166.7 K 18 Oct 2012 - 14:21 MathijsWintraecken? CGL-TR-43: A conceptual take on invariants of low-dimensional manifolds found by integration
pdfpdf CGL-TR-44.pdf manage 884.9 K 22 Oct 2012 - 16:08 BerndGaertner Variable Metric Random Pursuit
pdfpdf CGL-TR-45.pdf manage 2624.0 K 22 Oct 2012 - 16:01 MichaelHemmer CGL-TR-45: High Quality Surface Mesh Generation for Swept Volumes (updates CGL-TR-05)
pdfpdf CGL-TR-46.pdf manage 515.6 K 23 Oct 2012 - 14:06 BerndGaertner Fixed version wit references
pdfpdf CGL-TR-47.pdf manage 344.9 K 22 Oct 2012 - 16:23 BerndGaertner Convergence Rate of the DIRECT Algorithm
pdfpdf CGL-TR-48.pdf manage 12015.4 K 23 Oct 2012 - 13:23 FredericCazals CGL-TR-48: Report on Validations in Biophysics (Second period, task 1c)
pdfpdf CGL-TR-49.pdf manage 384.4 K 24 Oct 2012 - 16:06 JensMueller Basis Expansions for Support Vector Machines
pdfpdf CGL-TR-50.pdf manage 2783.6 K 15 Nov 2012 - 10:56 JensMueller A Data-Driven Approach to Hue-Preserving Color-Blending
pdfpdf CGL-TR-51.pdf manage 201.6 K 25 Nov 2012 - 15:48 JensMueller Heterogeneous and Missing Data
pdfpdf CGL-TR-52.pdf manage 575.3 K 21 Dec 2012 - 12:06 DrorAtariah?  
pdfpdf CGL-TR-53.pdf manage 1961.0 K 23 Sep 2013 - 13:33 DrorAtariah? C-Space parameterization tech report
pdfpdf CGL-TR-54.pdf manage 1515.0 K 24 Sep 2013 - 13:08 MichaelHemmer CGL-TR-54 Polyhedral Assembly Partitioning with Infinite Translations or The Importance of Being Exact
pdfpdf CGL-TR-55.pdf manage 392.5 K 07 Oct 2013 - 13:00 JensMueller CGL-TR-55 Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-Robot Motion Planning
pdfpdf CGL-TR-59.pdf manage 10020.8 K 07 Oct 2013 - 13:09 JensMueller Sclow Plots: Visualizing Empty Space
pdfpdf CGL-TR-60.pdf manage 1814.8 K 22 Nov 2013 - 11:01 RamsayDyer? CGL-TR-60: Intrinsic Simplices on Riemannian Manifolds
pdfpdf CGL-TR-61.pdf manage 877.2 K 04 Nov 2013 - 02:58 DonSheehy? CGL-TR-61: Geometric Separators and the Parabolic Lift
pdfpdf CGL-TR-62.pdf manage 467.2 K 04 Nov 2013 - 03:01 DonSheehy? CGL-TR-62: A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs
pdfpdf CGL-TR-63.pdf manage 728.3 K 04 Nov 2013 - 03:04 DonSheehy? CGL-TR-63: Zigzag Zoology
pdfpdf CGL-TR-64.pdf manage 721.2 K 04 Nov 2013 - 03:13 DonSheehy? A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations
pdfpdf CGL-TR-66.pdf manage 285.9 K 04 Nov 2013 - 15:49 JensMueller Compressing Support Vector Machines
pdfpdf CGL-TR-67.pdf manage 361.8 K 04 Nov 2013 - 15:52 JensMueller Sketching the Support of a Probability Measure
pdfpdf CGL-TR-68.pdf manage 1874.7 K 07 Nov 2013 - 13:26 MarcGlisse CGL-TR-68: Homological Reconstruction and Simplification in R^3
pdfpdf CGL-TR-69.pdf manage 565.1 K 08 Nov 2013 - 10:02 ChristianSohler Technical Report 69: Probabilistic k-median implementation
pdfpdf CGL-TR-70.pdf manage 333.0 K 08 Nov 2013 - 10:15 ChristianSohler Technical Report 70: Smallest enclosing ball for probabilistic data
pdfpdf CGL-TR-71.pdf manage 200.8 K 11 Nov 2013 - 14:46 BerndGaertner Continuum armed bandits paper
pdfpdf CGL-TR-72.pdf manage 119.3 K 11 Nov 2013 - 14:56 BerndGaertner Large shadows from sparse inequalities paper
pdfpdf CGL-TR-73.pdf manage 372.0 K 17 Feb 2014 - 10:28 ChristianSohler Fast clustering technique for range reporting
pdfpdf CGL-TR-74.pdf manage 298.3 K 08 Nov 2013 - 21:57 IoannisEmiris High Dimensional Predicates: Update on Algorithms and Software
pdfpdf CGL-TR-75.pdf manage 315.2 K 08 Nov 2013 - 22:05 IoannisEmiris Efficient edge skeleton computation for polytopes defined by Oracles
pdfpdf CGL-TR-76.pdf manage 359.4 K 08 Nov 2013 - 22:13 IoannisEmiris Algorithms for volume approximation of convex bodies
pdfpdf CGL-TR-77.pdf manage 467.7 K 14 Nov 2013 - 11:03 IoannisEmiris Approximate Nearest Neighbor Search for Points on Lower Dimensional Flats
pdfpdf CGL-TR-78.pdf manage 1089.9 K 27 Nov 2013 - 23:35 IoannisEmiris Randomized kd-trees for Approximate Nearest Neighbor Search
pdfpdf CGL-TR-79.pdf manage 1164.1 K 11 Nov 2013 - 09:03 MichaelHemmer [CGL-TR-79] Asymptotically near-optimal RRT for fast, high-quality, motion planning
pdfpdf CGL-TR-80.pdf manage 703.1 K 13 Nov 2013 - 14:27 BerndGaertner Experimental Validation of Variable Metric Random Pursuit
pdfpdf CGL-TR-83.pdf manage 407.8 K 09 Dec 2013 - 17:21 JeanDanielBoissonnat CGL-TR-83: Computing Persistent Cohomolgy
pdfpdf CGL-TR-84.pdf manage 517.5 K 26 Nov 2013 - 13:41 RamsayDyer? CGL-TR-84: Delaunay stability via perturbations
pdfpdf CGL-TR-85.pdf manage 566.4 K 26 Nov 2013 - 14:48 RamsayDyer? CGL-TR-85: The stability of Delaunay triangulations
pdfpdf CGL-TR-86.pdf manage 503.3 K 26 Nov 2013 - 13:57 RamsayDyer? CGL-TR-86: Delaunay triangulation of manifolds
pdfpdf CGL-TR-87.pdf manage 231.4 K 13 Nov 2013 - 17:28 BerndGaertner Matrix-valued iterated projections
pdfpdf CGL-TR-88.pdf manage 154.0 K 21 Nov 2013 - 14:39 BerndGaertner Random Pursuit in Hilbert Space
pdfpdf CGL-TR-89.pdf manage 311.3 K 26 Nov 2013 - 08:27 JensMueller A parallel algorithm for computing the flow complex
pdfpdf MSc-Konstantinakis-2012.pdf manage 713.8 K 04 Dec 2012 - 17:13 IoannisEmiris MSc-Konstantinakis-2012: Implementing Approximate Voronoi Diagrams for Approximate Nearest Neighbor Searching
pdfpdf MSc-Pogalnikova-2012.pdf manage 1549.3 K 24 Oct 2012 - 09:19 MichaelHemmer MSc-Pogalnikova-2012: Deconstruction of Approximate Offsets via Minkowski Sums
pdfpdf MSc-Porat-2012.pdf manage 1628.5 K 24 Oct 2012 - 09:33 MichaelHemmer MSc-Porat-2012: Lines Tangent to Four Polytopes in three-dimensional space
pdfpdf MSc-Salzman-2011.pdf manage 2713.4 K 06 Oct 2011 - 14:17 MichaelHemmer MSc-Salzman-2011: Motion Planning via Manifold Samples
pdfpdf MSc-Thanos-2012.pdf manage 193.5 K 12 Oct 2012 - 10:49 IoannisEmiris Exploiting the Structure of the Data in Approximate NNS
pdfpdf WP1softwareReport.pdf manage 98.3 K 23 Nov 2013 - 15:21 JoachimGiesen WP1 software report
pdfpdf final-workshop.pdf manage 834.9 K 05 Nov 2013 - 19:33 JoachimGiesen Report on final workshop
pdfpdf kickoff.pdf manage 81.2 K 14 Oct 2011 - 22:44 JoachimGiesen Report on Kickoff Workshop
pdfpdf website.pdf manage 65.6 K 14 Oct 2011 - 22:44 JoachimGiesen Report on Website
pdfpdf wp1period1.pdf manage 98.2 K 14 Oct 2011 - 22:42 JoachimGiesen WP1 first period report
pdfpdf wp1period2.pdf manage 108.2 K 24 Nov 2012 - 19:07 JoachimGiesen WP1 second period report
pdfpdf wp1period3.pdf manage 425.4 K 23 Nov 2013 - 15:21 JoachimGiesen WP1 third period report
pdfpdf wp2period1.pdf manage 95.4 K 15 Oct 2011 - 00:36 JoachimGiesen WP2 first period report
pdfpdf wp2period2.pdf manage 135.6 K 24 Nov 2012 - 19:07 JoachimGiesen WP2 second period report
pdfpdf wp2period3.pdf manage 144.2 K 25 Nov 2013 - 16:31 JoachimGiesen WP2 third period report
pdfpdf wp2software.pdf manage 107.8 K 04 Dec 2013 - 17:25 JoachimGiesen WP2 software report
pdfpdf wp3period1.pdf manage 114.0 K 14 Oct 2011 - 22:43 JoachimGiesen WP3 first period report
pdfpdf wp3period2.pdf manage 139.6 K 24 Nov 2012 - 19:08 JoachimGiesen WP3 second period report
pdfpdf wp3period3.pdf manage 173.8 K 23 Nov 2013 - 15:23 JoachimGiesen WP3 third period report
pdfpdf wp3software.pdf manage 127.9 K 23 Nov 2013 - 15:23 JoachimGiesen WP3 software report
pdfpdf wp4period1.pdf manage 71.7 K 14 Oct 2011 - 22:43 JoachimGiesen WP4 first period report
pdfpdf wp4period2.pdf manage 71.5 K 06 Nov 2013 - 17:16 JoachimGiesen WP4 second period report
pdfpdf wp4period3.pdf manage 72.5 K 06 Nov 2013 - 17:15 JoachimGiesen WP4 third period report

 
© 2010 CGL Computational Geometric Learning.