Reconstructing sets from distances given by graphs (コンピュテーション)

概要

論文の詳細を見る
Given n points in some Euclidean space, (^n_2) pairwise distances among the points can be easily calculated. On the other hand, it is not always possible to reconstruct a point set up to motion uniquely from a multiset of (^n_2) distances, and the computational complexity for the reconstruction is not known even if it uniquely exists. Therefore, it is a natural question to ask how much additional information is required for designing an efficient reconstruction algorithm. It becomes trivial if we know which distance corresponds to which pair of points; that is, we have a distance matrix instead of a multiset of distances. Our interest is that "what if we have a partial distance matrix?" Thus, we consider the case where partial information about the distance matrix is given: Precisely, we are given an weighted graph G=(V,E) and find an embedding of V into an Euclidean space such that the weight w(e) of each edge e gives the Euclidean distance between embedded points. Unfortunately, this problem is known to be strongly NP-hard for any Euclidean space R^d in general. In this paper, we discuss complexity of the problem for important families of graphs. We first present a polynomial-time algorithm to embed chordal graphs into R^d for any positive integer d. Then, we prove that although embedding cycles in a line is NP-hard, it becomes easy in higher-dimensions. We also give a polynomial-time algorithm to find a point set on a line from distance information given as a graph with a small connected dominating set.
2011-04-15

Reconstructing sets from distances given by graphs (コンピュテーション)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク