A key property of the Delaunay filtration is that it is topologically (i.e., weakly) equivalent to the offset (union-of-balls) filtration. Recently, this filtration has been extended to point clouds equipped with an ℝ-valued function, yielding a computable 2-parameter filtration that satisfies an analogous weak equivalence. Motivated in part by the study of time-varying data, we introduce a 3-parameter extension of the Delaunay filtration for point clouds equipped with an ℝ²-valued function, also satisfying an analogous weak equivalence. For a point cloud X ⊂ ℝ^d, our trifiltration has size O(|X|^{⌈(d+1)/2⌉+1}). We present an algorithm that computes this trifiltration in time O(|X|^{⌈d/2⌉+2}), together with an implementation. Our experiments demonstrate that the implementation can handle thousands of points in ℝ³, with memory growth that is nearly linear.

The Persistent Homology Transform (PHT) summarizes a shape in ℝ^m by collecting persistence diagrams obtained from linear height filtrations in all directions on 𝕊^{m-1}. It enjoys strong theoretical guarantees, including continuity, stability, and injectivity. A natural way to compare two PHTs is to use the bottleneck distance between their diagrams as the direction varies. Prior work has either compared PHTs by sampling directions or, in 2D, computed the exact integral of bottleneck distance over all angles via a kinetic data structure. We improve the integral objective to Õ(n⁵) in place of the earlier Õ(n⁶) bound, where n denotes the number of simplices. For the max objective, we give an Õ(n³) expected-time algorithm in ℝ² and an Õ(n⁵) expected-time algorithm in ℝ³.

Dey and Xin (J.Appl.Comput.Top., 2022) describe an algorithm to decompose finitely presented multiparameter persistence modules using a matrix reduction algorithm. Their algorithm only works for modules whose generators and relations are distinctly graded. We extend their approach to work on all finitely presented modules and introduce several improvements that lead to significant speed-ups in practice. Our algorithm is fixed-parameter tractable with respect to the maximal number of relations of the same degree and with further optimisation we obtain an O(n³) time algorithm for interval-decomposable modules. In particular, we can decide interval-decomposability in this time. As a by-product to the proofs of correctness we develop a theory of parameter restriction for persistence modules. Our algorithm is implemented as a software library aida, the first to enable the decomposition of large inputs. We show its capabilities via extensive experimental evaluation.

Abstract We study the decomposition of zero-dimensional persistence modules, viewed as functors valued in the category of vector spaces factorizing through sets. Instead of working directly at the level of vector spaces, we take a step back and first study the decomposition problem at the level of sets. This approach allows us to define the combinatorial notion of rooted subsets . In the case of a filtered metric space M , rooted subsets relate the clustering behavior of the points of M with the decomposition of the associated persistence module. In particular, we can identify intervals in such a decomposition quickly. In addition, rooted subsets can be understood as a generalization of the elder rule, and are also related to the notion of constant conqueror of Cai, Kim, Mémoli and Wang. As an application, we give a lower bound on the number of intervals that we can expect in the decomposition of zero-dimensional persistence modules of a density-Rips filtration in Euclidean space: in the limit, and under very general circumstances, we can expect that at least 25% of the indecomposable summands are interval modules.

Multiparameter persistence modules can be uniquely decomposed into indecomposable summands. Among these indecomposables, intervals stand out for their simplicity, making them preferable for their ease of interpretation in practical applications and their computational efficiency. Empirical observations indicate that modules that decompose into only intervals are rare. To support this observation, we show that for numerous common multiparameter constructions, such as density- or degree-Rips bifiltrations, and across a general category of point samples, the probability of the homology-induced persistence module decomposing into intervals goes to zero as the sample size goes to infinity.

