Publications

Technical Reports

• D.Atariah, G. Rote, Configuration Space Visualization, [CGL-TR 52], December 2012
  
  Abstract: Based on a simple parameterization of contact surfaces, we visualize both the workspace and the corresponding config- uration space of a planar polygonal robot that moves amid planar polygonal obstacles.

• F. Cazals, E. Ehsanfar, D. Halperin, R. van de Weijgaert, Report on Heterogeneous and Missing Data, Technical report [CGL-TR 51], October 2012

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

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

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

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

• Y. Brise and B. Gaertner, Convergence Rate of the DIRECT Algorithm, Technical Report [CGL-TR 47], October 2012
  
  Abstract: The {DIRECT} algorithm is a deterministic sampling method for Lipschitz continuous function optimization. We give the first quantitative analysis of the convergence rate of DIRECT. We show that, in $\mathbb{R}^d$, $O(d^{2d+2} \frac{1}{\epsilon^{2d}})$ function evaluations are sufficient to guarantee an absolute error in function value not larger than $\epsilon$. Dropping Lipschitz continuity the same bound applies to the sampling distance from the location of the global minimum, with an even better hidden constant.

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

• A. v. Dziegielewski, M. Hemmer and E. Schoemer, High Quality Conservative Surface Mesh Generation for Swept Volumes, Technical Report [CGL-TR 45], October 2012
  
  Abstract: We present a novel, efficient and flexible scheme to generate a high quality mesh that approximates the outer boundary of a swept volume. This is an updated and expanded version of Technical Report [CGL-TR-05].

• 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%.

• 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.

• 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.

• 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.

• 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.

• 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₁ and use them to obtain improved streaming algorithms for L₁-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.

• 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

• 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?

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

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

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

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

Theses (PhD and MSc)

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

Public Reports (Deliverables)

• D1.2: Report on WP 1 in Second Period (wp1period2.pdf)
• D1.1: Report on WP 1 in First Period (wp1period1.pdf)
• D2.3: Report on WP 2 in Second Period (wp2period2.pdf)
• D2.2: Report on WP 2 in First Period (wp2period1.pdf)
• D2.1: Assessment of Work in Database Community (CGL-TR-01.pdf)
• D3.3: Report on Heterogeneous and Missing Data (CGL-TR-51.pdf)
• D3.2: Report on WP 3 in Second Period (wp3period2.pdf)
• D3.1: Report on WP 3 in First Period (wp3period1.pdf)
• D4.4: Report on WP 4 in Second Period (wp4period2.pdf)
• D4.3: Report on WP 4 in First Period (wp4period1.pdf)
• D4.2: Report on the Kickoff Workshop (kickoff.pdf)
• D4.1: Report on the Website (website.pdf)

• cgl_constab.pdf: CGL-TR-26: Constructing intrinsic Delaunay triangulations of submanifolds