Computing the volume of a polytope in high dimensions is computationally challenging but has wide applications. Current state-of-the-art algorithms to compute such volumes rely on efficient sampling of a Gaussian distribution restricted to the polytope, using e.g. Hamiltonian Monte Carlo. We present a new sampling strategy that uses a Piecewise Deterministic Markov Process. Like Hamiltonian Monte Carlo, this new method involves simulating trajectories of a non-reversible process and inherits similar good mixing properties. However, importantly, the process can be simulated more easily due to its piecewise linear trajectories – and this leads to a reduction of the computational cost by a factor of the dimension of the space. Our experiments indicate that our method is numerically robust and is one order of magnitude faster (or better) than existing methods using Hamiltonian Monte Carlo. On a single core processor, we report computational time of a few minutes up to dimension 500.

The center of mass of a point set lying on a manifold generalizes the celebrated Euclidean centroid, and is ubiquitous in statistical analysis in non Euclidean spaces. In this work, we give a complete characterization of the weighted p-mean of a finite set of angular values on S¹, based on a decomposition of S¹ such that the functional of interest has at most one local minimum per cell. This characterization is used to show that the problem is decidable for rational angular values -a consequence of Lindemann’s theorem on the transcendence of π, and to develop an effective algorithm parameterized by exact predicates. A robust implementation of this algorithm based on multi-precision interval arithmetic is also presented, and is shown to be effective for large values of n and p. We use it as building block to implement the k-means and k-means++ clustering algorithms on the flat torus, with applications to clustering protein molecular conformations. These algorithms are available in the Structural Bioinformatics Library (http://sbl.inria.fr). Our derivations are of interest in two respects. First, efficient p-mean calculations are relevant to develop principal components analysis on the flat torus encoding angular spaces-a particularly important case to describe molecular conformations. Second, our two-stage strategy stresses the interest of combinatorial methods for p-means, also emphasizing the role of numerical issues.

We propose a novel nonparametric online predictor for discrete labels conditioned on multivariate continuous features. The predictor is based on a feature space discretization induced by a full-fledged k-d tree with randomly picked directions and a recursive Bayesian distribution, which allows to automatically learn the most relevant feature scales characterizing the conditional distribution. We prove its pointwise universality, i.e., it achieves a normalized log loss performance asymptotically as good as the true conditional entropy of the labels given the features. The time complexity to process the n-th sample point is O(log n) in probability with respect to the distribution generating the data points, whereas other exact nonparametric methods require to process all past observations. Experiments on challenging datasets show the computational and statistical efficiency of our algorithm in comparison to standard and state-of-the-art methods.

Given samples from two distributions, a non-parametric two-sample test aims at determining whether the two distributions are equal or not, based on a test statistic. Classically, this statistic is computed on the whole data set, or is computed on a subset of the data set by a function trained on its complement. We consider methods in a third tier, so as to deal with large (possibly infinite) data sets, and to automatically determine the most relevant scales to work at, making two contributions. First, we develop a generic sequential non-parametric testing framework, in which the sample size need not be fixed in advance. This makes our test a truly sequential non-parametric multivariate two-sample test. Under information theoretic conditions qualifying the difference between the tested distributions, consistency of the two-sample test is established. Second, we instantiate our framework using nearest neighbor regressors, and show how the power of the resulting two-sample test can be improved using Bayesian mixtures and switch distributions. This combination of techniques yields automatic scale selection, and experiments performed on challenging data sets show that our sequential tests exhibit comparable performances to those of state-of-the-art non-sequential tests.

Motivation: Software in structural bioinformatics has mainly been application driven. To favor practitioners seeking off-the-shelf applications, but also developers seeking advanced building blocks to develop novel applications, we undertook the design of the Structural Bioinformatics Library ( SBL , http://sbl.inria.fr ), a generic C ++/python cross-platform software library targeting complex problems in structural bioinformatics. Its tenet is based on a modular design offering a rich and versatile framework allowing the development of novel applications requiring well specified complex operations, without compromising robustness and performances. Results: The SBL involves four software components (1-4 thereafter). For end-users, the SBL provides ready to use, state-of-the-art (1) applications to handle molecular models defined by unions of balls, to deal with molecular flexibility, to model macro-molecular assemblies. These applications can also be combined to tackle integrated analysis problems. For developers, the SBL provides a broad C ++ toolbox with modular design, involving core (2) algorithms , (3) biophysical models and (4) modules , the latter being especially suited to develop novel applications. The SBL comes with a thorough documentation consisting of user and reference manuals, and a bugzilla platform to handle community feedback. Availability and Implementation: The SBL is available from http://sbl.inria.fr. Contact: [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

Comparing two sets of multivariate samples is a central problem in data analysis. From a statistical standpoint, the simplest way to perform such a comparison is to resort to a non-parametric two-sample test (TST), which checks whether the two sets can be seen as i.i.d. samples of an identical unknown distribution (the null hypothesis). If the null is rejected, one wishes to identify regions accounting for this difference. This paper presents a two-stage method providing feedback on this difference, based upon a combination of statistical learning (regression) and computational topology methods. Consider two populations, each given as a point cloud in Rd. In the first step, we assign a label to each set and we compute, for each sample point, a discrepancy measure based on comparing an estimate of the conditional probability distribution of the label given a position versus the global unconditional label distribution. In the second step, we study the height function defined at each point by the aforementioned estimated discrepancy. Topological persistence is used to identify persistent local minima of this height function, their basins defining regions of points with high discrepancy and in spatial proximity. Experiments are reported both on synthetic and real data (satellite images and handwritten digit images), ranging in dimension from d = 2 to d = 784, illustrating the ability of our method to localize discrepancies. On a general perspective, the ability to provide feedback downstream TST may prove of ubiquitous interest in exploratory statistics and data science.

Abstract Choosing balls that best approximate a 3D object is a non‐trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object defined by a union of n balls with balls defining a region . This solution is further used to construct an outer approximation enclosing the initial shape, and an interpolated approximation sandwiched between the inner and outer approximations. The inner approximation problem is reduced to a geometric generalization of weighted max k‐cover, solved with the greedy strategy which achieves the classical lower bound. The outer approximation is reduced to exploiting the partition of the boundary of by the Apollonius Voronoi diagram of the balls defining the inner approximation. Implementation‐wise, we present robust software incorporating the calculation of the exact Delaunay triangulation of points with degree two algebraic coordinates, of the exact medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. Application‐wise, we exhibit accurate coarse‐grain molecular models using a number of balls 20 times smaller than the number of atoms, a key requirement to simulate crowded cellular environments.

To address challenging flexible docking problems, a number of docking algorithms pregenerate large collections of candidate conformers. To remove the redundancy from such ensembles, a central problem in this context is to report a selection of conformers maximizing some geometric diversity criterion. We make three contributions to this problem. First, we resort to geometric optimization so as to report selections maximizing the molecular volume or molecular surface area (MSA) of the selection. Greedy strategies are developed, together with approximation bounds. Second, to assess the efficacy of our algorithms, we investigate two conformer ensembles corresponding to a flexible loop of four protein complexes. By focusing on the MSA of the selection, we show that our strategy matches the MSA of standard selection methods, but resorting to a number of conformers between one and two orders of magnitude smaller. This observation is qualitatively explained using the Betti numbers of the union of balls of the selection. Finally, we replace the conformer selection problem in the context of multiple-copy flexible docking. On the aforementioned systems, we show that using the loops selected by our strategy can improve the result of the docking process.

Balls and spheres are amongst the simplest 3 D modeling primitives, and computing the volume of a union of balls is an elementary problem. Although a number of strategies addressing this problem have been investigated in several communities, we are not aware of any robust algorithm, and present the first such algorithm. Our calculation relies on the decomposition of the volume of the union into convex regions, namely the restrictions of the balls to their regions in the power diagram. Theoretically, we establish a formula for the volume of a restriction, based on Gauss' divergence theorem. The proof being constructive, we develop the associated algorithm. On the implementation side, we carefully analyse the predicates and constructions involved in the volume calculation, and present a certified implementation relying on interval arithmetic. The result is certified in the sense that the exact volume belongs to the interval computed. Experimental results are presented on hand-crafted models illustrating various difficulties, as well as on the 58,898 models found in the tenth of July 2009 release of the Protein Data Bank.

SUMMARY: Intervor is a software computing a parameter-free representation of macro-molecular interfaces, based on the alpha-complex of the atoms. Given two interacting partners, possibly with water molecules squeezed in-between them, Intervor computes an interface model which has the following characteristics: (i) it identifies the atoms of the partners which are in direct contact and those whose interaction is water mediated, (ii) it defines a geometric complex separating the partners, the Voronoi interface, whose geometric and topological descriptions are straightforward (surface area, number of patches, curvature), (iii) it allows the definition of the depth of atoms at the interface, thus going beyond the traditional dissection of an interface into a core and a rim. These features can be used to investigate correlations between structural parameters and key properties such as the conservation of residues, their polarity, the water dynamics at the interface, mutagenesis data, etc. AVAILABILITY: Intervor can be run from the web site http://cgal.inria.fr/abs/Intervor or upon downloading the binary file. Plugins are also made available for VMD and Pymol.

UNLABELLED: The ever increasing number of structural biological data calls for robust and efficient software for analysis. Easy Structural Biology Template Library (ESBTL) is a lightweight C++ library that allows the handling of PDB data and provides a data structure suitable for geometric constructions and analyses. The parser and data model provided by this ready-to-use include-only library allows adequate treatment of usually discarded information (insertion code, atom occupancy, etc.) while still being able to detect badly formatted files. The template-based structure allows rapid design of new computational structural biology applications and is fully compatible with the new remediated PDB archive format. It also allows the code to be easy-to-use while being versatile enough to allow advanced user developments. AVAILABILITY: ESBTL is freely available under the GNU General Public License from http://esbtl.sf.net. The web site provides the source code, examples, code snippets and documentation.

Abstract Dealing with ambiguous data is a challenge in Science in general and geometry processing in particular. One route of choice to extract information from such data consists of replacing the ambiguous input by a continuum, typically a one‐parameter family, so as to mine stable geometric and topological features within this family. This work follows this spirit and introduces a novel framework to handle 3D ambiguous geometric data which are naturally modeled by balls. First, we introduce toleranced balls to model ambiguous geometric objects. A toleranced ball consists of two concentric balls, and interpolating between their radii provides a way to explore a range of possible geometries. We propose to model an ambiguous shape by a collection of toleranced balls, and show that the aforementioned radius interpolation is tantamount to the growth process associated with an additively‐multiplicatively weighted Voronoi diagram (also called compoundly weighted or CW). Second and third, we investigate properties of the CW diagram and the associated CW α‐complex, which provides a filtration called the λ‐complex. Fourth, we sketch a naive algorithm to compute the CW VD. Finally, we use the λ‐complex to assess the quality of models of large protein assemblies, as these models inherently feature ambiguities.

The Delaunay triangulation and its dual the Voronoi diagram are ubiquitous geometric complexes. From a topological standpoint, the connection has recently been made between these cell complexes and the Morse theory of distance functions. In particular, in the generic setting, algorithms have been proposed to compute the flow complex--the stable and unstable manifolds associated to the critical points of the distance function to a point set. As algorithms ignoring degenerate cases and numerical issues are bound to fail on general inputs, this paper develops the first complete and robust algorithm to compute the flow complex.

Surfaces of R 3 are ubiquitous in science and engineering, and estimating the local differential properties of a surface discretized as a point cloud or a triangle mesh is a central building block in computer graphics, computer aided design, computational geometry, and computer vision. One strategy to perform such an estimation consists of resorting to polynomial fitting, either interpolation or approximation, but this route is difficult for several reasons: choice of the coordinate system, numerical handling of the fitting problem, and extraction of the differential properties. This article presents a generic C++ software package solving these problems. On the theoretical side and as established in a companion paper, the interpolation and approximation methods provided achieve the best asymptotic error bounds known to date. On the implementation side and following state-of-the-art coding rules in computational geometry, genericity of the package is achieved thanks to four template classes accounting for, (a) the type of the input points, (b) the internal geometric computations, (c) a conversion mechanism between these two geometries, and (d) the linear algebra operations. An instantiation within the Computational Geometry Algorithms Library (CGAL, version 3.3) and using LAPACK is also provided.

The Bentley-Ottmann (BO) algorithm, initially designed to report theintersection points of line-segments in the plane, is the prototypicalsweep-line algorithm. This video presents an extension of the BOalgorithm to the spherical setting, so as to compute the exactarrangement of a collection of circles on a sphere.An application in bio-chemistry, geared towards the investigation ofatomic environments and multi-body interactions in macro-molecules, isalso presented.The reader is referred toRef. [1] for the companion paper of this video.

Docking is the process by which two or several molecules form a complex. Docking involves the geometry of the molecular surfaces, as well as chemical and energetical considerations. In the mid-eighties, Connolly proposed a docking algorithm matching surface knobs with surface depressions. Knobs and depressions refer to the extrema of the Connolly function, which is defined as follows. Given a surface M bounding a three-dimensional domain X, and a sphere S centered at a point p of M, the Connolly function is equal to the solid angle of the portion of S containing within X.We recast the notions of knobs and depressions in the framework of Morse theory for functions defined over two-dimensional manifolds. First, we study the critical points of the Connolly function for smooth surfaces. Second, we provide an efficient algorithm for computing the Connolly function over a triangulated surface. Third, we introduce a Morse-Smale decomposition based on Forman's discrete Morse theory, and provide an O(n log n) algorithm to construct it. This decomposition induces a partition of the surface into regions of homogeneous flow, and provides an elegant way to relate local quantities to global ones--from critical points to Euler's characteristic of the surface. Fourth, we apply this Morse-Smale decomposition to the discrete gradient vector field induced by Connolly's function, and present experimental results for several mesh models.

This paper addresses the pointwise estimation of differential properties of a smooth manifold S -a curve in the plane or a surface in 3D- assuming a point cloud sampled over S is provided. The method consists of fitting the local representation of the manifold using a jet, by either interpolating or approximating. A jet is a truncated Taylor expansion, and the incentive for using jets is that they encode all local geometric quantities - such as normal or curvatures. On the way to using jets, the question of estimating differential properties is recasted into the more general framework of multivariate interpolation/approximation, a well-studied problem in numerical analysis. On a theoretical perspective, we prove several convergence results when the samples get denser. For curves and surfaces, these results involve asymptotic estimates with convergence rates depending upon the degree of the jet used. For the particular case of curves, an error bound is also derived. To the best of our knowledge, these results are among the first ones providing accurate estimates for differential quantities of order three and more. On the algorithmic side, we solve the interpolation/approximation problem using Vandermonde systems. Experimental results for surfaces of R3 are reported. These experiments illustrate the asymptotic convergence results, but also the robustness of the methods on general Computer Graphics models.

Let PC be a 3D point cloud and ε be a positive value called tolerance. We aim at constructing a triangulated surface S based on a subset PCU of PC such that all the points in PCL=PC∖PCU are at distance at most ε from a facet of S. (PCU and PCL respectively stand for Point Cloud Used and Point Cloud Left.) We call this problem simplification with geometric guarantees. This paper presents a new framework to simplify with geometric guarantees. The approach relies on two main ingredients. First an oracle providing information on the surface being reconstructed even though the triangulated surface itself has not been computed. Second, a reconstruction algorithm providing incremental updates of the reconstructed surface, as well as a fast point-to-triangles distance computation. The oracle is used to guess a subset of the point cloud from which a triangulated surface is reconstructed. It relies on an implicit surface the triangulated surface is an approximation of, and is therefore available before the triangle mesh. The point-to-triangles distance computation and the local updates are then invoked to insert new vertices until the tolerance is met. We also present a detailed experimental study which shows the efficiency of the simplification process both in terms of simplification rate and running time. To the best of our knowledge, this algorithm is the first one performing coarse-to-fine surface simplification with geometric guarantees.

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganised sample points and normals. The method uses natural neighbour interpolation, works in any dimension and allows to deal with non uniform samples. The reconstructed surface is a smooth manifold passing through all the sample points. This surface is implicitly represented as the zero-set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound. Experimental results are presented for surfaces in R^3.

No abstract available.

Article Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering Share on Author: F. Cazals Algorithms project, INRIA Rocquencourt, F-78153 Le Chesnay and Prisme project, INRIA Sophia, F-06902 Sophia-Antipolis Algorithms project, INRIA Rocquencourt, F-78153 Le Chesnay and Prisme project, INRIA Sophia, F-06902 Sophia-AntipolisView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 222–230https://doi.org/10.1145/276884.276910Online:07 June 1998Publication History 4citation342DownloadsMetricsTotal Citations4Total Downloads342Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Data structures baaed on uniform subdivisions of the space ---&o known as bucketing-have the nice properties that they can be walked through very easily and can provide neighborhood relations at low cost.For data sets which are uniformly scattered in 2D or 3D space, this makes the imple- mentation of algorithms such as ray tracing, nearest neighbors computation or Delaunay triangulation almost trivial.But should the processed data set admit dense clusters, the spatial partitioning does not result in data partitioning so that the performzmces are collapsing.Although it has been known for a long time in dimension one that recursive bucket-sort admits a linear complexity for a wide rage of probability densities, recursive bucketlike data structures have not received any attention in the computational geometry community.It has been observed in computer graphics that these were the fastest to ray-trace, but the question of understanding why they are not just another space partitioning data structure but rather the only data structure that succeeds in capturing the probabilistic properties of data distribution remains open.This paper is a first step in this direction and investigates hierarchical recursive and non recursive data structures for ray-tracing.First, we show that precisely analyzing an optimized ray-tracer is a difficult task due to the context sensitivity of the calls costs of the functions called most often.Second, we exhibit statistics showing that if uniform grids are definitely not the right data structure to use for non-uniform dktributions, recursive grids are very good at handling such distributions.Third, we present several improvements of the Hierarchy of Uniform Grids data structure, which result for the best cases in running times improved by up to a factor three with reference to the previously best known solution.

This paper analyzes the variations of the relative positions of the parts composing an assembly when part dimensions span their specified tolerance zones. We focus on the simplified case where each part is modeled as a toleranced polygon defined as follows: each edge of this polygon is supported by a line of fixed orientation lying anywhere in a strip bounded by two extreme lines; these lines are themselves defined in a coordinate system attached to the part. The relative placements of parts in an assembly A are defined by spatial relations, such as edge e of part P is parallel to edge f of part Q, at distance d. We define the relative position of any two parts, P and Q, in an instance of A as the transform (a translation in our case) between the coordinate systems attached to these parts. Because of the possible variations in the geometry of each individual part, the relative position of P and Q is not constant over multiple instances of A. Hence, the question: what is the range of possible relative positions of any two parts in A? This paper describes an efficient algorithm to solve this problem. Experimental results obtained with an assembly sequence planner that incorporates this algorithm are also presented.

The goal of assembly sequencing is to plan a feasible series of operations to construct a product from its individual parts. Previous research has investigated assembly sequencing under the assumption that parts have nominal geometry. This paper considers the case where parts have toleranced geometry. Its main contribution is an efficient procedure that decides if a product admits an assembly sequence with infinite translations (i.e. translations that can be extended arbitrarily far along a fixed direction), that is feasible for all possible instances of the components within the specified tolerances. If the product admits one such sequence, the procedure can also generate it. For the cases where there exists no such assembly sequence, another procedure is proposed which generates assembly sequences that are feasible only for some values of the toleranced dimensions. If this procedure produces no such sequence, then no instance of the product is assemblable. These two procedures are described for 2D assemblies made of polygonial parts and for 3D assemblies made of polyhedral parts. So far, only the first has been implemented (for the planar case). This work assumes a simple, but non-trivial tolerance language that falls short of capturing all imperfections of a manufacturing process. In particular, it assumes that faces and edges have perfect relative orientations. Thus, it is only one step towards dealing with tolerances in assembly sequencing.

Abstract Data structures that handle very complex scenes (hundreds of thousands of objects) have in the past either been laboriously built by hand, or have required the determination of unintuitive parameter values by the user. It is often the case that an incorrect choice of these parameters can result in greedy memory requirements or severely degraded performance. As a remedy to this problem we propose a new data structure which is fully automatic since it does not require the user to determine any input parameters. The structure is built by first filtering the input objects by size, subsequently applying a clustering step to objects of the same size and finally building a hierarchy of uniform grids . We then show that this data structure can be efficiently constructed. The implementation of the shows that the new structure is stable since it's memory requirements grow linearly with the size of the scene, and that it presents a satisfactory compromise between memory usage and computational efficiency. A detailed comparison with previous data structures is also presented in the results.