We introduce graphcodes, a novel multi-scale summary of the topological properties of a dataset that is based on the well-established theory of persistent homology. Graphcodes handle datasets that are filtered along two real-valued scale parameters. Such multi-parameter topological summaries are usually based on complicated theoretical foundations and difficult to compute; in contrast, graphcodes yield an informative and interpretable summary and can be computed as efficient as one-parameter summaries. Moreover, a graphcode is simply an embedded graph and can therefore be readily integrated in machine learning pipelines using graph neural networks. We describe such a pipeline and demonstrate that graphcodes achieve better classification accuracy than state-of-the-art approaches on various datasets.

The Delaunay filtration D.(X) of a point cloud X ⊂ ℝd is a central tool of computational topology. Its use is justified by the topological equivalence of D. (X) and the offset (i.e., union-of-balls) filtration of X. Given a function γ : X → ℝ, we introduce a Delaunay bifiltration DC.(γ) that satisfies an analogous topological equivalence, ensuring that DC. (γ) topologically encodes the offset filtrations of all sublevel sets of γ, as well as the topological relations between them. DC.(γ) is of size , which for d odd matches the worst-case size of D. (X). Adapting the Bowyer-Watson algorithm for computing Delaunay triangulations, we give a simple, practical algorithm to compute DC.(γ) in time Our implementation, based on CGAL, computes DC. (γ) with modest overhead compared to computing D. (X), and handles tens of thousands of points in ℝ3 within seconds.

For a finite set of balls of radius r , the k -fold cover is the space covered by at least k balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the k -fold filtration of the centers. For k =1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger k , it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the k -fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case k =1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points. Our method also extends to the multicover bifiltration, composed of the k -fold filtrations for several values of k , with the same size and complexity bounds.

Bifiltered graphs are a versatile tool for modelling relations between data points across multiple grades of a two- dimensional scale. They are especially popular in topological data analysis, where the homological properties of the induced clique complexes are studied. To reduce the large size of these clique complexes, we identify filtration-dominated edges of the graph, whose removal preserves the relevant topological properties. We give two algorithms to detect filtration-dominated edges in a bifiltered graph and analyze their complexity. These two algorithms work directly on the bifiltered graph, without first extracting the clique complexes, which are generally much bigger. We present extensive experimental evaluation which shows that in most cases, more than 90% of the edges can be removed. In turn, we demonstrate that this often leads to a substantial speedup, and reduction in the memory usage, of the computational pipeline of multiparameter topological data analysis.

We study the decomposition of zero-dimensional persistence modules, viewed as functors valued in the category of vector spaces factorizing through sets. Instead of working directly at the level of vector spaces, we take a step back and first study the decomposition problem at the level of sets. This approach allows us to define the combinatorial notion of rooted subsets. In the case of a filtered metric space $M$, rooted subsets relate the clustering behavior of the points of $M$ with the decomposition of the associated persistence module. In particular, we can identify intervals in such a decomposition quickly. In addition, rooted subsets can be understood as a generalization of the elder rule, and are also related to the notion of constant conqueror of Cai, Kim, Mémoli and Wang. As an application, we give a lower bound on the number of intervals that we can expect in the decomposition of zero-dimensional persistence modules of a density-Rips filtration in Euclidean space: in the limit, and under very general circumstances, we can expect that at least 25% of the indecomposable summands are interval modules.

For a finite set of balls of radius $r$, the $k$-fold cover is the space covered by at least $k$ balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the $k$-fold filtration of the centers. For $k=1$, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger $k$, it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the $k$-fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case $k=1$, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points. Our method also extends to the multicover bifiltration, composed of the $k$-fold filtrations for several values of $k$, with the same size and complexity bounds.

We propose an extension of the classical union-of-balls filtration of persistent homology: fixing a point $q$, we focus our attention to a ball centered at $q$ whose radius is controlled by a second scale parameter. We discuss an absolute variant, where the union is just restricted to the $q$-ball, and a relative variant where the homology of the $q$-ball relative to its boundary is considered. Interestingly, these natural constructions lead to bifiltered simplicial complexes which are not $k$-critical for any finite $k$. Nevertheless, we demonstrate that these bifiltrations can be computed exactly and efficiently, and we provide a prototypical implementation using the CGAL library. We also argue that some of the recent algorithmic advances for $2$-parameter persistence (which usually assume $k$-criticality for some finite $k$) carry over to the $\infty$-critical case.

