Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions

Algorithms are developed, based on topological principles, to evaluate the boundary and “internal structure” of the Minkowski sum of two planar curves. A graph isotopic to the envelope curve is constructed by computing its characteristic points. The edges of this graph are in one-to-one correspondence with a set of monotone envelope segments. A simple formula allows a degree   to be assigned to each face defined by the graph, indicating the number of times its points are covered by the Minkowski sum. The boundary can then be identified with the set of edges that separate faces of zero and non-zero degree, and the boundary segments corresponding to these edges can be approximated to any desired geometrical accuracy. For applications that require only the Minkowski sum boundary, the algorithm minimizes geometrical computations on the “internal” envelope edges, that do not contribute to the final boundary. In other applications, this internal structure is of interest, and the algorithm provides comprehensive information on the covering degree for different regions within the Minkowski sum. Extensions of the algorithm to the computation of Minkowski sums in R³${\mathbb{R}}^3$, and other forms of geometrical convolution, are briefly discussed.     

Digital planarity—A review

Digital planarity is defined by digitizing Euclidean planes in the three-dimensional digital space of voxels; voxels are given either in the grid-point or the grid-cube model. The paper summarizes results (also including most of the proofs) about different aspects of digital planarity, such as supporting or separating Euclidean planes, characterizations in arithmetic geometry, periodicity, connectivity, and algorithmic solutions. The paper provides a uniform presentation, which further extends and details a recent book chapter in [R. Klette, A. Rosenfeld, Digital Geometry—Geometric Methods for Digital Picture Analysis, Morgan Kaufmann, San Francisco, 2004].     

The numerical stability of evaluation schemes for polynomials based on the lagrange interpolation form

For evaluation schemes based on the Lagrangian form of a polynomial with degreen, a rigorous error analysis is performed, taking into account that data, computation and even the nodes of interpolation might be perturbed by round-off. The error norm of the scheme is betweenn ² andn ²+(3n+7) _n , where _n denotes the Lebesgue constant belonging to the nodes. Hence, the error norm is of least possible orderO(n ²) if, for instance, the nodes are chosen to be the Chebyshev points or the Fekete points.     

An axiomatic approach to scalar data interpolation on surfaces

We discuss possible algorithms for interpolating data given on a set of curves in a surface of ℝ³. We propose a set of basic assumptions to be satisfied by the interpolation algorithms which lead to a set of models in terms of possibly degenerate elliptic partial differential equations. The Absolutely Minimizing Lipschitz Extension model (AMLE) is singled out and studied in more detail. We study the correctness of our numerical approach and we show experiments illustrating the interpolation of data on some simple test surfaces like the sphere and the torus.     

Pythagorean-hodograph preserving mappings

We study the scaled Pythagorean-hodograph (PH) preserving mappings. These mappings make offset-rational isothermal surfaces and map PH curves to PH curves. We present a method to produce a great number of the scaled PH preserving mappings. For an application of the PH preserving mappings, we solve the Hermite interpolation problem for PH curves in the space.     

An algorithm for the finite difference approximation of derivatives with arbitrary degree and order of accuracy

In this paper, we introduce an algorithm and a computer code for numerical differentiation of discrete functions. The algorithm presented is suitable for calculating derivatives of any degree with any arbitrary order of accuracy over all the known function sampling points. The algorithm introduced avoids the labour of preliminary differencing and is in fact more convenient than using the tabulated finite difference formulas, in particular when the derivatives are required with high approximation accuracy. Moreover, the given Matlab computer code can be implemented to solve boundary-value ordinary and partial differential equations with high numerical accuracy. The numerical technique is based on the undetermined coefficient method in conjunction with Taylor’s expansion. To avoid the difficulty of solving a system of linear equations, an explicit closed form equation for the weighting coefficients is derived in terms of the elementary symmetric functions. This is done by using an explicit closed formula for the Vandermonde matrix inverse. Moreover, the code is designed to give a unified approximation order throughout the given domain. A numerical differentiation example is used to investigate the validity and feasibility of the algorithm and the code. It is found that the method and the code work properly for any degree of derivative and any order of accuracy.     

Fast and accurate interpolation of large scattered data sets on the sphere

In this paper a new efficient algorithm for spherical interpolation of large scattered data sets is presented. The solution method is local and involves a modified spherical Shepard’s interpolant, which uses zonal basis functions as local approximants. The associated algorithm is implemented and optimized by applying a nearest neighbour searching procedure on the sphere. Specifically, this technique is mainly based on the partition of the sphere in a suitable number of spherical zones, the construction of spherical caps as local neighbourhoods for each node, and finally the employment of a spherical zone searching procedure. Computational cost and storage requirements of the spherical algorithm are analyzed. Moreover, several numerical results show the good accuracy of the method and the high efficiency of the proposed algorithm.     

Filtrations induced by continuous functions

