Dataset Information

Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm.

ABSTRACT: We study the problem of decomposing a volume with a smooth boundary into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from weighted ?-shapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given a ?-sparse ?-sample, we work with the balls of radius ? times the local feature size centered at each sample. The corners of the union of these balls on both sides of the surface are the Voronoi sites and the interface of their cells is a watertight surface reconstruction embedded in the dual shape of the union of balls. With the surface protected, the enclosed volume can be further decomposed by generating more sites inside it. Compared to clipping-based algorithms, VoroCrust cells are full Voronoi cells, with convexity and fatness guarantees. Compared to the power crust algorithm, VoroCrust cells are not filtered, are unweighted, and offer greater flexibility in meshing the enclosed volume by either structured or randomly genenerated samples.

SUBMITTER: Abdelkader A

PROVIDER: S-EPMC6344055 | biostudies-literature | 2018 Jun

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm.

Abdelkader Ahmed A Bajaj Chandrajit L CL Ebeida Mohamed S MS Mahmoud Ahmed H AH Mitchell Scott A SA Rushdi Ahmad A AA Owens John D JD

LIPIcs : Leibniz international proceedings in informatics 20180601

We study the problem of decomposing a volume with a smooth boundary into a collection of Voronoi cells. Unlike the dual problem of conforming Delaunay meshing, a principled solution to this problem for generic smooth surfaces remained elusive. VoroCrust leverages ideas from weighted α-shapes and the power crust algorithm to produce unweighted Voronoi cells conforming to the surface, yielding the first provably-correct algorithm for this problem. Given a κ-sparse ε-sample, we ...[more]

PMID: 30687412

Similar Datasets

Project description:An RNA molecule, particularly a long-chain mRNA, may exist as a population of structures. Further more, multiple structures have been demonstrated to play important functional roles. Thus, a representation of the ensemble of probable structures is of interest. We present a statistical algorithm to sample rigorously and exactly from the Boltzmann ensemble of secondary structures. The forward step of the algorithm computes the equilibrium partition functions of RNA secondary structures with recent thermodynamic parameters. Using conditional probabilities computed with the partition functions in a recursive sampling process, the backward step of the algorithm quickly generates a statistically representative sample of structures. With cubic run time for the forward step, quadratic run time in the worst case for the sampling step, and quadratic storage, the algorithm is efficient for broad applicability. We demonstrate that, by classifying sampled structures, the algorithm enables a statistical delineation and representation of the Boltzmann ensemble. Applications of the algorithm show that alternative biological structures are revealed through sampling. Statistical sampling provides a means to estimate the probability of any structural motif, with or without constraints. For example, the algorithm enables probability profiling of single-stranded regions in RNA secondary structure. Probability profiling for specific loop types is also illustrated. By overlaying probability profiles, a mutual accessibility plot can be displayed for predicting RNA:RNA interactions. Boltzmann probability-weighted density of states and free energy distributions of sampled structures can be readily computed. We show that a sample of moderate size from the ensemble of an enormous number of possible structures is sufficient to guarantee statistical reproducibility in the estimates of typical sampling statistics. Our applications suggest that the sampling algorithm may be well suited to prediction of mRNA structure and target accessibility. The algorithm is applicable to the rational design of small interfering RNAs (siRNAs), antisense oligonucleotides, and trans-cleaving ribozymes in gene knock-down studies.

Dataset Information

Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm.

Publications

Sampling Conditions for Conforming Voronoi Meshing by the VoroCrust Algorithm.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets