Vanishing geodesic distance for the Riemannian metric with geodesic equation the KdV-equation

The Virasoro-Bott group endowed with the right-invariant L ²-metric (which is a weak Riemannian metric) has the KdV-equation as geodesic equation. We prove that this metric space has vanishing geodesic distance.     

Embeddings of Gromov hyperbolic spaces

It is shown that a Gromov hyperbolic geodesic metric space X with bounded growth at some scale is roughly quasi-isometric to a convex subset of hyperbolic space. If one is allowed to rescale the metric of X by some positive constant, then there is an embedding where distances are distorted by at most an additive constant.?Another embedding theorem states that any -hyperbolic metric space embeds isometrically into a complete geodesic -hyperbolic space.?The relation of a Gromov hyperbolic space to its boundary is further investigated. One of the applications is a characterization of the hyperbolic plane up to rough quasi-isometries. Submitted: October 1998, Revised version: January 1999.     

The Chern-Mather class of the multiview variety

The multiview varietyassociated to a collection of N cameras records which sequences of image points in ?^2N can be obtained by taking pictures of a given world point x∈?³ with the cameras. In order to reconstruct a scene from its picture under the different cameras, it is important to be able to find the critical points of the function which measures the distance between a general point u∈?^2N and the multiview variety. In this paper we calculate a specific degree 3 polynomial that computes the number of critical points as a function of N. In order to do this, we construct a resolution of the multiview variety and use it to compute its Chern-Mather class.     

Comparison of Exit Moment Spectra for Extrinsic Metric Balls

We prove explicit upper and lower bounds for the L ¹-moment spectra for the Brownian motion exit time from extrinsic metric balls of submanifolds P ^m in ambient Riemannian spaces N ⁿ . We assume that P and N both have controlled radial curvatures (mean curvature and sectional curvature, respectively) as viewed from a pole in N. The bounds for the exit moment spectra are given in terms of the corresponding spectra for geodesic metric balls in suitably warped product model spaces. The bounds are sharp in the sense that equalities are obtained in characteristic cases. As a corollary we also obtain new intrinsic comparison results for the exit time spectra for metric balls in the ambient manifolds N ⁿ themselves.     

New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping

Abstract. We introduce two new related metrics, the geodesic width and the link width , for measuring the ``distance' between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n <sup>2</sup> log n) time using O(n <sup>2</sup> ) space and the link width in O(n <sup>3</sup> log n) time using O(n <sup>2</sup> ) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: • Compute a continuous transformation that ``morphs' one polyline into another polyline. Our morphing strategies ensure that each point on a polyline moves as little as necessary during the morphing, that every intermediate polyline is also simple and disjoint to any other intermediate polyline, and that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. We present an algorithm that computes the geodesic width of the two polylines and utilizes it to construct a corresponding morphing strategy in O(n ² log ² n) time using O(n ² ) space. We also give an O(nlog n) time algorithm to compute a 2-approximation of the geodesic width and a corresponding morphing scheme. • Locate a continuously moving target using a group of guards moving inside a simple polygon. The guards always determine a simple polygonal chain within the polygon, with consecutive guards along the chain being mutually visible. We compute a strategy that sweeps such a chain of guards through the polygon in order to locate a target. We compute in O(n ³ ) time and O(n ² ) working space the minimum number r ^* of guards needed to sweep an n -vertex polygon. We also give an approximation algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2)≤ r ^* ≤ r and P can be swept with a chain of r guards.     