Compression aims to reduce the size of an input, while maintaining its relevant properties. For multi-parameter persistent homology, compression is a necessary step in any computational pipeline, since standard constructions lead to large inputs, and computational tasks in this area tend to be expensive. We propose two compression methods for chain complexes of free 2-parameter persistence modules. The first method extends the multi-chunk algorithm for one-parameter persistent homology, returning the smallest chain complex among all the ones quasi-isomorphic to the input. The second method produces minimal presentations of the homology of the input; it is based on an algorithm of Lesnick and Wright, but incorporates several improvements that lead to substantial performance gains. The two methods are complementary, and can be combined to compute minimal presentations for complexes with millions of generators in a few seconds. The methods have been implemented, and the software is publicly available. We report on experimental evaluations, which demonstrate substantial improvements in performance compared to previously available compression strategies.

Abstract Given a finite set $$A\subset {\mathbb {R}}^d$$ A ⊂ R d , let $$\text {Cov}_{r,k}$$ Cov r , k denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.

We study the algorithmic complexity of computing persistent homology of a randomly chosen filtration. Specifically, we prove upper bounds for the average fill-up (number of non-zero entries) of the boundary matrix on Erdös-Rényi and Vietoris-Rips filtrations after matrix reduction. Our bounds show that, in both cases, the reduced matrix is expected to be significantly sparser than what the general worst-case predicts. Our method is based on a link between the fillup of the boundary matrix and expected Betti numbers of random filtrations. Our bound for Vietoris-Rips complexes is asymptotically tight up to logarithmic factors. We also provide an Erdös-Rényi filtration realising the worst-case.

Multi-parameter persistent homology is a recent branch of topological data analysis. In this area, data sets are investigated through the lens of homology with respect to two or more scale parameters. The high computational cost of many algorithms calls for a preprocessing step to reduce the input size. In general, a minimal presentation is the smallest possible representation of a persistence module. Lesnick and Wright [29] proposed recently an algorithm (the LW-algorithm) for computing minimal presentations based on matrix reduction. In this work, we propose, implement and benchmark several improvements over the LW-algorithm. Most notably, we propose the use of priority queues to avoid extensive scanning of the matrix columns, which constitutes the computational bottleneck in the LW-algorithm, and we combine their algorithm with ideas from the multi-parameter chunk algorithm by Fugacci and Kerber [21]. Our extensive experiments show that our algorithm outperforms the LW-algorithm and computes the minimal presentation for data sets with millions of simplices within a few seconds. Our software is publicly available.

In topological data analysis, the matching distance is a computationally tractable metric on multi-filtered simplicial complexes. We design efficient algorithms for approximating the matching distance of two bi-filtered complexes to any desired precision ε>0. Our approach is based on a quad-tree refinement strategy introduced by Biasotti et al., but we recast their approach entirely in geometric terms. This point of view leads to several novel observations resulting in a practically faster algorithm. We demonstrate this speed-up by experimental comparison and provide our code in a public repository which provides the first efficient publicly available implementation of the matching distance.

We give necessary and sufficient criteria for elementary operations in a two-dimensional terrain to preserve the persistent homology induced by the height function. These operations are edge flips and removals of interior vertices, re-triangulating the link of the removed vertex. This problem is motivated by topological terrain simplification, which means removing as many critical vertices of a terrain as possible while maintaining geometric closeness to the original surface. Existing methods manage to reduce the maximal possible number of critical vertices, but increase thereby the number of regular vertices. Our method can be used to post-process a simplified terrain, drastically reducing its size and preserving its favorable properties.

