Localization from Incomplete Noisy Distance Measurements

We consider the problem of positioning a cloud of points in the Euclidean space ? ^d , using noisy measurements of a subset of pairwise distances. This task has applications in various areas, such as sensor network localization and reconstruction of protein conformations from NMR measurements. It is also closely related to dimensionality reduction problems and manifold learning, where the goal is to learn the underlying global geometry of a data set using local (or partial) metric information. Here we propose a reconstruction algorithm based on semidefinite programming. For a random geometric graph model and uniformly bounded noise, we provide a precise characterization of the algorithm’s performance: in the noiseless case, we find a radius r ₀ beyond which the algorithm reconstructs the exact positions (up to rigid transformations). In the presence of noise, we obtain upper and lower bounds on the reconstruction error that match up to a factor that depends only on the dimension d, and the average degree of the nodes in the graph.     

Manifold Reconstruction Using Tangential Delaunay Complexes

We give a provably correct algorithm to reconstruct a k-dimensional smooth manifold embedded in d-dimensional Euclidean space. The input to our algorithm is a point sample coming from an unknown manifold. Our approach is based on two main ideas: the notion of tangential Delaunay complex defined in Boissonnat and Flötotto (Comput. Aided Des. 36:161–174, 2004), Flötotto (A coordinate system associated to a point cloud issued from a manifold: definition, properties and applications. Ph.D. thesis, 2003), Freedman (IEEE Trans. Pattern Anal. Mach. Intell. 24(10), 2002), and the technique of sliver removal by weighting the sample points (Cheng et al. in J. ACM 47:883–904, 2000). Differently from previous methods, we do not construct any subdivision of the d-dimensional ambient space. As a result, the running time of our algorithm depends only linearly on the extrinsic dimension d while it depends quadratically on the size of the input sample, and exponentially on the intrinsic dimension k. To the best of our knowledge, this is the first certified algorithm for manifold reconstruction whose complexity depends linearly on the ambient dimension. We also prove that for a dense enough sample the output of our algorithm is isotopic to the manifold and a close geometric approximation of the manifold.     

Normal cone approximation and offset shape isotopy

This work addresses the problem of the approximation of the normals of the offsets of general compact sets in Euclidean spaces. It is proven that for general sampling conditions, it is possible to approximate the gradient vector field of the distance to general compact sets. These conditions involve the μ-reach of the compact set, a recently introduced notion of feature size. As a consequence, we provide a sampling condition that is sufficient to ensure the correctness up to isotopy of a reconstruction given by an offset of the sampling. We also provide a notion of normal cone to general compact sets that is stable under perturbation.     

Geometric Inference for Probability Measures

Data often comes in the form of a point cloud sampled from an unknown compact subset of Euclidean space. The general goal of geometric inference is then to recover geometric and topological features (e.g., Betti numbers, normals) of this subset from the approximating point cloud data. It appears that the study of distance functions allows one to address many of these questions successfully. However, one of the main limitations of this framework is that it does not cope well with outliers or with background noise. In this paper, we show how to extend the framework of distance functions to overcome this problem. Replacing compact subsets by measures, we introduce a notion of distance function to a probability distribution in ℝ ^d . These functions share many properties with classical distance functions, which make them suitable for inference purposes. In particular, by considering appropriate level sets of these distance functions, we show that it is possible to reconstruct offsets of sampled shapes with topological guarantees even in the presence of outliers. Moreover, in settings where empirical measures are considered, these functions can be easily evaluated, making them of particular practical interest.     

Metrically homogeneous sets

A subset of a metric space is called metrically homogeneous if the set of distances from a chosen point of the subset to all the other points of the subset is independent of the chosen point. The main result of the paper is a complete characterization of the compact, metrically homogeneous subsets of the Euclidean plane.     

On a generalization of distance sets

