Harmonic Embeddings for Linear Shape Analysis

We present a novel representation of shape for closed contours in ℝ² or for compact surfaces in ℝ³ explicitly designed to possess a linear structure. This greatly simplifies linear operations such as averaging, principal component analysis or differentiation in the space of shapes when compared to more common embedding choices such as the signed distance representation linked to the nonlinear Eikonal equation. The specific choice of implicit linear representation explored in this article is the class of harmonic functions over an annulus containing the contour. The idea is to represent the contour as closely as possible by the zero level set of a harmonic function, thereby linking our representation to the linear Laplace equation. We note that this is a local represenation within the space of closed curves as such harmonic functions can generally be defined only over a neighborhood of the embedded curve. We also make no claim that this is the only choice or even the optimal choice within the class of possible linear implicit representations. Instead, our intent is to show how linear analysis of shape is greatly simplified (and sensible) when such a linear representation is employed in hopes to inspire new ideas and additional research into this type of linear implicit representations for curves. We conclude by showing an application for which our particular choice of harmonic representation is ideally suited.     

Two-Grid Discontinuous Galerkin Method for Quasi-Linear Elliptic Problems

In this paper, we consider the symmetric interior penalty discontinuous Galerkin (SIPG) method with piecewise polynomials of degree r≥1 for a class of quasi-linear elliptic problems in Ω⊂ℝ². We propose a two-grid approximation for the SIPG method which can be thought of as a type of linearization of the nonlinear system using a solution from a coarse finite element space. With this technique, solving a quasi-linear elliptic problem on the fine finite element space is reduced into solving a linear problem on the fine finite element space and solving the quasi-linear elliptic problem on a coarse space. Convergence estimates in a broken H ¹-norm are derived to justify the efficiency of the proposed two-grid algorithm. Numerical experiments are provided to confirm our theoretical findings. As a byproduct of the technique used in the analysis, we derive the optimal pointwise error estimates of the SIPG method for the quasi-linear elliptic problems in ℝ ^d ,d=2,3 and use it to establish the convergence of the two-grid method for problems in Ω⊂ℝ³.     

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

The diameter of a set P of n points in ℝ ^d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure of this polytope is given, we prove that, in the worst case, deciding whether the diameter of P is smaller than 1 requires Ω(nlog n) time in the algebraic computation tree model. It shows that the O(nlog n) time algorithm of Ramos for computing the diameter of a point set in ℝ³ is optimal for computing the diameter of a 3-polytope. We also give a linear time reduction from Hopcroft’s problem of finding an incidence between points and lines in ℝ² to the diameter problem for a point set in ℝ⁷.     

Edge Detection by Adaptive Splitting

In this paper we propose an algorithm (EDAS-d) to approximate the jump discontinuity set of functions defined on subsets of ℝ ^d . We have limited our study to the 1D (EDAS-1) and 2D (EDAS-2) versions of the algorithm. Theoretical and computational results prove its effectiveness in the case of piecewise continuous 1D functions and piecewise constant 2D functions. The algorithm is based on adaptive splitting of the domain of the function guided by the value of an average integral. EDAS-d exhibits a number of attractive features: accurate determination of the jump points, fast processing, absence of oscillatory behavior, precise determination of the magnitude of the jumps, and ability to differentiate between real jumps (discontinuities) and steep gradients. Moreover, low-dimensional versions of EDAS-d can be used for solving higher dimensional problems. Computational experiments also show that EDAS-d can be applied to solve some problems involving general piecewise continuous functions. EDAS-1 and EDAS-2 have been used to determine edges in 2D-images. The results are quite satisfactory for practical purposes.     

Homotopy-based surface reconstruction with application to?acoustic signals

This work introduces a new algorithm for surface reconstruction in ℝ³ from spatially arranged one-dimensional cross sections embedded in ℝ³. This is generally the case with acoustic signals that pierce an object non-destructively. Continuous deformations (homotopies) that smoothly reconstruct information between any pair of successive cross sections are derived. The zero level set of the resulting homotopy field generates the desired surface. Four types of homotopies are suggested that are well suited to generate a smooth surface. We also provide derivation of necessary higher order homotopies that can generate a C ² surface. An algorithm to generate surface from acoustic sonar signals is presented with results. Reconstruction accuracies of the homotopies are compared by means of simulations performed on basic geometric primitives.     

Implicitization and parametrization of quadratic and cubic surfaces by μ-bases

Parametric and implicit forms are two common representations of geometric objects. It is important to be able to pass back and forth between the two representations, two processes called parameterization and implicitization, respectively. In this paper, we study the parametrization and implicitization of quadrics (quadratic parametric surfaces with two base points) and cubic surfaces (cubic parametric surfaces with six base points) with the help of μ-bases – a newly developed tool which connects the parametric form and the implicit form of a surface. For both cases, we show that the minimal μ-bases are all linear in the parametric variables, and based on this observation, very efficient algorithms are devised to compute the minimal μ-bases either from the parametric equation or the implicit equation. The conversion between the parametric equation and the implicit equation can be easily accomplished from the minimal μ-bases.     

