В SODA 1995 года Джефф Эриксон показал нижние оценки линейной выполнимости (проверяя, удовлетворяет ли некоторое подмножество действительных чисел линейному уравнению на переменных). Метод доказательства использует бесконечно малые и принцип переноса Тарского .н рrrrnnnrrr Может ли кто-нибудь...
Какова текущая наилучшая граница для выполнения запросов подсчета диапазона полупространства для набора мерных точек, выраженного в форме компромисса времени / пространства. Согласно основополагающей работе Матусека 1993 года (теорема 6.2, Поиск диапазона с эффективными иерархическими вырезами), мы...
Я работаю в области структурной инженерии, и я хотел бы найти эффективный алгоритм для построения приближения (в метрике Хаусдорфа) выпуклого тела КKK выпуклой оболочкой Nnn эллипсоиды, для некоторых фиксированных Nnn, В настоящее время я работаю только в измерениях 2 и 3. Моей первой идеей было...
Я ищу алгоритм для рисования смешанного графа групп интересов / зависимостей (для лингвистического приложения). Такой граф будет иметь два разных типа вершин (токены, узлы) и два разных типа ребер (иерархические, неиерархические). Я новичок в теории графов и алгоритмах в целом, и я надеюсь, что...
Для применения машинного обучения моя группа должна рассчитать евклидово расстояние до Кkkближайший сосед в наборе ИксXX для каждого x∈(X∪Y)⊂Rdx∈(X∪Y)⊂Rdx \in (X \cup Y) \subset \mathbb R^d (за ddd от 5 до 100, и |X|≈|Y||X|≈|Y||X| \approx |Y|от нескольких сотен до нескольких миллионов). В настоящее...
Триангуляции Делоне на плоскости максимизируют минимальный угол в треугольнике. Справедливо ли то же самое для триангуляции Делоне точек на сфере? (здесь «угол» - это локальный угол в окрестности вокруг вершины на вершине). Вдохновленный, но не связанный с этим вопросом на...
Предположим, у меня есть Кkk указывает на RdRd\mathbb{R}^d, Они вызывают диаграмму Вороного. Если я назначу каждому изkkk указывает ±±\pm метка, они вызывают двоичную функцию на RdRd\mathbb{R}^d, Вопрос: какова VC-размерность всех таких возможных бинарных функций, вызванных некоторымиkkk очки и...
Позволять SSSбыть единым квадратом. Как функцияββ\betaкакое максимальное количество ββ\beta-жирных попарно непересекающихся областей диаметром не менее 1, которые могут пересекатьсяSSS? Ниже мы приводим рисунок, показывающий, что для β=1β=1\beta=1Максимальное количество равно 7. Как насчет для...
Вот проблема ближайшего соседа. Учитывая реалы a1, ... ,aNa1,…,ana_1, \ldots, a_n (очень большой Nnn!), плюс цель реальная пpp, найти aяaia_i а также aJaja_j чья сумма ближе всего пpp, Мы разрешаем разумную предварительную обработку / индексациюa1, ... ,aNa1,…,ana_1, \ldots, a_n (вплоть до O ( n...
Я хотел бы извиниться перед всеми постами ниже. Выбрал не тот форум, чтобы опубликовать это в оригинале. Однако вместо того, чтобы сделать это пустой тратой, я переработал вопрос, чтобы он стал настоящей проблемой «теоретической информатики». Задача: Создать алгоритм, который принимает набор из n...
Я ищу VC-размерность следующей заданной системы. вселенная U= {п1,п2, ... ,пм}U={p1,p2,…,pm}U=\{p_1,p_2,\ldots,p_m\} такой, что U⊆р3U⊆R3U\subseteq \mathbb{R}^3, В заданной системерR\mathcal{R} каждый набор S∈ RS∈RS\in \mathcal{R} соответствует сфере в R3R3\mathbb{R}^3 такой, что множество SSS...
В капаситированных Facility Местоположение задачи (CFLP) , нам дано множество клиентов и набор потенциальных объектов . У каждого клиента есть спрос который должен обслуживаться одним или несколькими открытыми средствами. Каждый объект имеет стоимость открытия и имеет емкость , что является...
Мне было трудно найти алгоритм или опубликовать статьи о триангуляции самопересекающегося многоугольника (также многоугольника со структурой дырок). Может, кто-нибудь поможет мне найти опубликованную статью / алгоритм, пожалуйста? PS: кто-то пометит этот вопрос соответствующим образом, пожалуйста,...
Я ищу программное обеспечение для вычисления / оценки объема многомерных выпуклых многогранников. В частности, я заинтересован в программе, которая может обрабатывать тела сNNn вершины в dddпространство с параметрами, ограниченными примерно следующим образом: d≤ 50d≤50d \le 50 а также n ≤...
В [1] Garey et al. определите то, что позже будет известно как проблема суммы квадратных корней в ходе разработки NP-полноты евклидовой TSP. Даны целые числа a1,a2,…,ana1,a2,…,ana_1, a_2, \ldots, a_n а также LLLопределить, если a1−−√+a2−−√+⋯+an−−√<La1+a2+⋯+an<L\sqrt{a_1} + \sqrt{a_2} + \cdots...