The extension of persistent homology to multi-parameter setups is an algorithmic challenge. Since most computation tasks scale badly with the size of the input complex, an important pre-processing step consists of simplifying the input while maintaining the homological information. We present an algorithm that drastically reduces the size of an input. Our approach is an extension of the chunk algorithm for persistent homology (Bauer et al., Topological Methods in Data Analysis and Visualization III, 2014). We show that our construction produces the smallest multi-filtered chain complex among all the complexes quasi-isomorphic to the input, improving on the guarantees of previous work in the context of discrete Morse theory. Our algorithm also offers an immediate parallelization scheme in shared memory. Already its sequential version compares favorably with existing simplification schemes, as we show by experimental evaluation.

The matching distance is a pseudometric on multi-parameter persistence modules, defined in terms of the weighted bottleneck distance on the restriction of the modules to affine lines. It is known that this distance is stable in a reasonable sense, and can be efficiently approximated, which makes it a promising tool for practical applications. In this work, we show that in the 2-parameter setting, the matching distance can be computed exactly in polynomial time. Our approach subdivides the space of affine lines into regions, via a line arrangement. In each region, the matching distance restricts to a simple analytic function, whose maximum is easily computed. As a byproduct, our analysis establishes that the matching distance is a rational number, if the bigrades of the input modules are rational.

Čech complexes are useful simplicial complexes for computing and analyzing topological features of data that lies in Euclidean space. Unfortunately, computing these complexes becomes prohibitively expensive for large-sized data sets even for medium-to-low dimensional data. We present an approximation scheme for (1 + ε)-approximating the topological information of the Čech complexes for n points in ℝd, for ε ∊ (0, 1]. Our approximation has a total size of for constant dimension d, improving all the currently available (1 + ε)-approximation schemes of simplicial filtrations in Euclidean space. Perhaps counter-intuitively, we arrive at our result by adding additional sample points to the input. We achieve a bound that is independent of the spread of the point set by pre-identifying the scales at which the Čech complexes changes and sampling accordingly.

Classical methods to model topological properties of point clouds, such as the Vietoris–Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in $$\mathbb {R}^d$$ , we obtain a O(d)-approximation whose k-skeleton has size $$n2^{O(d \log k)}$$ per scale and $$n2^{O(d\log d)}$$ in total over all scales. In conjunction with dimension reduction techniques, our approach yields a $$O(\mathrm {polylog} (n))$$ -approximation of size $$n^{O(1)}$$ for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximation: we construct a point set for which every $$(1+\varepsilon )$$ -approximation of the Čech filtration has to contain $$n^{\Omega (\log \log n)}$$ features, provided that $$\varepsilon <\frac{1}{\log ^{1+c} n}$$ for $$c\in (0,1)$$ .

A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG, 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.

Given a polytope P in R^d and a subset U of its vertices, is there a triangulation of P using d-simplices that all contain U? We answer this question by proving an equivalent and easy-to-check combinatorial criterion for the facets of P. Our proof relates triangulations of P to triangulations of its "shadow", a projection to a lower-dimensional space determined by U. In particular, we obtain a formula relating the volume of P with the volume of its shadow. This leads to an exact formula for the volume of a polytope arising in the theory of unit equations.

Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes constitutes an expensive task because of a combinatorial explosion in the complex size. For n points in R^d, we present a scheme to construct a 4.24-approximation of the multi-scale filtration of the Rips complex in the L-infinity metric, which extends to a O(d^{0.25})-approximation of the Rips filtration for the Euclidean case. The k-skeleton of the resulting approximation has a total size of n2^{O(d log k)}. The scheme is based on the integer lattice and on the barycentric subdivision of the d-cube.

