Известно , что дано - точечное подмножество (то есть, заданный точек в с евклидовым расстоянием) можно вставлять их изометрический в .
Является ли изометрия вычислимой за (возможно, рандомизированное) полиномиальное время?
Поскольку существуют проблемы с конечной точностью, точный вопрос
Для заданного множества из точек в и существует ли отображение вычисляемое (возможно, с использованием случайности) в полином по времени от и логарифмический по такой, что для каждого имеем
(Примечание: мне известно, что отображение с искажением можно найти с высокой вероятностью по полиному по времени от и , проецируя на случайные линии, но я не уверен, можно ли конструктивно уменьшить число измерений до или даже когда намного больше , и я не знаю, есть ли метод полиномиального времени для обработки случая, когда экспоненциально по .)
источник
Ответы:
Суреш попросил меня собрать мои комментарии выше в ответ, так что вот оно. Я не совсем уверен, что это ответ на первоначальный вопрос, так как не очевидно, как сделать это полиномиальным временем, когда размерность входного евклидова пространства непостоянна. По крайней мере, у него есть преимущество в том, чтобы избежать любой проблемы с большим как задает оригинальный вопрос, потому что он не включает в себя никакого приближения и выглядит многочленным для константы .1/ϵ d
В любом случае: из интегральной геометрии существует стандартная мера на множествах гиперплоскостей в мерном евклидовом пространстве, инвариантная относительно евклидовых конгруэнций. Свойство состоит в том, что длина любой кривой ограниченной длины пропорциональна мере гиперплоскостей, пересекающих (с кратностью, что означает, что если гиперплоскость пересекает дважды, то она вносит двойной вклад в общую меру гиперплоскостей, пересекающих ). В частности, если является отрезком прямой, усложнение множественности не возникает, и мы можем нормализовать меру на гиперплоскостях, пересекающих точно равной длинеd C C C C C C C , (Гиперплоскости, содержащие имеют нулевую меру, поэтому не беспокойтесь о бесконечной кратности.)C
Теперь, учитывая набор из n точек в d-мерном пространстве, сделайте координату для каждого из разбиений точек на два подмножества, индуцированных гиперплоскостью, которая не проходит ни через одну из точек. Приведите точки на одной стороне значения координаты разбиения к нулю, а точки на другой стороне значения координаты разбиения равны мере набора гиперплоскостей, индуцирующих это разбиение.ℓ1
Если и - любые две из точек, пусть - множество гиперплоскостей, пересекающих отрезок прямой , и пусть - подмножества образованные каждым возможным разбиением гиперплоскости, у которого на одной стороне и на другой. Тогда является непересекающимся объединением , а разности координат между и являются просто мерами подмножеств . Следовательно, расстояние между координатами иp q n K pq Ki K p q K Ki p q Ki ℓ1 p q (сумма мер ) является мерой , которая является просто исходным расстоянием между и .Ki K ℓ2 p q
Для вычислительных геометров может быть полезно альтернативное описание той же конструкции: используйте проективную двойственность для преобразования входных точек в гиперплоскостей и разделения гиперплоскостей на точки. Мера интегральной геометрии на наборах гиперплоскостей затем преобразуется в более стандартную меру на наборах точек, расстояние между и удваивается к мере двойного клина между двумя гиперплоскостями, а расположение гиперплоскости разбивает этот двойной клин на меньшие ячейки , Значение координаты для точки является либо мерой одной из ячеек в расположении (если двойная гиперплоскость находится ниже ячейки этой координаты), либо нулем (если двойная гиперплоскость находится выше ячейки). Следовательноn n p q ℓ1 Расстояние между и - это просто сумма мер ячеек в двойном клине, которая совпадает с мерой всего двойного клина. Эта двойная точка зрения также позволяет легко вычислить размерность вложения, найденного таким образом: это просто число ячеек в расположении гиперплоскости, которое равно , или, точнее, самое большее .p q O(nd) ∑di=0(ni)
Пока что это дает полностью детерминированное и точное вложение в . Но мы хотели меньшее измерение, . Вот где вступает комментарий Луки о теореме Каратеодори . Множество представимых метрик образует многогранный конус в мерном пространстве всех функций от неупорядоченных пар точек до действительных чисел, а приведенный выше геометрический аргумент говорит, что евклидова метрика принадлежит этому конусу. Точки на крайних лучах конуса являются одномернымиℓO(nd)1 ℓ(n2)1 ℓ1 (n2) ℓ1 псевдометрика (в которой точки делятся на два набора, все расстояния в одном наборе равны нулю, а все расстояния через разбиение равны), и Каратеодори говорит, что любая точка в конусе (включая ту, которая нам нужна) может быть представленный в виде выпуклой комбинации точек на экстремальных лучах, число которых не превосходит размерности окружающего пространства, . Но выпуклая комбинация не более чем одномерные метрики является метрикой .(n2) (n2) ℓ1 ℓ(n2)1
Наконец, как мы можем на самом деле вычислить мерное вложение? На данный момент у нас есть не только точка в мерный выпуклый конус метрики (метрика расстояния, с которой мы начали), но у нас также есть множество крайних точек конуса (соответствует разбиению входных данных на два подмножества, индуцированных гиперплоскостями), так что наша метрика представляет собой выпуклую комбинацию этих крайних точек - для малых это большое улучшение по сравнению с крайними лучами, которые имеет конус в целом. Теперь все, что нам нужно сделать, это применить жадный алгоритм, который избавляет от крайних точек из нашего множества, один за другим, пока только(n2) (n2) ℓ1 O(nd) d 2n−2 (n2) из них остались. На каждом этапе нам нужно поддерживать в качестве инварианта, что наша метрика все еще находится внутри выпуклой оболочки оставшихся крайних точек, что является просто проблемой выполнимости линейного программирования, и если мы сделаем это, Каратеодори будет гарантировать, что всегда остается набор крайние точки, выпуклая оболочка которых содержит входную метрику.(n2)
источник