اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOpen Problem Statement: Minimal Distortion Embeddings of Diversities in $ell_1$
46
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We state an open problem in the theory of diversities: what is the worst case minimal distortion embedding of a diversity on $n$ points in $ell_1$. This problem is the diversity analogue of a famous problem in metric geometry: what is the worst case minimal distortion embedding of an $n$-point metric space in $ell_1$. We explain the problem, state some special classes of diversities for which the answer is known, and show why the standard techniques from the metric space case do not work. We then outline some possible lines of attack for the problem that are not yet fully explored.
قيم البحث
اقرأ أيضاً
Diversities are a generalization of metric spaces, where instead of the non-negative function being defined on pairs of points, it is defined on arbitrary finite sets of points. Diversities have a well-developed theory. This includes the concept of a
diversity tight span that extends the metric tight span in a natural way. Here we explore the generalization of diversities to lattices. Instead of defining diversities on finite subsets of a set we consider diversities defined on members of an arbitrary lattice (with a 0). We show that many of the basic properties of diversities continue to hold. However, the natural map from a lattice diversity to its tight span is not a lattice homomorphism, preventing the development of a complete tight span theory as in the metric and diversity cases.
Diversities are a generalization of metric spaces in which a non-negative value is assigned to all finite subsets of a set, rather than just to pairs of points. Here we provide an analogue of the theory of negative type metrics for diversities. We in
troduce negative type diversities, and show that, as in the metric space case, they are a generalization of $L_1$-embeddable diversities. We provide a number of characterizations of negative type diversities, including a geometric characterisation. Much of the recent interest in negative type metrics stems from the connections between metric embeddings and approximation algorithms. We extend some of this work into the diversity setting, showing that lower bounds for embeddings of negative type metrics into $L_1$ can be extended to diversities by using recently established extremal results on hypergraphs.
Let $Dgeq 2$, $Ssubset mathbb R^D$ be finite and let $phi:Sto mathbb R^D$ with $phi$ a small distortion on $S$. We solve the Whitney extension-interpolation-alignment problem of how to understand when $phi$ can be extended to a function $Phi:mathbb R
^Dto mathbb R^D$ which is a smooth small distortion on $mathbb R^D$. Our main results are in addition to Whitney extensions, results on interpolation and alignment of data in $mathbb R^D$ and complement those of [14,15,20].
A quasiconformal tree is a doubling metric tree in which the diameter of each arc is bounded above by a fixed multiple of the distance between its endpoints. In this paper we show that every quasiconformal tree bi-Lipschitz embeds in some Euclidean s
pace, with the ambient dimension and the bi-Lipschitz constant depending only on the doubling and bounded turning constants of the tree. This answers Question 1.6 in cite{DV} (arXiv:2007.12297).
The approximation of a circle with a fine square grid distorts the perimeter by a factor of $tfrac{4}{pi}$. We prove that this factor is the same on average for approximations of any curve with any Delaunay mosaic (known as Voronoi path), and extend
the results to all dimensions, generalizing Voronoi paths to Voronoi scapes.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