New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping

   Abstract. We introduce two new related metrics, the geodesic width and the link width , for measuring the ``distance' between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n <sup>2</sup> log n) time using O(n <sup>2</sup> ) space and the link width in O(n <sup>3</sup> log n) time using O(n <sup>2</sup> ) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: • Compute a continuous transformation that ``morphs' one polyline into another polyline. Our morphing strategies ensure that each point on a polyline moves as little as necessary during the morphing, that every intermediate polyline is also simple and disjoint to any other intermediate polyline, and that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. We present an algorithm that computes the geodesic width of the two polylines and utilizes it to construct a corresponding morphing strategy in O(n ² log ² n) time using O(n ² ) space. We also give an O(nlog n) time algorithm to compute a 2-approximation of the geodesic width and a corresponding morphing scheme. • Locate a continuously moving target using a group of guards moving inside a simple polygon. The guards always determine a simple polygonal chain within the polygon, with consecutive guards along the chain being mutually visible. We compute a strategy that sweeps such a chain of guards through the polygon in order to locate a target. We compute in O(n ³ ) time and O(n ² ) working space the minimum number r ^* of guards needed to sweep an n -vertex polygon. We also give an approximation algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2)≤ r ^* ≤ r and P can be swept with a chain of r guards.     

Finding the optimal metric in classification problems with ordinal features

A method for finding the optimal distance function for the classification problem with two classes in which the objects are specified by vectors of their ordinal features is proposed. An optimal distance function is sought by the minimization of the weighted difference of the average intraclass and interclass distances. It is assumed that a specific distance function is given for each feature, which is defined on the Cartesian product of the set of integer numbers in the range from 0 to N − 1 and takes values from 0 to M. Distance functions satisfy modified metric properties. The number of admissible distance functions is calculated, which enables one to significantly reduce the complexity of the problem. To verify the appropriateness of metric optimization and to perform experiments, the nearest neighbor algorithm is used.     

Abstract convergence theorem for quasi-convex optimization problems with applications

Abstract

Quasi-convex optimization is fundamental to the modelling of many practical problems in various fields such as economics, finance and industrial organization. Subgradient methods are practical iterative algorithms for solving large-scale quasi-convex optimization problems. In the present paper, focusing on quasi-convex optimization, we develop an abstract convergence theorem for a class of sequences, which satisfy a general basic inequality, under some suitable assumptions on parameters. The convergence properties in both function values and distances of iterates from the optimal solution set are discussed. The abstract convergence theorem covers relevant results of many types of subgradient methods studied in the literature, for either convex or quasi-convex optimization. Furthermore, we propose a new subgradient method, in which a perturbation of the successive direction is employed at each iteration. As an application of the abstract convergence theorem, we obtain the convergence results of the proposed subgradient method under the assumption of the Hölder condition of order p and by using the constant, diminishing or dynamic stepsize rules, respectively. A preliminary numerical study shows that the proposed method outperforms the standard, stochastic and primal-dual subgradient methods in solving the Cobb–Douglas production efficiency problem.     

Facility Location on a Polyhedral Surface

Given an orientable genus-0 polyhedral surface defined by n triangles, and a set of m point sites} on it, we would like to identify its 1-center, i.e., the location on the surface that minimizes the maximum distance to the sites. The distance is measured as the length of the Euclidean shortest path along the surface. To compute the 1-center, we compute the furthest-site Voronoi diagram of the sites on the polyhedral surface. We show that the diagram has maximum combinatorial complexity (m n ²), and present an algorithm that computes the diagram in O(m n ²log mlog n) expected time. The 1-center can then be identified in time linear in the size of the diagram.     

Solving Euclidean Distance Multifacility Location Problems Using Conjugate Subgradient and Line-Search Methods

Subgradient methods are popular for solving nondifferentiable optimization problems because of their relative ease in implementation, but are not always robust and require a careful design of strategies in order to yield an effective procedure for any given class of problems. In this paper, we present an approach for solving the Euclidean distance multifacility location problem (EMFLP) using conjugate or deflected subgradient based algorithms along with suitable line-search strategies. The subgradient deflection method considered is the Average Direction Strategy (ADS) imbedded within the Variable Target Value Method (VTVM). We also investigate the generation of two types of subgradients to be employed in conjunction with ADS. The first type is a simple valid subgradient that assigns zero values to contributions corresponding to the nondifferentiable terms in the objective function, and so, the subgradient is composed by summing the contributions corresponding to the differentiable terms alone. The second type expends more effort to derive a low-norm member of the subdifferential in order to enhance the prospect of obtaining a descent direction. Furthermore, a special Newton-based line-search that exploits the nondifferentiability of the problem is also designed to be implemented in the developed algorithm in order to study its impact on the convergence behavior. Various combinations of the above strategies are composed and evaluated on a set of test problems. The results show that a modification of the VTVM method along with the first or a certain combination of the two subgradient generation strategies, and the use of a suitable line-search technique, provides promising results. An alternative block-halving step-size strategy used within VTVM in conjunction with the proposed line-search method yields a competitive second choice performance.     

