Publications

Technical Reports

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

• 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, Oren Salzman, Motion Planning via Manifold Samples, TAU, 2011, 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, Approximate Voronoi diagrams, NKUA 2011-12.
• MSc, Manos Thanos, Adaptive data-structures in medium dimensions, NKUA 2011-12.
• MSc, Dimitris Nicolopoulos, Approximate nearest neighbors in high dimensions, NKUA 2011-12.

Public Reports (Deliverables)

• D1.1: Report on WP 1 in First Period (wp1period1.pdf)
• D2.1: Assessment of Work in Database Community (CGL-TR-01.pdf)
• D2.2: Report on WP 2 in First Period (wp2period1.pdf)
• D3.1: Report on WP 3 in First Period (wp3period1.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)