Calculation of coordinates from molecular geometric parameters and the concept of a geometric calculator

Three different geometric parameters, distance r(i,j), angle θ(i,j, k), and dihedral (or torsion) angle φ(i,j, k, l), are commonly used to specify the shape of a molecule. Given Cartesian coordinates it is simple to calculate such parameters. The, non-trivial, inverse problem of finding coordinates when given such parameters is considered here. When a triple of such geometric parameters is given to specify the position of an atom, n, relative to reference atoms i,j, k,…, with known positions, five qualitatively different cases arise: r(n, i), θ(n, i,j), φ(n, i,j, k), θ(j, n, i) and φ(k, n, i,j). Each such geometric coordinate specifies n to lie on a certain type of surface. To calculate its position one must find the point of intersection of three such surfaces. A program, Evclid, that can perform these calculations is integrated with an interactive set of routines that constitute a geometric calculator and editor. It works on (three-dimensional) points and has a number of input, display and output options. It can translate, rotate, reflect, invert and scale as well as edit the point set or subsets.     

A new approach to contour coding

This paper presents a method for the compact representation of the contours of binary images on the basis of the sets of coordinates of equidistant points along the contour. Let P = {P₁, P₂, …, P_n} an ordered set of points approximately equidistant on the contour Γ of the image. With P is associated a n-dimensional vector α with components consisting of the angles between the straight lines passing through P_(i−1), P_(i) and P_(i), P_(i+1). We can take α as representative of the contour; α has the following properties: (A) 0 ≤ |α(i)| ≤ 180°. (B) Given a suitable positive direction of rotation for the angles, Σ_1niα(i) = 360° for a closed, simply connected boundary. (C) If Γ is expressed in polar coordinates ϱ = ϱ(θ) and Γ′ϱ′ = kp(θ), then α = α′. (D) α(i), a component of α, extracts information about the local characteristics of the contour such as concavities, convexities, corners and straight lines. (E) α is independent of the orientation of the contour.A simple program was implemented on a 2100 HP computer and a series of preliminary experiments were performed in which the computer was given the (x, y) coordinates of manually digitized contours. We found good reliability of the method with contours of various orientations and sizes even in the presence of noise on the contours.     

Locally optimal tests for exponential distributions with type-I censoring

This article studies a locally optimal test φ^∗ for testing H₀:θ≥θ₀ versus H₁:θ<θ₀ for the lifetime parameter θ in an exponential distribution based on type-I censored data. Certain properties associated with φ^∗ are addressed. We compare the performance of φ^∗ with that of Spurrier and Wei’s [Spurrier, J.D., Wei, L.J., 1980. A test of the parameter of the exponential distribution in the type-I censoring case. J. Amer. Statist. Assoc. 75, 405-409] test φ_SW, which is based on the MLE of θ. The exact powers and asymptotic powers of φ^∗ and φ_SW are computed. The numerical results indicate that the power of φ^∗ is better than that of φ_SW when θ(0<θ<θ₀) is close to θ₀.     

Membrane statics of parachute-like shells

The parachute-like shells studied in this paper may be referred to as scalloped paraboloids. The middle surface of the shell, which lacks rotational symmetry, is defined in cylindrical coordinates by the equation Z=Ar²(1 +βθ²). Of interest to the designer are the membrane forces N_r, N_θ, N_rθ in the shell or their dimensionless plan projections n_r, n_θ, n_rθ. The latter may be found from the consideration of equilibrium, using the stress function approach. The stress function has to satisfy a second order partial differential equation subject to proper boundary conditions. The solution is found by separation of variables and the method of infinite series. The generation of practical results relies heavily on the digital computer. An approximate technique, convenient for practical purposes, is also discussed. For the purpose of illustration, a scalloped paraboloid loaded and supported like a parachute is considered. Adequate numerical and graphical results are given. The necessary mathematical expressions are included in an Appendix. It is shown graphically how the stresses within the shell are influenced by the parameter β. By a proper choice of this parameter the stresses within the shell can be restricted to be either entirely tensile or compressive. The value of the optimum β depends on the height to radius ratio μ. A practical curve that describes this optimum μ, β relationship is included.     

Optimal algorithm for a special point-labeling problem

A special class of map labeling problem is studied. Let P={p₁,p₂,…,p_n} be a set of point sites distributed on a 2D map. A label associated with each point p_i is an axis-parallel rectangle r_i of specified width. The height of all are same. The placement of r_i must contain p_i at its top-left or bottom-left corner, and it does not obscure any other point in P. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. We first consider a simple model for this problem. Here, for each point p_i, the corner specification (i.e., whether the point p_i would appear at the top-left or bottom-left corner of the label) is known a priori. We show that the time complexity of this problem is , and then propose an algorithm for this problem which runs in O(nlogn) time. If the corner specifications of the points in P are not known, our algorithm is a 2-approximation algorithm. Here we propose an efficient heuristic algorithm that is easy to implement. Experimental evidences show that it produces optimal solutions for most of the randomly generated instances and for all the standard benchmarks available in http://www.math-inf.uni-greifswald.de/map-labeling/.     

