Resolvable Representation of Polyhedra

The paper proposes a new method for the boundary representation of three-dimensional (not necessarily convex) polyhedra, called a resolvable representation , in which small numerical errors do not violate the symbolic part of the representation. In this representation, numerical data are represented partly by the coordinates of vertices and partly by the coefficients of face equations in such a way that the polyhedron can be reconstructed from the representation in a step-by-step manner. It is proved that any polyhedron homeomorphic to a sphere has a resolvable representation, and an algorithm for finding such a representation is constructed. Received January 21, 1997, and in revised form April 29, 1998.     

三维加权PFDK重建算法研究

基于滤波反投影的Feldkamp-Davis-Kress(FDK)算法,具有数学形式简单、容易实现和计算速度快等优点,在医疗和工业等领域得到了广泛的应用.平行重排(PF DK)算法是FDK算法的一种推广,针对PFDK算法重建出的图像受锥角的影响加大的问题,给出一种三维加权PFDK图像重建算法,并研究了重排过程中径向插值间隔对重建图像质量的影响,分别采用三种不同插值总数(插值间隔分别是1单位,0.5单位,0.25单位)重排数据.实验结果表明给出的三维加权PFDK算法可有效减少锥角的影响,且当采用2倍插值总数时重建结果较好.     

Weighted frames of exponentials and stable recovery of multidimensional functions from nonuniform Fourier samples

In this paper, we consider the problem of recovering a compactly supported multivariate function from a collection of pointwise samples of its Fourier transform taken nonuniformly. We do this by using the concept of weighted Fourier frames. A seminal result of Beurling shows that sampling points give rise to a classical Fourier frame provided they are relatively separated and of sufficient density. However, this result does not allow for arbitrary clustering of sampling points, as is often the case in practice. Whilst keeping the density condition sharp and dimension independent, our first result removes the separation condition and shows that density alone suffices. However, this result does not lead to estimates for the frame bounds. A known result of Gröchenig provides explicit estimates, but only subject to a density condition that deteriorates linearly with dimension. In our second result we improve these bounds by reducing the dimension dependence. In particular, we provide explicit frame bounds which are dimensionless for functions having compact support contained in a sphere. Next, we demonstrate how our two main results give new insight into a reconstruction algorithm—based on the existing generalized sampling framework—that allows for stable and quasi-optimal reconstruction in any particular basis from a finite collection of samples. Finally, we construct sufficiently dense sampling schemes that are often used in practice—jittered, radial and spiral sampling schemes—and provide several examples illustrating the effectiveness of our approach when tested on these schemes.     

Approximation inL 2 Sobolev spaces on the 2-sphere by quasi-interpolation

In this article we consider a simple method of radial quasi-interpolation by polynomials on the unit sphere in ℝ³, and present rates of covergence for this method in Sobolev spaces of square integrable functions. We write the discrete Fourier series as a quasi-interpolant and hence obtain convergence rates, in the aforementioned Sobolev spaces, for the discrete Fourier projection. We also discuss some typical practical examples used in the context of spherical wavelets.     

Shift coordinates, stretch lines and polyhedral structures for Teichmüller space

This paper has two parts. In the first part, we study shift coordinates on a sphere S equipped with three distinguished points and a triangulation whose vertices are the distinguished points. These coordinates parametrize a space (S)\widetilde{{\cal T}}(S) that we call an unfolded Teichmüller space. This space contains Teichmüller spaces of the sphere with \frak b{\frak b} boundary components and \frak p{\frak p} cusps (which we call generalized pairs of pants), for all possible values of \frak b{\frak b} and \frak p{\frak p} satisfying \frak b+\frak p=3{\frak b}+{\frak p}=3 . The parametrization of [(T)\tilde](S)\widetilde{{\cal T}}(S) by shift coordinates equips this space with a natural polyhedral structure, which we describe more precisely as a cone over an octahedron in \Bbb R³{\Bbb {R}}^3 . Each cone over a simplex of this octahedron is interpreted as a Teichmüller space of the sphere with \frak b{\frak b} boundary components and \frak p{\frak p} cusps, for fixed \frak b{\frak b} and \frak p{\frak p} , the sphere being furthermore equipped with an orientation on each boundary component. There is a natural linear action of a finite group on [(T)\tilde](S)\widetilde{{\cal T}}(S) whose quotient is an augmented Teichmüller space in the usual sense. We describe several aspects of the geometry of the space [(T)\tilde](S)\widetilde{{\cal T}}(S) . Stretch lines and earthquakes can be defined on this space. In the second part of the paper, we use the shift coordinates to obtain estimates on the behaviour of stretch lines in the Teichmüller space of a surface obtained by gluing hyperbolic pairs of pants. We also use the shift coordinates to give formulae that express stretch lines in terms of Fenchel-Nielsen coordinates. We deduce the disjointness of some stretch lines in Teichmüller space. We study in more detail the case of a closed surface of genus 2.     