A subset X in the d-dimensional Euclidean space is called a k-distance set if there are exactly k distinct distances between two distinct points in X and a subset X is called a locally k-distance set if for any point x in X, there are at most k distinct distances between x and other points in X.Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of k-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally k-distance sets on a sphere. In the first part of this paper, we prove that if X is a locally k-distance set attaining the Fisher type upper bound, then determining a weight function w, (X,w) is a tight weighted spherical 2k-design. This result implies that locally k-distance sets attaining the Fisher type upper bound are k-distance sets. In the second part, we give a new absolute bound for the cardinalities of k-distance sets on a sphere. This upper bound is useful for k-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in (d−1)-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in d-space with more than d(d+1)/2 points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.     

Geometric characterizations of C1 manifolds in Euclidean spaces by tangent cones

A remarkable and elementary fact that a locally compact set $F$ of Euclidean space is a smooth manifold if (and only if) the lower and upper paratangent cones to $F$ coincide at every point, is proved. The celebrated von Neumann’s result (1929) that a locally compact subgroup of the general linear group is a smooth manifold, is a straightforward application.     

Multivalued contractions

LetE be a Banach space,C a closed convex subset ofE, F a multivalued contraction fromC to itself with closed values. Ifx ₀ is a fixed point and ifF(x ₀) is not a singleton, then there exists a fixed pointx ₁ ofF which is different fromx ₀. We prove also that there is in the Euclidean space ?² a multivalued contraction with compact connected values having a nonconnected set of fixed points.     

Aspects of the Qualitative Theory of Suspended Foliations

We proved that the set of suspended foliations of a compact manifold M is open in the space of foliations with C r -topology. Relation between sets of suspended foliations with Hausdorff and non-Hausdorff graphs are investigated from topological and set-theoretical points of view. Continuum set of pairwise non-isomorphic C X -diffeomorphisms of 1-dimensional manifold with special properties is constructed and used essentially.     

Proximal Point Algorithm On Riemannian Manifolds

Abstract

In this paper we consider the minimization problem with constraints. We will show that if the set of constraints is a Riemannian manifold of nonpositive sectional curvature, and the objective function is convex in this manifold, then the proximal point method in Euclidean space is naturally extended to solve that class of problems. We will prove that the sequence generated by our method is well defined and converge to a minimizer point. In particular we show how tools of Riemannian geometry, more specifically the convex analysis in Riemannian manifolds, can be used to solve nonconvex constrained problem in Euclidean, space.     

关于平面点集三角剖分的两类子集

给定欧氏平面上的一个点集合Ｓ，我们给出两类端点在Ｓ中的线段集合，第一类线段集合是Ｓ的任一三角剖分的子集，第二类线段集合是Ｓ的任一最小权三解剖分的子集，这两类子集是不相交的，这两类子集合的计算要用Ｏ(n³)时间和Ｏ（ｎ）空间．     

Rigidity of Noncompact Finsler Manifolds

For a Euclidean space or a Minkowski space, we change the metric in a compact subset and show that the resulting Finsler manifold is isometric to the original standard space under certain conditions. We assume that the mean tangent curvature vanishes and the metric satisfies some curvature conditions or have no conjugate points.     

Delaunay Triangulation of Manifolds

We present an algorithm for producing Delaunay triangulations of manifolds. The algorithm can accommodate abstract manifolds that are not presented as submanifolds of Euclidean space. Given a set of sample points and an atlas on a compact manifold, a manifold Delaunay complex is produced for a perturbed point set provided the transition functions are bi-Lipschitz with a constant close to 1, and the original sample points meet a local density requirement; no smoothness assumptions are required. If the transition functions are smooth, the output is a triangulation of the manifold. The output complex is naturally endowed with a piecewise-flat metric which, when the original manifold is Riemannian, is a close approximation of the original Riemannian metric. In this case the output complex is also a Delaunay triangulation of its vertices with respect to this piecewise-flat metric.     