On a circle placement problem

We consider the following circle placement problem: given a set of pointsp _i ,i=1,2, ...,n, each of weightw _i , in the plane, and a fixed disk of radiusr, find a location to place the disk such that the total weight of the points covered by the disk is maximized. The problem is equivalent to the so-called maximum weighted clique problem for circle intersection graphs. That is, given a setS ofn circles,D _i ,i=1,2, ...,n, of the same radiusr, each of weightw _i , find a subset ofS whose common intersection is nonempty and whose total weight is maximum. AnO (n ²) algorithm is presented for the maximum clique problem. The algorithm is better than a previously known algorithm which is based on sorting and runs inO (n ² logn) time.     

Embedding K-ary Complete Trees into Hypercubes

In this paper, dilated embedding and precise embedding of K-ary complete trees into hypercubes are studied. For dilated embedding, a nearly optimal algorithm is proposed which embeds a K-ary complete tree of height h, T_K(h), into an (h − 1)[log K] + [log (K + 2)]-dimensional hypercube with dilation Max{2, φ(K), φ(K + 2)}. φ(x) = min{λ: Σ^λ_i=0Cⁱ_d ≥ x and d = [log x]}. It is clear that [([log x] + 1)/2] ≤ φ(x) ≤ [log x], for x ≥ 3.) For precise embedding, we show a (K − 1)h + 1-dimensional hypercube is large enough to contain T_K(h) as its subgraph, K ≥ 3.     

A lower bound for computing Oja depth

Let S={s₁,…,sn} be a set of points in the plane. The Oja depth of a query point θ with respect to S is the sum of the areas of all triangles (θ,si,sj). This depth may be computed in O(nlogn) time in the RAM model of computation. We show that a matching lower bound holds in the algebraic decision tree model. This bound also applies to the computation of the Oja gradient, the Oja sign test, and to the problem of computing the sum of pairwise distances among points on a line.     

Fitting a least squares piecewise linear continuous curve in two dimensions

An optimal piecewise linear continuous fit to a given set of n data points D = {(x_i, y_i) : 1 ≤ i ≤ n} in two dimensions consists of a continuous curve defined by k linear segments {L₁, L₂,…,L_k} which minimizes a weighted least squares error function with weight w_i at (x_i, y_i), where k ≥ 1 is a given integer. A key difficulty here is the fact that the linear segment L_j, which approximates a subset of consecutive data points D_j ⊂ D in an optimal solution, is not necessarily an optimal fit in itself for the points D_j. We solve the problem for the special case k = 2 by showing that an optimal solution essentially consists of two least squares linear regression lines in which the weight w_j of some data point (x_j, y_j) is split into the weights λw_j and (1 − λ)w_j, 0 ≤ λ ≤ 1, for computations of these lines. This gives an algorithm of worst-case complexity O(n) for finding an optimal solution for the case k = 2.     

Motion of spin-half particles in the axially symmetric field of naked singularities of the static <Emphasis Type="Italic">q</Emphasis>-metric

Quantum-mechanical motion of a spin-half particle is examined in the axially symmetric fields of static naked singularities formed by a mass distribution with a quadrupole moment (q-metric). The analysis is performed by means of the method of effective potentials of the Dirac equation generalized to the case where radial and angular variables are not separated. If ?1 < q < qlim, |qlim| ? 1, where q is the quadrupolemoment in proper units, the naked singularities do not exclude the existence of stationary bound states of Dirac particles for a prolate mass distribution in the q-metric along the axial axis. For an oblate mass distribution, the naked singularities of the q-metric are separated from a Dirac particle by infinitely large repulsive barriers followed by a potential well which deepens while moving apart from the equator (from θ = θ _min or θ = π ? θ _min) toward the poles. The poles make an exception, and at 0 < q < q*, there are some points θ _i for particle states with j ≥ 3/2.     

Texture classification using features derived from random field models

This paper presents a new feature extraction method for classifying a texture image into one of the l possible classes C_i, i=1,…,l. It is assumed that the given M × M image characterized by a set of intensity levels, {y(s₁,S₂), 0≤s_s,s₂≤M?1}, is a realization of an underlying random field model, known as the Simultaneous Autoregressive Model (SAR). This model is characterized by a set of parameters φ whose probability density function p_i(φ), depends on the class to which the image belongs. First it is shown that the maximum likelihood estimate (M.L.E.) $\text{φ}{}^1$, of φ is an appropriate feature vector for classification purposes. The optimum Bayes classifier which minimizes the average probability of classification error, is then designed using $\text{φ}{}^1$. Finally the efficiency of the feature vector is demonstrated through experimental results obtained with some natural texture data and a simpler quadratic mean classifier.     

Some characterizations of finitely specifiable implicational dependency families