Exploiting geometric structure to improve the asymptotic complexity of discrete assignment problems is a well-studied subject. In contrast, the practical advantages of using geometry for such problems have not been explored. We implement geometric variants of the Hopcroft–Karp algorithm for bottleneck matching (based on previous work by Efrat el al.), and of the auction algorithm by Bertsekas for Wasserstein distance computation. Both implementations use k-d trees to replace a linear scan with a geometric proximity query. Our interest in this problem stems from the desire to compute distances between persistence diagrams, a problem that comes up frequently in topological data analysis. We show that our geometric matching algorithms lead to a substantial performance gain, both in running time and in memory consumption, over their purely combinatorial counterparts. Moreover, our implementation significantly outperforms the only other implementation available for comparing persistence diagrams.

Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically – as long as the algorithm does not exhaust the available memory. Following up on a recently presented parallel method for persistence computation on shared memory systems [1], we demonstrate that a simple adaption of the standard reduction algorithm leads to a variant for distributed systems. Our algorithmic design ensures that the data is distributed over the nodes without redundancy; this permits the computation of much larger instances than on a single machine. Moreover, we observe that the parallelism at least compensates for the overhead caused by communication between nodes, and often even speeds up the computation compared to sequential and even parallel shared memory algorithms. In our experiments, we were able to compute the persistent homology of filtrations with more than a billion (109) elements within seconds on a cluster with 32 nodes using less than 6GB of memory per node.

Motivated by an application in cell biology, we describe an extension of the kinetic data structures framework from Delaunay triangulations to fixed-radius alpha complexes. Our algorithm is implemented using CGAL, following the exact geometric computation paradigm. We report on several techniques to accelerate the computation that turn our implementation applicable to the underlying biological problem.

We present a robust method for solving the map matching problem exploiting massive GPS trace data. Map matching is the problem of determining the path of a user on a map from a sequence of GPS positions of that user --- what we call a trajectory. Commonly obtained from GPS devices, such trajectory data is often sparse and noisy. As a result, the accuracy of map matching is limited due to ambiguities in the possible routes consistent with trajectory samples. Our approach is based on the observation that many regularity patterns exist among common trajectories of human beings or vehicles as they normally move around. Among all possible connected k-segments on the road network (i.e., consecutive edges along the network whose total length is approximately k units), a typical trajectory collection only utilizes a small fraction. This motivates our data-driven map matching method, which optimizes the projected paths of the input trajectories so that the number of the k-segments being used is minimized. We present a formulation that admits efficient computation via alternating optimization. Furthermore, we have created a benchmark for evaluating the performance of our algorithm and others alike. Experimental results demonstrate that the proposed approach is superior to state-of-art single trajectory map matching techniques. Moreover, we also show that the extracted popular k-segments can be used to process trajectories that are not present in the original trajectory set. This leads to a map matching algorithm that is as efficient as existing single trajectory map matching algorithms, but with much improved map matching accuracy.

In an urban setting, such as the city of Beijing, after a taxi driver drops the previous passenger, he/she needs to decide where to drive to find the next --- preferably lucrative --- passenger. Different drivers follow different strategies that are mostly based on personal experiences. In this work, we analyze large amounts of GPS location data of taxicabs to compute a high-level profit-maximizing strategy for taxi drivers. Formally, we model the problem of finding a passenger as a Markov Decision Process (MDP) whose parameters are estimated from the GPS data. For this MDP, we compute an optimal policy using dynamic programming. We show that the proposed strategy captures meaningful rules for finding a passenger and we demonstrate that taxi drivers whose behaviors agree with our proposal generate more profit than average drivers.

This note contributes to the point calculus of persistent homology by extending Alexander duality from spaces to real-valued functions. Given a perfect Morse function f: Sspacen+1 -> [0,1] and a decomposition Sspacen+1 = Uspace ∪ Vspace into two (n+1)-manifolds with common boundary Mspace, we prove elementary relationships between the persistence diagrams of f restricted to Uspace, to Vspace, and to Mspace.