In Persistent Homology and Topology, filtrations are usually given by introducing an ordered collection of sets or a continuous function from a topological space to Rⁿ${\mathbb{R}}^n$. A natural question arises, whether these approaches are equivalent or not. In this paper we study this problem and prove that, while the answer to the previous question is negative in the general case, the approach by continuous functions is not restrictive with respect to the other, provided that some natural stability and completeness assumptions are made. In particular, we show that every compact and stable 1-dimensional filtration of a compact metric space is induced by a continuous function. Moreover, we extend the previous result to the case of multi-dimensional filtrations, requiring that our filtration is also complete. Three examples show that we cannot drop the assumptions about stability and completeness. Consequences of our results on the definition of a distance between filtrations are finally discussed.     

Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights

The nonsymmetric Lanczos algorithm reduces a general matrix to tridiagonal by generating two sequences of vectors which satisfy a mutual bi-orthogonality property. The process can proceed as long as the two vectors generated at each stage are not mutually orthogonal, otherwise the process breaks down. In this paper, we propose a variant that does not break down by grouping the vectors into clusters and enforcing the bi-orthogonality property only between different clusters, but relaxing the property within clusters. We show how this variant of the matrix Lanczos algorithm applies directly to a problem of computing a set of orthogonal polynomials and associated indefinite weights with respect to an indefinite inner product, given the associated moments. We discuss the close relationship between the modified Lanczos algorithm and the modified Chebyshev algorithm. We further show the connection between this last problem and checksum-based error correction schemes for fault-tolerant computing.The research reported by this author was supported in part by NSF grant CCR-8813493.The research reported by this author was supported in part by ARO grant DAAL03-90-G-0105 and in part by NSF grant DCR-8412314.     

A remark on fixed points of functors in topological categories

For a topological category over Set we prove that if a functor T: has a fixed cardinal (i.e. for each object K with card (UK)= we have card (UTK)), then T has a least fixed point, and if T has a successive pair of fixed cardinals and ⁺, then T has a greatest fixed point. This extends results of Adámek and Koubek.Partial financial support of the Grant Agency of the Czech Republic under Grant No. 201/93/0950 is gratefully acknowledged.     

Fast algorithms for greedy triangulation

We present the first quadratic-time algorithm for the greedy triangulation of a finite planar point set, and the first linear-time algorithm for the greedy triangulation of a convex polygon.     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

Multilevel Monte Carlo simulation for Lévy processes based on the Wiener–Hopf factorisation

In Kuznetsov et al. (2011) a new Monte Carlo simulation technique was introduced for a large family of Lévy processes that is based on the Wiener–Hopf decomposition. We pursue this idea further by combining their technique with the recently introduced multilevel Monte Carlo methodology. Moreover, we provide here for the first time a theoretical analysis of the new Monte Carlo simulation technique in Kuznetsov et al. (2011) and of its multilevel variant for computing expectations of functions depending on the historical trajectory of a Lévy process. We derive rates of convergence for both methods and show that they are uniform with respect to the “jump activity” (e.g. characterised by the Blumenthal–Getoor index). We also present a modified version of the algorithm in Kuznetsov et al. (2011) which combined with the multilevel methodology obtains the optimal rate of convergence for general Lévy processes and Lipschitz functionals. This final result is only a theoretical one at present, since it requires independent sampling from a triple of distributions which is currently only possible for a limited number of processes.     

A fast algorithm for solving diagonally dominant symmetric pentadiagonal Toeplitz systems

Banded Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Recently, significant advancement has been made in algorithm development of fast parallel scalable methods to solve tridiagonal Toeplitz problems. In this paper we will derive a new algorithm for solving symmetric pentadiagonal Toeplitz systems of linear equations based upon a technique used in [J.M. McNally, L.E. Garey, R.E. Shaw, A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Int. J. Comput. Math. 75 (2000) 303-313] for tridiagonal Toeplitz systems. A common example which arises in natural quintic spline problems will be used to demonstrate the algorithm’s effectiveness. Finally computational results and comparisons will be presented.     

A communication-less parallel algorithm for tridiagonal Toeplitz systems

Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations.     

Blowing up: application to $G^2$-continuous 8-sided filling patch

Summary. We propose a method for filling a n-sided hole, , that interpolates n connected boundary curves of a given net of patches. This method allows the joining with patches defined in many different ways. A new class of blowing up pole-functions is introduced in order to build a G-continuous n-sided filling surface. This filling surface is in one piece, image of . Received February 21, 2000 / Revised version received January 2, 2001 / Published online December 18, 2001     

Geodesics in CAT(0) cubical complexes

We describe an algorithm to compute the geodesics in an arbitrary CAT(0) cubical complex. A key tool is a correspondence between cubical complexes of global non-positive curvature and posets with inconsistent pairs. This correspondence also gives an explicit realization of such a complex as the state complex of a reconfigurable system, and a way to embed any interval in the integer lattice cubing of its dimension.     

Digital Jordan curves

A digital Jordan curve theorem is proved for a new topology defined on Z². This topology is compared with the classical Khalimsky and Marcus topologies used in digital topology. We show that the Jordan curves with respect to the topology defined, unlike the Jordan curves with respect to any of the two classical topologies mentioned, may turn at the acute angle . We also discuss a quotient topology of the new topology.