Let r be a relation for the relation scheme R(A₁,A₂,…,A_n); then we define Dom(r) to be Dom_r(A₁)×Dom_r(A₂)×…×Dom_r(A_n), where Dom_r(A_i) for each i is the set of all ith coordinates of tuples of r. A relation s is said to be a substructure of the relation r if and only if Dom(s)∩r = s.The following theorems analogous to Tarski-Fraisse-Vaught's characterizations of universal classes are proved: (i) An implicational dependency family (ID-family) F over the relation scheme R is finitely specifiable if and only if there exists a finite number of relations r₁,r₂,…,r_m for R such that r ∈ F if and only if no r_i is isomorphic to a substructure of r. (ii) F is finitely specifiable if and only if there exists a natural number k such that r ∈ F whenever F contains all substructures of r with at most k elements.We shall use these characterizations to obtain a new proof for Hull's (1984) characterization of finitely specifiable ID-families.     

Alcuni problemi relativi alle formule di quadratura del tipo di tchebycheff

In this paper we study quadrature formulas of the form $$\int\limits_{ - 1}^1 {(1 - x)^a (1 + x)^\beta f(x)dx = \sum\limits_{i = 0}^{r - 1} {[A_i f^{(i)} ( - 1) + B_i f^{(i)} (1)] + K_n (\alpha ,\beta ;r)\sum\limits_{i = 1}^n {f(x_{n,i} ),} } } $$ (α>?1, β>?1), with realA _i ,B _i ,K _n and real nodesx _n,i in (?1,1), valid for prolynomials of degree ≤2n+2r?1. In the first part we prove that there is validity for polynomials exactly of degree2n+2r?1 if and only if α=β=?1/2 andr=0 orr=1. In the second part we consider the problem of the existence of the formula $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} f(x)dx = A_n f( - 1) + B_n f(1) + C\sum\limits_{i = 1}^n {f(x_{n,i} )} }$$ for polynomials of degree ≤n+2. Some numerical results are given when λ=1/2.     

Algorithms for finding the axis of a helix: Fast rotational and parametric least-squares methods

Several methods for finding the axis of a helix are presented and compared. The most accurate determines the helix axis as the axis of rotation necessary to map point i to point i + 1 of the helix. The fastest method calculates the helix axis as the best-fit line through the coordinates by a three-dimensional parametric linear least-squares algorithm, taking advantage of the sequential nature of the data.     

On the All-Farthest-Segments problem for a planar set of points

In this note, we outline a very simple algorithm for the following problem: Given a set S of n points p₁,p₂,p₃,…,pn in the plane, we have O(n²) segments implicitly defined on pairs of these n points. For each point pi, find a segment from this set of implicitly defined segments that is farthest from pi. The time complexity of our algorithm is in O(nh+nlogn), where n is the number of input points, and h is the number of vertices on the convex hull of S.     

Metric information filtering

The traditional problem of similarity search requires to find, within a set of points, those that are closer to a query point q, according to a distance function d. In this paper we introduce the novel problem of metric information filtering (MIF): in this scenario, each point x_i comes with its own distance function d_i and the task is to efficiently determine those points that are close enough, according to d_i, to a query point q. MIF can be seen as an extension of both the similarity search problem and of approaches currently used in content-based information filtering, since in MIF user profiles (points) and new items (queries) are compared using arbitrary, personalized, metrics. We introduce the basic concepts of MIF and provide alternative resolution strategies aiming to reduce processing costs. Our experimental results show that the proposed solutions are indeed effective in reducing evaluation costs.     

Three-dimensional simulation of magneto-hydrodynamic implosion of multi-wire cylindrical liners by the FLUX-3D code

A three-dimensional magneto-hydrodynamic model of conductive radiating plasma, underlying the Euler (in the cylindrical coordinates r-φ-z) program code FLUX-3D, developed at the Russian Federal Nuclear Center VNIIEF, is presented. Finite-difference methods for solving the equations of the model on a stationary regular spatial grid are described. Results of numerical 3D simulation of a multi-wire Z-pinch in conditions of the Shot-51 experiment on electrophysical facility Z (USA) in the full (2π) azimuth angle are presented. The computation geometry has been approximated to the real experimental configuration, in which the electromagnetic energy was supplied to the chamber by a vacuum coaxial transmission line. In the numerical simulation, the dynamics of the acceleration of plasma ablated from tungsten wires as a function of the number of wires in the initial cylindrical assembly was studied. In addition, results of 3D calculations of the current implosion of multi-wire Z-pinch for two kinds of artificial perturbations on the plasma ablation intensity are presented. The reasons of the difference in the soft X-ray radiation pulses generated in these cases are discussed.     

A Time-Optimal Multiple Search Algorithm on Enhanced Meshes,with Applications

Given a sorted sequence A = a₁, a₂, ..., a_n of items from a totally ordered universe, along with an arbitrary sequence Q = q₁, q₂, ..., q_m (1 ≤ m ≤ n) of queries, the multiple search problem involves computing for every q_j (1 ≤ j ≤ m) the unique a_i for which a_i−1 ≤ q_j < a_i. In this paper we propose a time-optimal algorithm to solve the multiple search problem on meshes with multiple broadcasting. More specifically, on a [formula] × [formula] mesh with multiple broadcasting, our algorithm runs in [formula] time which is shown to be time-optimal. We also present some surprising applications of the multiple search algorithm to computer graphics, image processing, robotics, and computational geometry.