Что известно о следующей проблеме? Для набора функций : f : { 0 , 1 } n → { 0 , 1 } найдите наибольшую подгруппу S ⊆ C с учетом ограничения VC-Dimension ( S ) ≤ k для некоторого целого числа k .СCCе: { 0 , 1 }N→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆ CS⊆CS \subseteq C( S) ≤...
Задача традиционной художественной галереи устанавливает регион и охранников с некоторым представлением о видимости и требует минимального количества охранников, которые необходимо разместить, чтобы увидеть весь регион. Кто-нибудь когда-нибудь смотрел варианты художественной галереи, где область...
Лемма Джонсона-Линденштрауса грубо говорит о том, что для любого набора из точек в существует карта где такой, что для всех : Известно, что подобные выражения невозможны для метрики , но известно, есть ли способ обойти такое низкое значение границы, предлагая более слабые гарантии? Например, может...
Согласно книге «Топологическая теория графов» Гросса и Такера, учитывая клеточное вложение графа на поверхность (под «поверхностью» я подразумеваю здесь сферу с некоторыми ручками , а ниже S n относится к сфере с ровно n ручками), можно определить двойной мультиграф, рассматривая грани исходного...
Для двух подмножеств мерного гиперкуба (т. Е. M , N ⊆ { 0 , 1 } d ) я ищу алгоритм, который извлекает точки m ∈ M , n ∈ N на расстоянии Хэмминга (или L 1 - расстояние по гиперкубу) d H ( m , n ) минимально. Наивный алгоритм, который проверяет только каждую пару | М | ⋅ | N | ⋅ дdddM, N⊆ { 0 , 1...
Я пытаюсь покрыть простой вогнутый многоугольник с минимумом прямоугольников. Мои прямоугольники могут быть любой длины, но они имеют максимальную ширину, и у многоугольника никогда не будет острого угла. Я думал о попытке разложить мой вогнутый многоугольник на треугольники, которые создают набор...
Для заданного набора гиперплоскостей, определяемых нормальными векторами , его типами ячеек (или знаковыми векторами) являются все векторы t ∈ { + , - } m, для которых существует вектор v ∈ R d так , что ⟨ v , ч я ⟩ ≠ 0 и т я = знак ( ⟨ v , ч я ⟩ )h1,…,hm∈Rdh1,…,hm∈Rdh_1,\dots,h_m \in \mathbf...
Была ли работа по восстановлению наклона отрезка линии после его оцифровки? Конечно, нельзя делать это с идеальной точностью; то, что нужно, - это метод получения из оцифрованной линии интервала возможных уклонов. (Понятие оцифрованной строки, которую я использую, - это Розенфельд: набор пар где...
(X,d)(X,d)(X, d)(Y,f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X \rightarrow Yμμ\muρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)}ρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)} \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \} Есть и другие показатели качества:...
Следующие упражнения были розданы студентам, которых я курирую: Учитывая точек на плоскости, разработайте алгоритм, который находит пару точек, расстояние которых минимально среди всех пар точек. Алгоритм должен работать за время o ( n 2 ) .nnno(n2)o(n2)o(n^2) Существует (относительно) простой...
Входные данные: набор из точек в и целое число .nnnR3R3\mathbb{R}^3k≤nk≤nk \le n Выход: наименьший ограничивающий прямоугольник, выровненный по оси объема, который содержит не менее из этих точек.kkknnn Мне интересно, если какие-либо алгоритмы известны для этой проблемы. Лучшее, что я мог...
В SODA 1995 года Джефф Эриксон показал нижние оценки линейной выполнимости (проверяя, удовлетворяет ли некоторое подмножество действительных чисел линейному уравнению на переменных). Метод доказательства использует бесконечно малые и принцип переноса Тарского .н рrrrnnnrrr Может ли кто-нибудь...
Для заданного набора из точек в d- мерном евклидовом пространстве задача состоит в том, чтобы определить, содержит ли выпуклая оболочка единичный шарик с центром в начале координат.NNnddd Эта проблема в NP? Это в co-NP, поскольку можно указать точку в шаре вне выпуклой оболочки в качестве свидетеля...
Какова текущая наилучшая граница для выполнения запросов подсчета диапазона полупространства для набора мерных точек, выраженного в форме компромисса времени / пространства. Согласно основополагающей работе Матусека 1993 года (теорема 6.2, Поиск диапазона с эффективными иерархическими вырезами), мы...
Пусть граф с (положительно) взвешенными ребрами. Я хочу определить диаграмму Вороного для набора узлов / сайтов S , чтобы связать с узлом v ∈ S подграф R ( v ) группы G, индуцированный всеми узлами строго ближе к v, чем к любому другому узлу в S , измеряя длина пути по сумме весов на дугах. R ( v )...
Пусть - множество из N точек в R d . Для любого т ≥ 1 , A т -spanner представляет собой неориентированный граф G = ( Р , Е ) , взвешенный в соответствии с евклидовыми мерами, таким , что для любых двух точек V , U , самое короткое расстояние в G , d ( v , у ) , не более чем в t раз евклидово...
Предположим, у меня есть простой многоугольник и целое число k . Каковы некоторые существующие подходы для нахождения наименьшего радиуса ¨R таким образом, что я могу покрыть S с K окружностей радиуса г ? Как насчет, если г фиксирован, и я хочу минимизировать к...
Учитывая набор точек в трехмерном декартовом пространстве, я ищу алгоритм, который будет сортировать эти точки так, чтобы минимальное евклидово расстояние между двумя последовательными точками было бы максимальным. Было бы также полезно, если бы алгоритм имел тенденцию к увеличению среднего...
Теорема о зоне гласит, что если мы нанесем на карту расположение n линий с другой линией, общая сложность ее зоны , множества смежных с ней 0-, 1- и 2-граней, будет O (n). Фактическая константа примерно равна 6n, по крайней мере, как указано в различных учебниках, и доказательство по индукции с...
Сумма Минковского двух множеств векторов имеет видA , B ∈ RdA,B∈RdA, B \in R^d A ⊕ B = { a + b ∣ a ∈ A , b ∈ B }A⊕B={a+b∣a∈A,b∈B} A \oplus B = \{ a + b \mid a \in A, b \in B \} Я только что услышал интересную проблему (приписываемое Dan Гальперина): Учитывая форма , существует ли форма А такое ,...