Isometric embeddings of locally Euclidean metrics in ℝ3 as conical surfaces

It is proved that if a domain with a locally Euclidean metric can be isometrically immersed in the Euclidean plane ?² with the standard metric, then it can be isometrically embedded in ?³ as a conical surface whose projection on a sphere centered at the vertex of the cone is a self-avoiding planar graph with sufficiently smooth edges of specially selected lengths.     

Further characterizations of cubic lattice graphs

A cubic lattice graph with characteristic n is a graph whose points can be identified with the ordered triplets on n symbols and two points are adjacent whenever the corresponding triplets have two coordinates in common. An L₂ graph is a graph whose points can be identified with the ordered pairs on n symbols such that two points are adjacent if and only if the corresponding pairs have a common coordinate. The main result of this paper is two new characterizations and shows the relation between cubic lattice and L₂ graphs. The main result also suggests a conjecture concerning the characterization of interchange graphs of complete m-partite graphs.     

On the Approximation Order of Splines on Spherical Triangulations

Bounds are provided on how well functions in Sobolev spaces on the sphere can be approximated by spherical splines, where a spherical spline of degree d is a C ^r function whose pieces are the restrictions of homogeneous polynomials of degree d to the sphere. The bounds are expressed in terms of appropriate seminorms defined with the help of radial projection, and are obtained using appropriate quasi-interpolation operators.     

On the computation of protein backbones by using artificial backbones of hydrogens

NMR experiments provide information from which some of the distances between pairs of hydrogen atoms of a protein molecule can be estimated. Such distances can be exploited in order to identify the three-dimensional conformation of the molecule: this problem is known in the literature as the Molecular Distance Geometry Problem (MDGP). In this paper, we show how an artificial backbone of hydrogens can be defined which allows the reformulation of the MDGP as a combinatorial problem. This is done with the aim of solving the problem by the Branch and Prune (BP) algorithm, which is able to solve it efficiently. Moreover, we show how the real backbone of a protein conformation can be computed by using the coordinates of the hydrogens found by the BP algorithm. Formal proofs of the presented results are provided, as well as computational experiences on a set of instances whose size ranges from 60 to 6000 atoms.     

Rectilinear planar layouts and bipolar orientations of planar graphs

We propose a linear-time algorithm for generating a planar layout of a planar graph. Each vertex is represented by a horizontal line segment and each edge by a vertical line segment. All endpoints of the segments have integer coordinates. The total space occupied by the layout is at mostn by at most 2n–4. Our algorithm, a variant of one by Otten and van Wijk, generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way. The algorithm is based on the concept of abipolar orientation. We discuss relationships among the bipolar orientations of a planar graph.Research partly supported by the Agence de L'Informatique du Ministere de L'Industrie, France, under contract No. 83-285.     

Even points on an algebraic curve

We show that the points of a global function field, whose classes are 2-divisible in the Picard group, form a connected regular infinite graph, with the incidence relation generalizing the well known quadratic reciprocity law. We prove that for every global function field the diameter of this graph is precisely 2. In addition we develop an analog of global square theorem that concerns points 2-divisible in the Picard group.     

Low-Dimensional Embedding with Extra Information

A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry (e.g., distances, angles, and/or orientations), and the goal is to reconstruct the global geometry from this partial information. More precisely, we are given a graph, the approximate lengths of the edges, and possibly extra information, and our goal is to assign two-dimensional coordinates to the vertices such that the (multiplicative or additive) error on the resulting distances and other information is within a constant factor of the best possible. We obtain the first pseudo-quasipolynomial-time algorithm for this problem given a complete graph of Euclidean distances with additive error and no extra information. For general graphs, the analogous problem is NP-hard even with exact distances. Thus, for general graphs, we consider natural types of extra information that make the problem more tractable, including approximate angles between edges, the order type of vertices, a model of coordinate noise, or knowledge about the range of distance measurements. Our pseudo-quasipolynomial-time algorithm for no extra information can also be viewed as a polynomial-time algorithm given an "extremum oracle" as extra information. We give several approximation algorithms and contrasting hardness results for these scenarios.     