Dynamic Delaunay tetrahedralisation of a deforming surface

Reconstruction algorithms make it possible to retrieve a surface from the Delaunay tetrahedralisation (DT) of a point sampling, whose density reflects the surface local geometry and thickness. Most of these algorithms are static and some work remains to be done to handle deforming surfaces. In such case, we defend the idea that each point of the sampling should move with the surface using the information given by the motion to allow fast reconstruction. In this article, we tackle the problem of producing a good evolving sampling of a deforming surface S, and maintaining its DT along the motion. The surface is known only through a projection operator (O ₁):ℝ³→S, and a normal operator (O ₂) that returns the oriented normal at a point on the surface. On that basis, we offer some perspectives on how reconstruction algorithms can be extended to the tracking of deforming surfaces.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

The normalform of a space curve and its application to surface design

x )=0 with ∥▿h∥=1. The normalform function h is (unlike the latter cases) not differentiable at curve points. Despite of this disadvantage the normalform is a suitable tool for designing surfaces which can be treated as common implicit surfaces. Many examples (bisector surfaces, constant distance sum/product surfaces, metamorphoses, blending surfaces, smooth approximation surfaces) demonstrate applications of the normalform to surface design. Published online: 25 July 2001     

The conformal alpha shape filtration

Conformal alpha shapes are a new filtration of the Delaunay triangulation of a finite set of points in ℝ^d. In contrast to (ordinary) alpha shapes the new filtration is parameterized by a local scale parameter instead of the global scale parameter in alpha shapes. The local scale parameter conforms to the local geometry and is motivated from applications and previous algorithms in surface reconstruction. We show how conformal alpha shapes can be used for surface reconstruction of non-uniformly sampled surfaces, which is not possible with alpha shapes.     

Two-level methods for the single layer potential in ℝ3

We consider weakly singular integral equations of the first kind on open surface pieces Γ in ℝ³. To obtain approximate solutions we use theh-version Galerkin boundary element method. Furthermore we introduce two-level additive Schwarz operators for non-overlapping domain decompositions of Γ and we estimate the conditions numbers of these operators with respect to the mesh size. Based on these operators we derive an a posteriori error estimate for the difference between the exact solution and the Galerkin solution. The estimate also involves the error which comes from an approximate solution of the Galerkin equations. For uniform meshes and under the assumption of a saturation condition we show reliability and efficiency of our estimate. Based on this estimate we introduce an adaptive multilevel algorithm with easily computable local error indicators which allows direction control of the local refinements. The theoretical results are illustrated by numerical examples for plane and curved surfaces. Supported by the German Research Foundation (DFG) under grant Ste 238/25-9.     

Piercing Translates and Homothets of a Convex Body

According to a classical result of Grünbaum, the transversal number τ(ℱ) of any family ℱ of pairwise-intersecting translates or homothets of a convex body C in ℝ ^d is bounded by a function of d. Denote by α(C) (resp. β(C)) the supremum of the ratio of the transversal number τ(ℱ) to the packing number ν(ℱ) over all finite families ℱ of translates (resp. homothets) of a convex body C in ℝ ^d . Kim et al. recently showed that α(C) is bounded by a function of d for any convex body C in ℝ ^d , and gave the first bounds on α(C) for convex bodies C in ℝ ^d and on β(C) for convex bodies C in the plane.     

Solutions to the generalized Sylvester matrix equations by a singular value decomposition

In this paper,solutions to the generalized Sylvester matrix equations AX-XF=BY and MXN-X=TY with A,M∈Rn×n,B,T∈Rn×n,F,N∈Rp×p and the matrices N,F being in companion form,are established by a singular value decomposition of a matrix with dimensions n×(n pr).The algorithm proposed in this paper for the euqation AX-XF=BY does not require the controllability of matrix pair(A,B)andthe restriction that A,F do not have common eigenvalues.Since singular value decomposition is adopted,the algorithm is numerically stable and may provide great convenience to the computation of the solution to these equations,and can perform important functions in many design problems in control systems theory.     

Smooth multiple B-spline surface fitting with Catmull%ndash;Clark subdivision surfaces for extraordinary corner patches

This paper presents an algorithm for simultaneously fitting smoothly connected multiple surfaces from unorganized measured data. A hybrid mathematical model of B-spline surfaces and Catmull–Clark subdivision surfaces is introduced to represent objects with general quadrilateral topology. The interconnected multiple surfaces are G ² continuous across all surface boundaries except at a finite number of extraordinary corner points where G ¹ continuity is obtained. The algorithm is purely a linear least-squares fitting procedure without any constraint for maintaining the required geometric continuity. In case of general uniform knots for all surfaces, the final fitted multiple surfaces can also be exported as a set of Catmull–Clark subdivision surfaces with global C ² continuity and local C ¹ continuity at extraordinary corner points. Published online: 14 May 2002 Correspondence to: W. Ma     

