The persistent homology transform, Betti function transform, and Euler characteristic transform represent a shape with a multiset of persistence diagrams, Betti functions, or Euler characteristic functions, respectively, parameterized by the sphere of directions in the ambient space. In this work, we give the first explicit construction of finite sets of directions discretizing the verbose variants of these transforms and show that such discretizations faithfully represent the underlying shape. Our discretization, while exponential in the dimension of the shape, does not depend on any restrictions on the particular immersion beyond general position, and is stable with respect to various perturbations.

Microorganisms make up most of the earth’s biomass, and most microbes exist in the form of biofilms, complex communities of microorganisms growing attached to surfaces. Biofilms are directly relevant to a large number of scientific disciplines, and are the subjects of growing multidisciplinary research. As such, there is a pressing requirement for information systems that specialize in biofilm knowledge. Realization of such systems will require a coherent approach to understanding and curating the language used to study biofilms; an ontology of biofilms-related terms offers a foundation for such systems. Here we present an ontology for the study of biofilms (BIFO), a tool that will provide precisely defined terms describing all aspects involved in the biofilms domain. We describe semi-automated methods for the identification of relevant terms from a body of literature, the selection of a set of important terms by domain experts, and the construction of the ontology. A generic approach for BIFO is presented, in which foundational biofilm-related entities and relationships are represented. This ontology reuses terms from other ontologies that provide biofilm knowledge from the Open Biological and Biomedical Ontologies (OBO) foundry.

Geometric algorithms use numerical computations to perform geometric tests, so correct algorithms may produce erroneous results if insufficient arithmetic precision is available. Liotta, Preparata, and Tamassia, in 1999, suggested that algorithm design, which traditionally considers running time and memory space, could also consider precision as a resource. They demonstrated that the Voronoi diagram of n sites on a U × U grid could be rounded to answer nearest neighbor queries on the same grid using only double precision. They still had to compute the Voronoi diagram before rounding, which requires the quadruple-precision InCircle test. We develop a "degree-2 Voronoi diagram" that can be computed using only double precision by a randomized incremental construction in O(n log n log U) expected time and O(n) expected space. Our diagram also answers nearest neighbor queries, even though it doesn't even use sufficient precision to determine a Delaunay triangulation.

Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The d-dimensional algorithms we describe are (a) spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangulations for mesh generation algorithms or simply computing Delaunay triangulations. We show experimental results for these algorithms in 3D, using our implementations based on the Computational Geometry Algorithms Library (CGAL, http://www.cgal.org/). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.