Generating the Acyclic Orientations of a Graph

The acyclic orientations of a graph are related to its chromatic polynomial, to its reliability, and to certain hyperplane arrangements. In this paper, an algorithm for listing the acyclic orientations of a graph is presented. The algorithm is shown to requireO(n) time per acyclic orientation generated. This is the most efficient algorithm known for generating acyclic orientations.     

SQP技术与广义投影相结合的次可行方向法

本文建立非线性不等式约束优化的一个新算法，分析和证明了算法的整体收敛性和超线性收敛性。其技巧在于将广义投影和ＳＱＰ技术结合使用。     

Highly effective stable evaluation of bandlimited functions on the sphere

An algorithm for fast and accurate evaluation of band-limited functions at many scattered points on the unit 2-d sphere is developed. The algorithm is based on trigonometric representation of spherical harmonics in spherical coordinates and highly localized tensor-product trigonometric kernels (needlets). It is simple, fast, local, memory efficient, numerically stable and with guaranteed accuracy. Comparison of this algorithm with other existing algorithms in the literature is also presented.     

Connections between three-dimensional inverse scattering and linear least-squares estimation of random fields

The three-dimensional Schrödinger equation inverse scattering problem with a nonspherically-symmetric potential is related to the filtering problem of computing the linear leastsquares estimate of the three-dimensional random field on the surface of a sphere from noisy observations inside the sphere. The relation consists of associating an estimation problem with the inverse scattering problem, and vice-versa. This association allows equations and quantities for one problem to be given interpretations in terms of the other problem. A new fast algorithm is obtained for the estimation of random fields using this association. The present work is an extension of the connections between estimation and inverse scattering already known to exist for stationary random processes and one-dimensional scattering potentials, and isotropic random fields and radial scattering protentials.     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

Global minimum potential energy conformations of small molecules

A global optimization algorithm is proposed for finding the global minimum potential energy conformations of small molecules. The minimization of the total potential energy is formulated on an independent set of internal coordinates involving only torsion (dihedral) angles. Analytical expressions for the Euclidean distances between non-bonded atoms, which are required for evaluating the individual pairwise potential terms, are obtained as functions of bond lengths, covalent bond angles, and torsion angles. A novel procedure for deriving convex lower bounding functions for the total potential energy function is also introduced. These underestimating functions satisfy a number of important theoretical properties. A global optimization algorithm is then proposed based on an efficient partitioning strategy which is guaranteed to attain -convergence to the global minimum potential energy configuration of a molecule through the solution of a series of nonlinear convex optimization problems. Moreover, lower and upper bounds on the total finite number of required iterations are also provided. Finally, this global optimization approach is illustrated with a number of example problems.     

Function approximation via particular input space partition and region-based exponential membership functions

This paper presents an algorithm to build a compact fuzzy model for approximating unknown nonlinear functions. According to the coordinates of input–output pairs in the Cartesian product-space, the proposed algorithm partitions the input space into several characteristic regions, whose boundaries are determined by the local-minimum, local-maximum, and turning points of the training data. The region-based exponential functions are chosen as membership functions of antecedents, with consequents of rules as singletons, to construct the fuzzy model. Finally, five examples demonstrate that the proposed fuzzy model indeed improves performance in the approximating of nonlinear functions.     

Spinorial Method of Terminal Control of Spatial Rotations

In this paper, we introduce the notion of three-dimensional generalized rotations. We obtain relations between the parameters of the spinor representation of the group of three-dimensional generalized rotations and the coordinates of the initial and terminal points of rotation. Simple relations between elements of a three-dimensional orthogonal matrix of the basic representation and the Euler angles, on the one hand, and the coordinates of the initial and terminal points of rotation, on the other hand, were derived. The spinor method of solution of the inverse kinematic problem for spatial mechanisms with spherical pairs is developed and the corresponding algorithm is proposed. The obtained results allow one to reduce the three-dimensional problem of spatial motion control to the one-dimensional problem. Simple adaptive algorithms are suggested, by means of which various partial problems on the terminal control are solved under various terminal conditions. New algorithms of control of spatial rotations of manipulating robots are studied.