Local monotonicity of Riemannian and Finsler volume with respect to boundary distances

We show that the volume of a simple Riemannian metric on D ⁿ is locally monotone with respect to its boundary distance function. Namely if g is a simple metric on D ⁿ and g′ is sufficiently close to g and induces boundary distances greater or equal to those of g, then vol(D ⁿ , g′) ≥ vol(D ⁿ , g). Furthermore, the same holds for Finsler metrics and the Holmes–Thompson definition of volume. As an application, we give a new proof of injectivity of the geodesic ray transform for a simple Finsler metric.     

Multilevel preconditioning on the refined interface and optimal boundary solvers for the Laplace equation

In this paper we propose and analyze some strategies to construct asymptotically optimal algorithms for solving boundary reductions of the Laplace equation in the interior and exterior of a polygon. The interior Dirichlet or Neumann problems are, in fact, equivalent to a direct treatment of the Dirichlet-Neumann mapping or its inverse, i.e., the Poincaré-Steklov (PS) operator. To construct a fast algorithm for the treatment of the discrete PS operator in the case of polygons composed of rectangles and regular right triangles, we apply the Bramble-Pasciak-Xu (BPX) multilevel preconditioner to the equivalent interface problem in theH ^1/2-setting. Furthermore, a fast matrix-vector multiplication algorithm is based on the frequency cutting techniques applied to the local Schur complements associated with the rectangular substructures specifying the nonmatching decomposition of a given polygon. The proposed compression scheme to compute the action of the discrete interior PS operator is shown to have a complexity of the orderO(N log ^q N),q [2, 3], with memory needsO(N log² N), whereN is the number of degrees of freedom on the polygonal boundary under consideration. In the case of exterior problems we propose a modification of the standard direct BEM whose implementation is reduced to the wavelet approximation applied to either single layer or hypersingular harmonic potentials and, in addition, to the matrix-vector multiplication for the discrete interior PS operator.     

Fast block Toeplitz orthogonalization

Summary Algorithms are presented which compute theQR factorization of a block-Toeplitz matrix inO(n) ² block-operations, wheren is the block-order of the matrix and a block-operation is a multiplication, inversion or a set of Householder operations involving one or two blocks. The algorithms are in general analogous to those presented in the scalar Toeplitz case in a previous paper, but the basic operation is the Householder transform rather than the Givens transform, and the computation of the Householder coefficients and other working matrices requires special treatment. Two algorithms are presented-the first computes onlyR explicitly and the second computes bothQ andR.     

(h, Φ)-entropy differential metric

Burbea and Rao (1982a, 1982b) gave some general methods for constructing quadratic differential metrics on probability spaces. Using these methods, they obtained the Fisher information metric as a particular case. In this paper we apply the method based on entropy measures to obtain a Riemannian metric based on (h, )-entropy measures (Salicrú et al., 1993). The geodesic distances based on that information metric have been computed for a number of parametric families of distributions. The use of geodesic distances in testing statistical hypotheses is illustrated by an example within the Pareto family. We obtain the asymptotic distribution of the information matrices associated with the metric when the parameter is replaced by its maximum likelihood estimator. The relation between the information matrices and the Cramér-Rao inequality is also obtained.     

Characterization of Geodesic Flows on T 2 with and without Positive Topological Entropy