Caratterizzazione degli insiemi Δ n e Δ∞ di Vitali per classi di funzioni definite su insiemi compatti e numerabili

Continuous functions defined on countable compact subset of Euclidean spaces and functions with discontinuities of the first kind defined on countable set of the reals are studied. For both classes of functions results which characterize the Vitali Δ _n — and Δ_∞ — sets are obtained.     

A weak characterisation of the Delaunay triangulation

We consider a new construction, the weak Delaunay triangulation of a finite point set in a metric space, which contains as a subcomplex the traditional (strong) Delaunay triangulation. The two simplicial complexes turn out to be equal for point sets in Euclidean space, as well as in the (hemi)sphere, hyperbolic space, and certain other geometries. There are weighted and approximate versions of the weak and strong complexes in all these geometries, and we prove equality theorems in those cases also. On the other hand, for discrete metric spaces the weak and strong complexes are decidedly different. We give a short empirical demonstration that weak Delaunay complexes can lead to dramatically clean results in the problem of estimating the homology groups of a manifold represented by a finite point sample.      

Local Schr?dinger flow into K?hler manifolds

In this paper we show that there exists a unique local smooth solution for the Cauchy problem of the Schr?dinger flow for maps from a compact Riemannian manifold into a complete K?hler manifold, or from a Euclidean space R^m into a compact K?hler manifold. As a consequence, we prove that Heisenberg spin system is locally well-posed in the appropriate Sobolev spaces.     

Maximal integral point sets in affine planes over finite fields

Motivated by integral point sets in the Euclidean plane, we consider integral point sets in affine planes over finite fields. An integral point set is a set of points in the affine plane over a finite field F_q, where the formally defined squared Euclidean distance of every pair of points is a square in F_q. It turns out that integral point sets over F_q can also be characterized as affine point sets determining certain prescribed directions, which gives a relation to the work of Blokhuis. Furthermore, in one important sub-case, integral point sets can be restated as cliques in Paley graphs of square order.In this article we give new results on the automorphisms of integral point sets and classify maximal integral point sets over F_q for q≤47. Furthermore, we give two series of maximal integral point sets and prove their maximality.     

Torus Actions of Complexity 1 and Their Local Properties

We consider an effective action of a compact (n ? 1)-torus on a smooth 2n-manifold with isolated fixed points. We prove that under certain conditions the orbit space is a closed topological manifold. In particular, this holds for certain torus actions with disconnected stabilizers. There is a filtration of the orbit manifold by orbit dimensions. The subset of orbits of dimensions less than n ? 1 has a specific topology, which is axiomatized in the notion of a sponge. In many cases the original manifold can be recovered from its orbit manifold, the sponge, and the weights of tangent representations at fixed points. We elaborate on the introduced notions using specific examples: the Grassmann manifold G_4,2, the complete flag manifold F₃, and quasitoric manifolds with an induced action of a subtorus of complexity 1.     

Incompatible elasticity and the immersion of non-flat Riemannian manifolds in Euclidean space

We study a geometric problem that originates from theories of nonlinear elasticity: given a non-flat n-dimensional Riemannian manifold with boundary, homeomorphic to a bounded subset of ? ⁿ , what is the minimum amount of deformation required in order to immerse it in a Euclidean space of the same dimension? The amount of deformation, which in the physical context is an elastic energy, is quantified by an average over a local metric discrepancy. We derive an explicit lower bound for this energy for the case where the scalar curvature of the manifold is non-negative. For n = 2 we generalize the result for surfaces of arbitrary curvature.     

Some combinatorial properties of centrosymmetric matrices

The elements in the group of centrosymmetric n×n permutation matrices are the extreme points of a convex subset of n²-dimensional Euclidean space, which we characterize by a very simple set of linear inequalities, thereby providing an interesting solvable case of a difficult problem posed by L. Mirsky, as well as a new analogue of the famous theorem on doubly stochastic matrices due to G. Birkhoff. Several further theorems of a related nature also are included.