We report on a generic uni- and bivariate algebraic kernel that is publicly available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art implementations on polynomials, roots of polynomial systems, and the support to analyze algebraic curves defined by bivariate polynomials. The kernel design is generic, that is, various number types and substeps can be exchanged. It is accompanied with a ready-to-use interface to enable arrangements induced by algebraic curves, that have already been used as basis for various geometric applications, as arrangements on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel applications: arrangements of rotated algebraic curves and Boolean set operations on polygons bounded by segments of algebraic curves. We also provide experiments showing that our general implementation is competitive and even often clearly outperforms existing implementations that are explicitly tailored for specific types of non-linear curves that are available in CGAL

We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm.

In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n x n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376) algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo algorithm for an arbitrary ε>0.

We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms.

We are interested in 3-dimensional images given as arrays of voxels with intensity values. Extending these values to a continuous function, we study the robustness of homology classes in its level and interlevel sets, that is, the amount of perturbation needed to destroy these classes. The structure of the homology classes and their robustness, over all level and interlevel sets, can be visualized by a triangular diagram of dots obtained by computing the extended persistence of the function. We give a fast hierarchical algorithm using the dual complexes of oct-tree approximations of the function. In addition, we show that for balanced oct-trees, the dual complexes are geometrically realized in R³ and can thus be used to construct level and interlevel sets. We apply these tools to study 3-dimensional images of plant root systems.

We present a method to compute the exact topology of a real algebraic surface S, implicitly given by a polynomial f ∈ Q[x;y;z] of arbitrary degree N. Additionally, our analysis provides geometric information as it supports the computation of arbitrary precise samples of S including critical points. We use a projection approach, similar to Collins' cylindrical algebraic decomposition (cad). In comparison we reduce the number of output cells to O(N5) by constructing a special planar arrangement instead of a full cad in the projection plane. Furthermore, our approach applies numerical and combinatorial methods to minimize costly symbolic computations. The algorithm handles all sorts of degeneracies without transforming the surface into a generic position. We provide a complete implementation of the algorithm, written in C++. It shows good performance for many well known examples from algebraic geometry.

A web application is presented to compute, plot, and interactively explore planar arrangements induced by algebraic plane curves of arbitrary degree. It produces accurate curve plots and reflects the exact topology for any arrangement, including degenerated cases. Various user interface features allow the interactive exploration of the arrangement structure. This makes the tool useful for demonstrative and educational purposes, especially as it runs without initial installation process.

An algorithm and implementation is presented to compute the exact arrangement induced by arbitrary algebraic surfaces on a parametrized ring dupin cyclide. The family of dupin cyclides contains as a special case the torus. The intersection of an algebraic surface of degree n with a reference cyclide is represented as a real algebraic curve of bi-degree (2n, 2n) in the two-dimensional parameter space of the cyclide. We use eigenwillig and kerber: "exact and efficient 2D-Arrangements of arbitrary algebraic Curves", SODA 2008, to compute a planar arrangement of such curves and extend their approach to obtain more asymptotic information about curves approaching the boundary of the cyclide's parameter space. With that, we can base our implementation on the general software framework by berberich et. al.: "sweeping and maintaining two-dimensional arrangements on surfaces: A first Step", ESA 2007. Our contribution provides the demanded techniques to model the special geometry of surfaces intersecting a cyclide and the special topology of the reference surface of genus one. The contained implementation is complete and does not assume generic position. Our experiments show that the combinatorial overhead of the framework does not harm the efficiency of the method. Our experiments show that the overall performance is strongly coupled to the efficiency of the implementation for arrangements of algebraic plane curves.

An algorithm is presented for the geometric analysis of an algebraic curve f(x, y) = 0 in the real affine plane. It computes a cylindrical algebraic decomposition (CAD) of the plane, augmented with adjacency information. The adjacency information describes the curve's topology by a topologically equivalent planar graph. The numerical data in the CAD gives an embedding of the graph.