In the present work we consider the behavior of the geodesic flow on the unit tangent bundle of the 2-torus T ² for an arbitrary Riemannian metric. A natural non-negative quantity which measures the complexity of the geodesic flow is the topological entropy. In particular, positive topological entropy implies chaotic behavior on an invariant set in the phase space of positive Hausdorff-dimension (horseshoe). We show that in the case of zero topological entropy the flow has properties similar to integrable systems. In particular, there exists a non-trivial continuous constant of motion which measures the direction of geodesics lifted onto the universal covering \mathbbR²{\mathbb{R}^{2}} . Furthermore, those geodesics travel in strips bounded by Euclidean lines. Moreover, we derive necessary and sufficient conditions for vanishing topological entropy involving intersection properties of single geodesics on T ².     

A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances

We describe a linear-time algorithm for solving the molecular distance geometry problem with exact distances between all pairs of atoms. This problem needs to be solved in every iteration of general distance geometry algorithms for protein modeling such as the EMBED algorithm by Crippen and Havel (Distance Geometry and Molecular Conformation, Wiley, 1988). However, previous approaches to the problem rely on decomposing an distance matrix or minimizing an error function and require O(n²) to O(³) floating point operations. The linear-time algorithm will provide a much more efficient approach to the problem, especially in large-scale applications. It exploits the problem structure and hence is able to identify infeasible data more easily as well.     

Decomposing Ends of Locally Finite Graphs

An important invariant of translations of infinite locally finite graphs is that of a direction as introduced by Halin . This invariant gives not much information if the translation is not a proper one. A new refined concept of directions is investigated. A double ray D of a graph X is said to be metric, if the distance metrics in D and X on V(D) are equivalent. It is called geodesic, if these metrics are equal. The translations leaving some metric double ray invariant are characterized. Using a result of Polat and Watkins , we characterize the translations leaving some geodesic double ray invariant.     

On neighbouring matrices with quadratic elementary divisors

Summary Algorithms are presented which compute theQR factorization of an order-n Toeplitz matrix inO(n ²) operations. The first algorithm computes onlyR explicitly, and the second computes bothQ andR. The algorithms are derived from a well-known procedure for performing the rank-1 update ofQR factors, using the shift-invariance property of the Toeplitz matrix. The algorithms can be used to solve the Toeplitz least-squares problem, and can be modified to solve Toeplitz systems inO(n) space.     

Calculation of coordinates from incomplete and incorrect distance data

Summary A method has been developed to calculate cartesian coordinates from distances by means of a metric matrix. In contrast to usual methods it requires a minimum of four lines of the distance matrix, i.e. a fraction 8/N of all possible distances when applied to a three-dimensional structure. The factorization of the metric matrix is performed with a stable modified Gauss algorithm. The amount of storage and computing time depends linearly on the number of particles considered. Numerical results were obtained for a system of 58 atoms of a protein and compared with the results from other methods.

---

Zusammenfassung Ein Verfahren wurde entwickelt zur Berechnung kartesischer Koordinaten mit Hilfe einer metrischen Matrix. Bei der Anwendung auf dreidimensionale Strukturen sind im Minimalfall vier Zeilen der Abstandsmatrix erforderlich, d. h. nur ein Bruchteil 8/N aller möglichen Abstände muß bekannt sein. Zur Faktorisierung der metrischen Matrix wird ein stabiler modifizierter Gaußalgorithmus benutzt. Speicherbedarf und Rechenzeit hängen linear von der Zahl der betrachteten Teilchen ab. Für ein System bestehend aus 58 Atomen eines Proteins wurden numerische Ergebnisse berechnet und mit denen anderer Methoden verglichen.

     

Bilipschitz Embeddings of Metric Spaces into Space Forms

The paper describes some basic geometric tools to construct bilipschitz embeddings of metric spaces into (finite-dimensional) Euclidean or hyperbolic spaces. One of the main results implies the following: If X is a geodesic metric space with convex distance function and the property that geodesic segments can be extended to rays, then X admits a bilipschitz embedding into some Euclidean space iff X has the doubling property, and X admits a bilipschitz embedding into some hyperbolic space iff X is Gromov hyperbolic and doubling up to some scale. In either case the image of the embedding is shown to be a Lipschitz retract in the target space, provided X is complete.