Лучший способ определить минимальный размер конструкции с учетом только расстояний между точками

Я сталкивался с этой проблемой в области физики, довольно далекой от компьютерных наук, но это похоже на вопрос, который был изучен в CS, поэтому я решил попытать счастья, задав его здесь.

Представьте, что вам дан набор точек и список некоторых расстояний между точками . Как наиболее эффективно определить минимальную размерность пространства, в которое нужно вложить эти точки? Другими словами, что является наименьшим таким, что в существует множество точек, удовлетворяющих ограничениям на расстояние . Я был бы одинаково счастлив с ответом для $\{v_i\}_{i=1}^n$ $d_{ij}$ $k$ $\mathbb{R}^k$ $d_{ij}$ , но это кажется более трудным. $\mathbb{C}^k$

Я счастлив сказать, что расстояния должны соответствовать $d_{ij}$ только с точностью до некоторой постоянной и иметь точки ограничены точки на некоторой решетке постоянного расстояниятого, чтобы вопросыИЗБЕЖАТЬ вычислительный с реалом. $\epsilon$

Действительно, я был бы весьма доволен решением для версии решения этой проблемы, где при заданных и вас спрашивают, существует ли такой набор вершин . Тривиально проблема в NP, так как задан набор точек в $d_{ij}$ $k$ $\{v_i\}$ $\mathbb{R}^k$ легко проверить, что они удовлетворяют требованиям к расстоянию, но кажется, что для этой конкретной задачи должны быть субэкспоненциальные алгоритмы времени.

Наиболее очевидный подход , как представляется, чтобы попытаться построить $k$ мерные структуры итеративно, добавляя дополнительные точки по одной и определяя, нужно ли добавлять новое пространственное измерение на каждой итерации. Проблема в том, что кажется, что вы можете столкнуться с неоднозначностью, когда существует несколько способов добавить точку в существующую структуру, и неясно, какой из них приведет к меньшему количеству измерений, поскольку вы продолжаете добавлять больше точек.

Наконец, позвольте мне сказать, что я знаю, что легко создать списки расстояний, которые не могут быть выполнены в любом количестве измерений (то есть тех, которые нарушают неравенство треугольника). Однако для тех случаев, которые меня интересуют, всегда будет какое-то минимальное конечное число измерений, в которых можно найти удовлетворительный набор точек.

ds.algorithms cg.comp-geom Джо Фитцсимонс
источник

Я полагаю, вы хотите вложение в

ℓ_{2}

$\ell_2$

Суреш Венкат

@Suresh: Да, извините, я хотел добавить это.

Джо Фицсимонс

Кстати, из какой области физики это происходит?

Винаяк Патхак

@Vinayak: я только сталкивался с этим, пытаясь вычислить что-то в квантовой механике.

Джо Фицсимонс

Ответы:

Эту проблему иногда называют низкоразмерным евклидовым заполнением матрицы расстояний или низкоразмерным евклидовым вложением взвешенного графа.

Сакс [Sax79] и Йемини [Yem79] независимо показали простым сокращением проблемы разбиения, что эта задача NP-полна даже в случае одного измерения; то есть следующая задача является NP-полной при k = 1:

Завершение k- мерной евклидовой матрицы расстояний / k- мерное евклидово вложение взвешенного графа
Экземпляр : Симметричная матрица M , элементы которой являются либо положительными целыми числами в двоичной системе, либо «неизвестными».
Вопрос : Могут ли неизвестные записи в M быть заполнены действительными числами, так что M становится матрицей расстояний точек в k- мерном евклидовом пространстве ℝ^k ?
Эквивалентно,
Экземпляр : граф G, где каждое ребро имеет положительный целочисленный вес, записанный в двоичном виде.
Вопрос : Могут ли вершины G помещаться в kевклидово пространство ℝ ^k, так что для каждого ребра G расстояние между двумя конечными точками равно весу ребра?

Более того, Сакс [Sax79] показал (путем более сложного сокращения из 3SAT), что k- мерное евклидово расстояние до матрицы завершения остается NP-трудным даже при ограничении, что все известные записи в M либо 1, либо 2 для каждой положительной целочисленной константы. к . В частности, проблема является NP-полной, даже когда известны записи в M даны в унарном виде. [Sax79] также содержит некоторые результаты твердости о приближенном внедрении.

Между прочим, я не думаю, что это тривиально, что проблема в NP; обратите внимание, что вам нужны иррациональные координаты в некоторых случаях, когда к > 1. Я не знаю, если это известно, чтобы быть в NP.

Ссылки

[Sax79] Джеймс Б. Сакс. Встраиваемость взвешенных графов в k- пространстве сильно NP-трудна. В материалах 17-й конференции Аллертона по коммуникациям, управлению и вычислениям , с. 480–489, 1979. Также у Джеймса Б. Сакса: Две статьи по проблемам вложения графов , факультет компьютерных наук, Университет Карнеги-Меллона, 1980.

[Yem79] Йехиам Йемини. Некоторые теоретические аспекты проблем определения местоположения. В 20-м ежегодном симпозиуме по основам компьютерных наук (FOCS) , с. 1–8, октябрь 1979. DOI: 10.1109 / SFCS.1979.39

Цуёси Ито
источник

Благодарю. Конечно, в общем случае это не очевидно в NP, но если вы превратите это в многообещающую проблему, ограничив точки лежащими на решетке, и вместо этого получите квадрат расстояний, а не сами расстояния, тогда все квадратные расстояния являются целыми числами, и поэтому решение может быть проверено точно за полиномиальное время.

Джо Фицсимонс

$d$ $n$ $d$ $n$

Суреш Венкат
источник

Отлично, это может быть просто указатель мне нужен. Извините, что трачу ваше время, если это несколько тривиальный вопрос.

Джо Фицсимонс

Это не тривиально, если вы не копаетесь в геометрии расстояния :)

Суреш Венкат

Я прочитал ваш пост, и он определенно указывает мне верное направление. Однако я не совсем понимаю, как это будет применяться только с частичным набором расстояний. Не могли бы вы просветить меня?

Джо Фицсимонс

Ах, проблема, которую я понимаю, состоит в том, что это не обрабатывает частичный случай. :(

Суреш Венкат

@Joe: матрица расстояний удовлетворяет всем неравенствам отрицательного типа тогда и только тогда, когда соответствующая «матрица Грама» является положительной полуопределенной. (Я поместил «матрицу Грама» в страшные кавычки, потому что это не совсем матрица Грама, если расстояние не реализуемо в евклидовом пространстве.) Однако я не знаю, как справиться с ограничением на размерность, используя этот подход.

Цуёси Ито