Detection of discontinuities in scattered data approximation

A Detection Algorithm for the localisation of unknown fault lines of a surface from scattered data is given. The method is based on a local approximation scheme using thin plate splines, and we show that this yields approximation of second order accuracy instead of first order as in the global case. Furthermore, the Detection Algorithm works with triangulation methods, and we show their utility for the approximation of the fault lines. The output of our method provides polygonal curves which can be used for the purpose of constrained surface approximation. This revised version was published online in June 2006 with corrections to the Cover Date.     

The flow complex: A data structure for geometric modeling

We study a special case of the critical point (Morse) theory of distance functions namely, the gradient flow associated with the distance function to a finite point set in . The fixed points of this flow are exactly the critical points of the distance function. Our main result is a mathematical characterization and algorithms to compute the stable manifolds, i.e., the inflow regions, of the fixed points. It turns out that the stable manifolds form a polyhedral complex that shares many properties with the Delaunay triangulation of the same point set. We call the latter complex the flow complex of the point set. The flow complex is suited for geometric modeling tasks like surface reconstruction.     

Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds

Ideas of a simplicial variable dimension restart algorithm to approximate zero points onR ⁿ developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solving the nonlinear complementarity problem with lower and upper bounds. The algorithm can be considered as a modification of the2n-ray zero point finding algorithm onR ⁿ . It appears that for the new algorithm the number of linear programming pivot steps is typically less than for the2n-ray algorithm applied to an equivalent zero point problem. This is caused by the fact that the algorithm utilizes the complementarity conditions on the variables. This work is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply,” which has been approved by the Netherlands Ministry of Education and Sciences.     

Geometric Analysis and Symbol Calculus: Fourier Transform Magnetic Resonance Imaging and Wavelets

Due to its unequalled advantages, the magnetic resonance imaging (MRI) modality has truly revolutionized the diagnosis and evaluation of pathology. Because many morphological anatomic details that may not be visualized by other high tech imaging methods can now be readily shown by diagnostic MRI, it has already become the standard modality by which all other clinical imaging techniques are measured. The unique quantum physical basis of the MRI modality combined with the imaging capabilities of current computer technology has made this imaging modality a target of interdisciplinary interest for clinicians, physicists, biologists, engineers, and mathematicians. Due to the fact that MRI scanners perform corticomorphic processing, this modality is by far more complex than all the other high tech clinical imaging techniques. The purpose of this paper is to outline a phase coherent wavelet approach to Fourier transform MRI. It is based on distributional harmonic analysis on the Heisenberg nilpotent Lie group G and the associated symplectically invariant symbol calculus of pseudodifferential operators. The contour and contrast resolution of MRI scans which is controlled by symplectic filter bank processing gives the noninvasive MRI modality superiority over X-ray computed tomography (CT) in soft tissue differentiation.     

Subdivision of simplices relative to a cutting plane and finite concave minimization

In this article, our primary concern is the classical problem of minimizing globally a concave function over a compact polyhedron (Problem (P)). We present a new simplicial branch and bound approach, which combines triangulations of intersections of simplices with halfspaces and ideas from outer approximation in such a way, that a class of finite algorithms for solving (P) results. For arbitrary compact convex feasible sets one obtains a not necessarily finite but convergent algorithm. Theoretical investigations include determination of the number of simplices in each applied triangulation step and bounds on the number of iterations in the resulting algorithms. Preliminary numerical results are given, and additional applications are sketched.     

Lp-based combinatorial problem solving

A tutorial outline of the polyhedral theory that underlies linear programming (LP)-based combinatorial problem solving is given. Design aspects of a combinatorial problem solver are discussed in general terms. Three computational studies in combinatorial problem solving using the polyhedral theory developed in the past fifteen years are surveyed: one addresses the symmetric traveling salesman problem, another the optimal triangulation of input/output matrices, and the third the optimization of large-scale zero-one linear programming problems.     

Grünbaum colorings of even triangulations on surfaces

A Grünbaum coloring of a triangulation G is a map c : such that for each face f of G, the three edges of the boundary walk of f are colored by three distinct colors. By Four Color Theorem, it is known that every triangulation on the sphere has a Grünbaum coloring. So, in this article, we investigate the question whether each even (i.e., Eulerian) triangulation on a surface with representativity at least r has a Grünbaum coloring. We prove that, regardless of the representativity, every even triangulation on a surface has a Grünbaum coloring as long as is the projective plane, the torus, or the Klein bottle, and we observe that the same holds for any surface with sufficiently large representativity. On the other hand, we construct even triangulations with no Grünbaum coloring and representativity , and 3 for all but finitely many surfaces. In dual terms, our results imply that no snark admits an even map on the projective plane, the torus, or the Klein bottle, and that all but finitely many surfaces admit an even map of a snark with representativity at least 3.     

一类分层三角剖分下三次样条空间的维数

本文定义了平面单连通多边形域的一类较任意的三角剖分－分层三角剖分，并通过分析二元样条的积分协调条件，确定了分层三角剖分卜三次Ｃ^１作条函数空间的维数．