S. Stich, B. Gärtner. Random Pursuit in Hilbert Space, [CGL-TR-88], November 2013
C. Müller, S. Stich, B. Gärtner. Matrix-valued Iterative Random Projections, [CGL-TR-87], November 2013
J-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay triangulations of manifolds. [INRIA RR-8389,hal-00879133], [CGL-TR-86], October 2013
J-D. Boissonnat, R. Dyer, A. Ghosh. The Stability of Delaunay Triangulations [INRIA RR-8276 , hal-00807050], [CGL-TR-85], April 2013
J-D. Boissonnat, R. Dyer, A. Ghosh. Delaunay stability via perturbations [hal-00806107], [CGL-TR-84], March 2013
J-D. Boissonnat, T. Dey, C. Maria. The Compressed Annotation Matrix: an Efficient Data Structure for Computing Persistent Cohomology,[CGL-TR-83], April 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.
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
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.
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 L_{1 }and use them to obtain improved streaming algorithms for L_{1}-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.
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
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.
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 L_{1 }and use them to obtain improved streaming algorithms for L_{1}-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.
I | Attachment | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|
CGL-TR-01.pdf | manage | 236.7 K | 14 Oct 2011 - 22:53 | JoachimGiesen | CGL-TR-01: Report on handling high-dimensional data | |
CGL-TR-02.pdf | manage | 378.4 K | 01 Oct 2011 - 14:22 | ChristianSohler | ||
CGL-TR-03.pdf | manage | 1081.0 K | 01 Oct 2011 - 19:10 | MichaelHemmer | CGL-TR-03: Deconstructing Approximate Offsets | |
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 | |
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) | |
CGL-TR-06.pdf | manage | 723.0 K | 01 Oct 2011 - 19:14 | MichaelHemmer | CGL-TR-06: Motion Planning via Manifold Samples | |
CGL-TR-07.pdf | manage | 1242.8 K | 09 Oct 2011 - 20:24 | FredericCazals | Tech report CGL-TR-07 | |
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) | |
CGL-TR-09.pdf | manage | 840.4 K | 07 Oct 2011 - 13:38 | BerndGaertner | Optimization with Random Pursuit | |
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 | |
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 | |
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 | |
CGL-TR-13.pdf | manage | 515.7 K | 08 Oct 2011 - 18:58 | BerndGaertner | Using CMA-ES to refute a conjecture for Euclidean TSP | |
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) | |
CGL-TR-15.pdf | manage | 441.4 K | 08 Oct 2011 - 21:40 | JeanDanielBoissonnat | Manifold Reconstruction Using the Tangential Complex | |
CGL-TR-16.pdf | manage | 400.7 K | 08 Oct 2011 - 21:43 | JeanDanielBoissonnat | Sampling and meshing smooth manifolds | |
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 | |
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 | |
CGL-TR-19.pdf | manage | 1587.6 K | 10 Oct 2011 - 06:56 | FredChazal | CGL-TR-19: Data-Driven Trajectory Smoothing | |
CGL-TR-20.pdf | manage | 613.8 K | 10 Oct 2011 - 07:08 | FredChazal | Geometric Inference for Probability Measures | |
CGL-TR-21.pdf | manage | 6011.6 K | 10 Oct 2011 - 14:51 | FredChazal | CGL-TR-21: Persistence-Based Clustering in Riemannian Manifolds | |
CGL-TR-22.pdf | manage | 1080.8 K | 10 Oct 2011 - 15:50 | FredChazal | CGL-TR-22: Model selection for simplicial approximation | |
CGL-TR-24.pdf | manage | 425.1 K | 10 Oct 2011 - 20:56 | JeanDanielBoissonnat | equating witness and restricted Delaunay complexes | |
CGL-TR-25.pdf | manage | 630.6 K | 15 Jun 2012 - 15:23 | RamsayDyer? | CGL-TR-25: Delaunay-type structures for manifolds I: Stability | |
CGL-TR-26.pdf | manage | 1060.4 K | 11 Dec 2012 - 12:13 | RamsayDyer? | CGL-TR-26: Constructing intrinsic Delaunay triangulations of submanifolds | |
CGL-TR-27.pdf | manage | 268.0 K | 12 Oct 2012 - 14:00 | IoannisEmiris | High Dimensional Predicates: Algorithms and Software (Updated in TR 74) | |
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 | |
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) | |
CGL-TR-30.pdf | manage | 2704.7 K | 03 Dec 2012 - 09:41 | DonSheehy? | CGL-TR-30: Minimax Rates for Homlogy Inference | |
CGL-TR-31.pdf | manage | 857.0 K | 03 Dec 2012 - 09:45 | DonSheehy? | CGL-TR-31 | |
CGL-TR-32.pdf | manage | 1434.0 K | 03 Dec 2012 - 09:45 | DonSheehy? | CGL-TR-32 | |
CGL-TR-33.pdf | manage | 422.3 K | 03 Dec 2012 - 09:46 | DonSheehy? | CGL-TR-33 | |
CGL-TR-34.pdf | manage | 1434.6 K | 11 Dec 2012 - 14:22 | FredChazal | CGL-TR-34 | |
CGL-TR-35.pdf | manage | 851.4 K | 11 Dec 2012 - 14:18 | FredChazal | CGL-RR-35 | |
CGL-TR-36.pdf | manage | 442.6 K | 11 Dec 2012 - 14:18 | FredChazal | CGL-RR-36 | |
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 | |
CGL-TR-38.pdf | manage | 903.6 K | 21 Oct 2012 - 16:50 | MichaelHemmer | CGL-TR-38: Lines Through Segments in 3D Space | |
CGL-TR-39.pdf | manage | 441.1 K | 21 Oct 2012 - 16:50 | MichaelHemmer | CGL-TR-39: k-Color Multi-Robot Motion Planning | |
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 | |
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 | |
CGL-TR-42.pdf | manage | 100.7 K | 18 Oct 2012 - 14:20 | MathijsWintraecken? | CGL-TR-42:On the extrinsic nature of triangulations | |
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 | |
CGL-TR-44.pdf | manage | 884.9 K | 22 Oct 2012 - 16:08 | BerndGaertner | Variable Metric Random Pursuit | |
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) | |
CGL-TR-46.pdf | manage | 515.6 K | 23 Oct 2012 - 14:06 | BerndGaertner | Fixed version wit references | |
CGL-TR-47.pdf | manage | 344.9 K | 22 Oct 2012 - 16:23 | BerndGaertner | Convergence Rate of the DIRECT Algorithm | |
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) | |
CGL-TR-49.pdf | manage | 384.4 K | 24 Oct 2012 - 16:06 | JensMueller | Basis Expansions for Support Vector Machines | |
CGL-TR-50.pdf | manage | 2783.6 K | 15 Nov 2012 - 10:56 | JensMueller | A Data-Driven Approach to Hue-Preserving Color-Blending | |
CGL-TR-51.pdf | manage | 201.6 K | 25 Nov 2012 - 15:48 | JensMueller | Heterogeneous and Missing Data | |
CGL-TR-52.pdf | manage | 575.3 K | 21 Dec 2012 - 12:06 | DrorAtariah? | ||
CGL-TR-53.pdf | manage | 1961.0 K | 23 Sep 2013 - 13:33 | DrorAtariah? | C-Space parameterization tech report | |
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 | |
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 | |
CGL-TR-59.pdf | manage | 10020.8 K | 07 Oct 2013 - 13:09 | JensMueller | Sclow Plots: Visualizing Empty Space | |
CGL-TR-60.pdf | manage | 1814.8 K | 22 Nov 2013 - 11:01 | RamsayDyer? | CGL-TR-60: Intrinsic Simplices on Riemannian Manifolds | |
CGL-TR-61.pdf | manage | 877.2 K | 04 Nov 2013 - 02:58 | DonSheehy? | CGL-TR-61: Geometric Separators and the Parabolic Lift | |
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 | |
CGL-TR-63.pdf | manage | 728.3 K | 04 Nov 2013 - 03:04 | DonSheehy? | CGL-TR-63: Zigzag Zoology | |
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 | |
CGL-TR-66.pdf | manage | 285.9 K | 04 Nov 2013 - 15:49 | JensMueller | Compressing Support Vector Machines | |
CGL-TR-67.pdf | manage | 361.8 K | 04 Nov 2013 - 15:52 | JensMueller | Sketching the Support of a Probability Measure | |
CGL-TR-68.pdf | manage | 1874.7 K | 07 Nov 2013 - 13:26 | MarcGlisse | CGL-TR-68: Homological Reconstruction and Simplification in R^3 | |
CGL-TR-69.pdf | manage | 565.1 K | 08 Nov 2013 - 10:02 | ChristianSohler | Technical Report 69: Probabilistic k-median implementation | |
CGL-TR-70.pdf | manage | 333.0 K | 08 Nov 2013 - 10:15 | ChristianSohler | Technical Report 70: Smallest enclosing ball for probabilistic data | |
CGL-TR-71.pdf | manage | 200.8 K | 11 Nov 2013 - 14:46 | BerndGaertner | Continuum armed bandits paper | |
CGL-TR-72.pdf | manage | 119.3 K | 11 Nov 2013 - 14:56 | BerndGaertner | Large shadows from sparse inequalities paper | |
CGL-TR-73.pdf | manage | 372.0 K | 17 Feb 2014 - 10:28 | ChristianSohler | Fast clustering technique for range reporting | |
CGL-TR-74.pdf | manage | 298.3 K | 08 Nov 2013 - 21:57 | IoannisEmiris | High Dimensional Predicates: Update on Algorithms and Software | |
CGL-TR-75.pdf | manage | 315.2 K | 08 Nov 2013 - 22:05 | IoannisEmiris | Efficient edge skeleton computation for polytopes defined by Oracles | |
CGL-TR-76.pdf | manage | 359.4 K | 08 Nov 2013 - 22:13 | IoannisEmiris | Algorithms for volume approximation of convex bodies | |
CGL-TR-77.pdf | manage | 467.7 K | 14 Nov 2013 - 11:03 | IoannisEmiris | Approximate Nearest Neighbor Search for Points on Lower Dimensional Flats | |
CGL-TR-78.pdf | manage | 1089.9 K | 27 Nov 2013 - 23:35 | IoannisEmiris | Randomized kd-trees for Approximate Nearest Neighbor Search | |
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 | |
CGL-TR-80.pdf | manage | 703.1 K | 13 Nov 2013 - 14:27 | BerndGaertner | Experimental Validation of Variable Metric Random Pursuit | |
CGL-TR-83.pdf | manage | 407.8 K | 09 Dec 2013 - 17:21 | JeanDanielBoissonnat | CGL-TR-83: Computing Persistent Cohomolgy | |
CGL-TR-84.pdf | manage | 517.5 K | 26 Nov 2013 - 13:41 | RamsayDyer? | CGL-TR-84: Delaunay stability via perturbations | |
CGL-TR-85.pdf | manage | 566.4 K | 26 Nov 2013 - 14:48 | RamsayDyer? | CGL-TR-85: The stability of Delaunay triangulations | |
CGL-TR-86.pdf | manage | 503.3 K | 26 Nov 2013 - 13:57 | RamsayDyer? | CGL-TR-86: Delaunay triangulation of manifolds | |
CGL-TR-87.pdf | manage | 231.4 K | 13 Nov 2013 - 17:28 | BerndGaertner | Matrix-valued iterated projections | |
CGL-TR-88.pdf | manage | 154.0 K | 21 Nov 2013 - 14:39 | BerndGaertner | Random Pursuit in Hilbert Space | |
CGL-TR-89.pdf | manage | 311.3 K | 26 Nov 2013 - 08:27 | JensMueller | A parallel algorithm for computing the flow complex | |
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 | |
MSc-Pogalnikova-2012.pdf | manage | 1549.3 K | 24 Oct 2012 - 09:19 | MichaelHemmer | MSc-Pogalnikova-2012: Deconstruction of Approximate Offsets via Minkowski Sums | |
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 | |
MSc-Salzman-2011.pdf | manage | 2713.4 K | 06 Oct 2011 - 14:17 | MichaelHemmer | MSc-Salzman-2011: Motion Planning via Manifold Samples | |
MSc-Thanos-2012.pdf | manage | 193.5 K | 12 Oct 2012 - 10:49 | IoannisEmiris | Exploiting the Structure of the Data in Approximate NNS | |
WP1softwareReport.pdf | manage | 98.3 K | 23 Nov 2013 - 15:21 | JoachimGiesen | WP1 software report | |
final-workshop.pdf | manage | 834.9 K | 05 Nov 2013 - 19:33 | JoachimGiesen | Report on final workshop | |
kickoff.pdf | manage | 81.2 K | 14 Oct 2011 - 22:44 | JoachimGiesen | Report on Kickoff Workshop | |
website.pdf | manage | 65.6 K | 14 Oct 2011 - 22:44 | JoachimGiesen | Report on Website | |
wp1period1.pdf | manage | 98.2 K | 14 Oct 2011 - 22:42 | JoachimGiesen | WP1 first period report | |
wp1period2.pdf | manage | 108.2 K | 24 Nov 2012 - 19:07 | JoachimGiesen | WP1 second period report | |
wp1period3.pdf | manage | 425.4 K | 23 Nov 2013 - 15:21 | JoachimGiesen | WP1 third period report | |
wp2period1.pdf | manage | 95.4 K | 15 Oct 2011 - 00:36 | JoachimGiesen | WP2 first period report | |
wp2period2.pdf | manage | 135.6 K | 24 Nov 2012 - 19:07 | JoachimGiesen | WP2 second period report | |
wp2period3.pdf | manage | 144.2 K | 25 Nov 2013 - 16:31 | JoachimGiesen | WP2 third period report | |
wp2software.pdf | manage | 107.8 K | 04 Dec 2013 - 17:25 | JoachimGiesen | WP2 software report | |
wp3period1.pdf | manage | 114.0 K | 14 Oct 2011 - 22:43 | JoachimGiesen | WP3 first period report | |
wp3period2.pdf | manage | 139.6 K | 24 Nov 2012 - 19:08 | JoachimGiesen | WP3 second period report | |
wp3period3.pdf | manage | 173.8 K | 23 Nov 2013 - 15:23 | JoachimGiesen | WP3 third period report | |
wp3software.pdf | manage | 127.9 K | 23 Nov 2013 - 15:23 | JoachimGiesen | WP3 software report | |
wp4period1.pdf | manage | 71.7 K | 14 Oct 2011 - 22:43 | JoachimGiesen | WP4 first period report | |
wp4period2.pdf | manage | 71.5 K | 06 Nov 2013 - 17:16 | JoachimGiesen | WP4 second period report | |
wp4period3.pdf | manage | 72.5 K | 06 Nov 2013 - 17:15 | JoachimGiesen | WP4 third period report |