اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدReconstruction in one dimension from unlabeled Euclidean lengths
294
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $G$ be a $3$-connected graph with $n$ vertices and $m$ edges. Let $mathbf{p}$ be a randomly chosen mapping of these $n$ vertices to the integer range $[1..2^b]$ for $bge m^2$. Let $mathbf{l}$ be the vector of $m$ Euclidean lengths of $G$s edges under $mathbf{p}$. In this paper, we show that, WHP over $mathbf{p}$, we can efficiently reconstruct both $G$ and $mathbf{p}$ from $mathbf{l}$. In contrast to this average case complexity, this reconstruction problem is NP-HARD in the worst case. In fact, even the labeled version of this problem (reconstructing $mathbf{p}$ given both $G$ and $mathbf{l}$) is NP-HARD. We also show that our results stand in the presence of small amounts of error in $mathbf{l}$, and in the real setting with approximate length measurements. Our method is based on older ideas that apply lattice reduction to solve certain SUBSET-SUM problems, WHP. We also rely on an algorithm of Seymour that can efficiently reconstruct a graph given an independence oracle for its matroid.
قيم البحث
اقرأ أيضاً
Let $mathbf{p}$ be a configuration of $n$ points in $mathbb{R}^d$ for some $n$ and some $d ge 2$. Each pair of points defines an edge, which has a Euclidean length in the configuration. A path is an ordered sequence of the points, and a loop is a pat
h that has the same endpoints. A path or loop, as a sequence of edges, also has a Euclidean length, which is simply the sum of its Euclidean edge lengths. We are interested in reconstructing $mathbf{p}$ given a set of edge, path and loop lengths. In particular, we consider the unlabeled setting where the lengths are given simply as a set of real numbers, and are not labeled with the combinatorial data describing which paths or loops gave rise to these lengths. In this paper, we study the question of when $mathbf{p}$ will be uniquely determined (up to an unknowable Euclidean transform) from some given set of path or loop lengths through an exhaustive trilateration process. Such a process has been already been used for the simpler problem of unlabeled edge lengths.
Let $mathbf{p}$ be a configuration of $n$ points in $mathbb{R}^d$ for some $n$ and some $d ge 2$. Each pair of points has a Euclidean length in the configuration. Given some graph $G$ on $n$ vertices, we measure the point-pair lengths corresponding t
o the edges of $G$. In this paper, we study the question of when a generic $mathbf{p}$ in $d$ dimensions will be uniquely determined (up to an unknowable Euclidean transformation) from a given set of point-pair lengths together with knowledge of $d$ and $n$. In this setting the lengths are given simply as a set of real numbers; they are not labeled with the combinatorial data that describes which point-pair gave rise to which length, nor is data about $G$ given. We show, perhaps surprisingly, that in terms of generic uniqueness, labels have no effect. A generic configuration is determined by an unlabeled set of point-pair lengths (together with $d$ and $n$) iff it is determined by the labeled edge lengths.
A subset $X$ in the $d$-dimensional Euclidean space is called a $k$-distance set if there are exactly $k$ distances between two distinct points in $X$. Einhorn and Schoenberg conjectured that the vertices of the regular icosahedron is the only 12-poi
nt three-distance set in $mathbb{R}^3$ up to isomorphism. In this paper, we prove the uniqueness of 12-point three-distance sets in $mathbb{R}^3$.
A bar-joint framework $(G,p)$ in a (non-Euclidean) real normed plane $X$ is the combination of a finite, simple graph $G$ and a placement $p$ of the vertices in $X$. A framework $(G,p)$ is globally rigid in $X$ if every other framework $(G,q)$ in $X$
with the same edge lengths as $(G,p)$ arises from an isometry of $X$. The weaker property of local rigidity in normed planes (where only $(G,q)$ within a neighbourhood of $(G,p)$ are considered) has been studied by several researchers over the last 5 years after being introduced by Kitson and Power for $ell_p$-norms. However global rigidity is an unexplored area for general normed spaces, despite being intensely studied in the Euclidean context by many groups over the last 40 years. In order to understand global rigidity in $X$, we introduce new generalised rigid body motions in normed planes where the norm is determined by an analytic function. This theory allows us to deduce several geometric and combinatorial results concerning the global rigidity of bar-joint frameworks in $X$.
In this note, we give a short solution of the kissing number problem in dimension three.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
