Набор расстояний - Distance set
В геометрия, то набор расстояний набора баллов набор из расстояния между различными парами точек. Таким образом, его можно рассматривать как обобщение набор различий, набор расстояний (и их отрицания) в наборах чисел.
Некоторые проблемы и результаты в геометрии касаются наборов расстояний, обычно основанных на том принципе, что большой набор точек должен иметь большой набор расстояний (для различных определений «большого»):
- Гипотеза Фальконера это утверждение, что для набора точек в -мерное пространство, имеющее Хаусдорфово измерение больше, чем , соответствующий набор расстояний имеет ненулевые Мера Лебега. Хотя частичные результаты известны, гипотеза остается недоказанной.[1]
- В Проблема Эрдеша – Улама спрашивает, возможно ли плотный набор в Евклидова плоскость набор расстояний состоит только из рациональное число. Опять же, это остается нерешенным.[2]
- Теорема Ферма о суммах двух квадратов характеризует числа в множестве расстояний двумерного целочисленная решетка: они являются квадратными корнями из целых чисел, разложение на простые множители которых не содержит нечетного числа копий любого простого числа, конгруэнтного 3 по модулю 4. Аналогично, Теорема Лежандра о трех квадратах характеризует набор расстояний трехмерной целочисленной решетки, а Теорема Лагранжа о четырех квадратах характеризует набор расстояний целочисленных решеток в четырех и более высоких измерениях как квадратные корни из целых чисел без каких-либо дополнительных ограничений. В решетках пяти или более измерений каждое подмножество решетки с ненулевым верхняя плотность имеет набор расстояний, содержащий квадраты бесконечного арифметическая прогрессия.[3]
- Согласно Теорема Эрдеша – Эннинга, каждый бесконечный набор точек в евклидовой плоскости, который не лежит на одной прямой, имеет нецелое число в своем наборе расстояний.[4]
- Квадратные сетки точек имеют наборы расстояний сублинейного размера, в отличие от точек в общая позиция набор расстояний квадратичный по размеру. Однако согласно решению 2015 г. Проблема различных расстояний Эрдеша к Ларри Гут и Нетс Кац, набор расстояний любого конечного набора точек на евклидовой плоскости лишь слегка сублинейен, почти такой же большой, как данный набор.[5] В частности, только конечный набор точек может иметь конечный набор расстояний.
- А Правитель голомба - конечный набор точек на прямой такой, что никакие две пары точек не имеют одинакового расстояния. Софи Пикар утверждал, что никакие два правителя Голомба не имеют одинаковых наборов расстояний. Утверждение неверно, но есть только один контрпример, пара шестиконечных линейок Голомба с общим набором расстояний.[6]
- В равносторонний размер из метрическое пространство - это наибольший размер набора точек, набор расстояний которых состоит только из одного элемента. Гипотеза Куснера утверждает, что равностороннее измерение -мерное пространство с Манхэттенское расстояние точно , но это остается недоказанным.[7]
Наборы расстояний также использовались как дескриптор формы в компьютерное зрение.[8]
Рекомендации
- ^ Арутюнянц, Г .; Иосевич, А. (2004), "Гипотеза Фальконера, сферические средние и дискретные аналоги", в Пах, Янош (ред.), К теории геометрических графов, Contemp. Математика, 342, Амер. Математика. Soc., Providence, RI, стр. 15–24, Дои:10.1090 / conm / 342/06127, МИСТЕР 2065249
- ^ Клее, Виктор; Вагон, Стан (1991), "Проблема 10 Есть ли на плоскости плотное рациональное множество?", Старые и новые нерешенные задачи плоской геометрии и теории чисел, Математические экспозиции Дольчиани, 11, Cambridge University Press, стр. 132–135, ISBN 978-0-88385-315-3.
- ^ Мадьяр, Акос (2008), "О наборах расстояний больших наборов целочисленных точек", Израильский математический журнал, 164: 251–263, Дои:10.1007 / s11856-008-0028-z, МИСТЕР 2391148, S2CID 17629304
- ^ Эннинг, Норман Х .; Эрдеш, Пол (1945), «Интегральные расстояния», Бюллетень Американского математического общества, 51 (8): 598–600, Дои:10.1090 / S0002-9904-1945-08407-9.
- ^ Гут, Ларри; Кац, Нетс Хок (2015), "О проблеме различных расстояний Эрдеша на плоскости", Анналы математики, 181 (1): 155–190, arXiv:1011.4105, Дои:10.4007 / анналы.2015.181.1.2, МИСТЕР 3272924
- ^ Бекир, Ахмад; Голомб, Соломон В. (2007), «Других контрпримеров к теореме С. Пикара нет», IEEE Transactions по теории информации, 53 (8): 2864–2867, Дои:10.1109 / TIT.2007.899468, МИСТЕР 2400501, S2CID 16689687
- ^ Кулен, Джек; Лоран, Моник; Шрайвер, Александр (2000), «Равностороннее измерение прямолинейного пространства», Конструкции, коды и криптография, 21 (1): 149–164, Дои:10.1023 / А: 1008391712305, МИСТЕР 1801196, S2CID 9391925
- ^ Grigorescu, C .; Петков, Н. (октябрь 2003 г.), «Наборы расстояний для фильтров формы и распознавания форм» (PDF), IEEE Transactions по обработке изображений, 12 (10): 1274–1286, Дои:10.1109 / tip.2003.816010, PMID 18237892