On the convergence rate of two projection methods for variational inequalities in ℝ n

This paper presents a study on the convergence rate of two projection methods for solving the variational inequality problemh∈K, 〈C(h),f-h〉 ≥ 0, ∀f∈K, whereK is a closed convex subset of ℝ ⁿ ,C is a mapping fromK to ℝ ⁿ and <.,.> denotes the inner product in ℝ ⁿ . The first method, proposed by Dafermos [6] for the case whenC is continuously differentiable and strongly monotone, generates a sequence{f ⁱ } inK which is geometrically convergent to the unique solutionh∈K of the variational inequality; i.e., there exists a constant λ≡]0,1[ such that for all i, ∥f ⁱ⁺¹ −h∥ _G ≤λ ∥f ⁱ −h∥, whereG is a symmetric positive definite matrix and ∀f≡ℝ ⁿ . The second method, proposed by Bertsekas and Gafni [8] for the case whenK is polyhedral andC is of the formC=A ⁱ TA, whereA is anm×n matrix andT: ℝ ^m →ℝ ^m is Lipschitz continuous and strongly monotone, generates a sequence{f ⁱ } inK which converges to a solutionh≡K of the variational inequality and satisfies the following estimate: ∥f ⁱ⁺¹ −h∥ _G ≤qβ ⁱ , whereq>0 and β≡]0,1[. We examine the dependence of the constants λ and β on the parameters of the methods and establish that, except for particular cases, these constants do not assume those values which guarantee a rapid convergence of the methods. This work was extracted from the degree thesis [9] (Supervisor: A Laratta), Dipartimento di Matematica, Università di Modena.     

Adaptive polygonization of geometrically constrained surfaces

n -dimensional space, where n>3. This definition can be used for given surfaces that are implicit or parametric. This paper presents a robust, adaptive polygonization algorithm for evaluating and visualizing geometrically constrained surfaces. Let be the constrained surface, a 2-surface in n-space, and let π() be its projection into the subspace spanned by the first three coordinates. Our polygonization algorithm computes π(). The method works directly with the n-space representation, but performs all major computations in 3-space. Techniques for triangulation, polygon decimation, and local refinement are also presented.     

Computing multiple pitchfork bifurcation points

A point (x*,λ*) is called apitchfork bifurcation point of multiplicityp≥1 of the nonlinear systemF(x, λ)=0,F:ℝⁿ×ℝ¹→ℝⁿ, if rank∂ _xF(x*, λ*)=n−1, and if the Ljapunov-Schmidt reduced equation has the normal formg(ξ, μ)=±ξ ²⁺ p±μξ=0. It is shown that such points satisfy a minimally extended systemG(y)=0,G:ℝ ⁿ⁺²→ℝⁿ⁺² the dimensionn+2 of which is independent ofp. For solving this system, a two-stage Newton-type method is proposed. Some numerical tests show the influence of the starting point and of the bordering vectors used in the definition of the extended system on the behavior of the iteration.     

Large Deformation Diffeomorphic Metric Curve Mapping

We present a matching criterion for curves and integrate it into the large deformation diffeomorphic metric mapping (LDDMM) scheme for computing an optimal transformation between two curves embedded in Euclidean space ℝ ^d . Curves are first represented as vector-valued measures, which incorporate both location and the first order geometric structure of the curves. Then, a Hilbert space structure is imposed on the measures to build the norm for quantifying the closeness between two curves. We describe a discretized version of this, in which discrete sequences of points along the curve are represented by vector-valued functionals. This gives a convenient and practical way to define a matching functional for curves. We derive and implement the curve matching in the large deformation framework and demonstrate mapping results of curves in ℝ² and ℝ³. Behaviors of the curve mapping are discussed using 2D curves. The applications to shape classification is shown and experiments with 3D curves extracted from brain cortical surfaces are presented. J. Glaunès and A. Qiu contributed equally to this work.     

Isometric Embeddings in Imaging and Vision: Facts and Fiction

We explore the practicability of Nash’s Embedding Theorem in vision and imaging sciences. In particular, we investigate the relevance of a result of Burago and Zalgaller regarding the existence of PL isometric embeddings of polyhedral surfaces in ℝ³ and we show that their proof does not extended directly to higher dimensions.     

An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions

We present a new streaming algorithm for maintaining an ε-kernel of a point set in ℝ ^d using O((1/ε ^(d−1)/2)log (1/ε)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension d ≥3) the best previous algorithm for this problem that uses O(1/ε ^d−(3/2)) space, presented by Agarwal and Yu. Our algorithm immediately improves the space complexity of the previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum-volume bounding box, minimum-radius enclosing cylinder, minimum-width enclosing annulus, etc.