Для заданных точек в R d и расстояния l найти наибольшее подмножество этих точек, такое, что евклидово расстояние ни одной из них не превышает l .p1,…,pnp1,…,pnp_1,\ldots,p_nRdRd\mathbb{R}^{d}llllll В чем сложность этой проблемы? На графике точек, имеющих ребро, когда расстояние между двумя точками...
Существуют ли сейчас более простые алгоритмы / доказательства триангуляции плоского многоугольника за линейное время? Что является хорошим ресурсом о состоянии этой знаменитой...
Какова вычислительная сложность следующей задачи: с учетом двух комплексных матриц A и B проверить, есть ли матрица перестановок Р таким образом, что: В = Р Р Т .n × nN×Nn\times nAAAВВBппPB = PА ПT,Взнак равнопAпT,B = P A P^T. Если это помогает, можно предположить, что и B эрмитовы (или даже что A...
Для плоского вложения плоского графа на плоскость с прямыми ребрами определите вершину как острую вершину, если максимальный угол между двумя последовательными ребрами вокруг нее больше 180. Или, другими словами, если существует линия, проходящая через это вершина вложения так, что все ребра,...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...
В этой статье Эрика Д. Деймэна, Сандора П. Фекете, Роберта Дж. Ланга «Упаковка кругов для дизайна оригами сложно» на странице 15, рис. 13, они утверждают, что длина стороны наименьшего квадрата, заключающего два круга области 1/2 каждый составляет 1,471299. По моим расчетам я получаю длину стороны...
Существует красивая теорема Кобе (см. Здесь ), которая гласит, что любой плоский граф можно нарисовать как целующий граф дисков (очень романтично ...). (Другими словами, любой плоский граф может быть нарисован как граф пересечений дисков.) Теорема Кебе не очень легко доказать. Мой вопрос:...
У меня есть серьезные проблемы с пониманием одного шага в статье Добкина и Киркпатрика о разделении многогранников. Я пытаюсь понять эту версию: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf Он утверждает, что после того, как мы знаем лучшее разделение и ,...
Этим летом я услышал, как Эмо Велцл говорит на эту тему. Я знаю, что число триангуляций набора из точек на плоскости находится где-то между Ω ( 8,48 n ) и O ( 30 n ) . Извиняюсь, если я устарел; Обновления приветствуются.nnnΩ(8.48n)Ω(8.48n)\Omega(8.48^n)O(30n)O(30n)O(30^n) Я упомянул об этом в...
Предположим, что вам дан набор из n точек на плоскости, и вы хотите проверить, образуют ли они выпуклый n-многоугольник, т. Е. Лежат ли все они на выпуклой оболочке. Мне было интересно, если кто-нибудь знает, как это сделать за время (nlogn), т. Е. Без вычисления...
Я сталкивался с этой проблемой в области физики, довольно далекой от компьютерных наук, но это похоже на вопрос, который был изучен в CS, поэтому я решил попытать счастья, задав его здесь. Представьте, что вам дан набор точек и список некоторых расстояний между точками d i j . Как наиболее...
Я ищу структуру данных, которая бы поддерживала целочисленную таблицу ttt размера и позволяла бы выполнять следующие операции за время .nnnO(logn)O(logn)O(\log n) increase(a,b)increase(a,b)\text{increase}(a,b) , которое увеличивает .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b]...
Легко проверить, что при заданной d-размерной сетке целочисленных точек {1,…,n}d{1,…,n}d\{1,\ldots,n\}^d с регулярной смежностью можно найти разделитель размера nd−1nd−1n^{d-1} (просто выберите любой средней гиперплоскости и удалите все ее вершины). Также не сложно (но определенно не сразу)...
Есть ли проблемы, которые являются NP-полными при использовании евклидовой геометрии, но хорошо определены и разрешимы за полиномиальное время для некоторой неевклидовой...
Я поставил перед своими учениками задачу нахождения треугольника, согласующегося с набором точек в R 2 , помеченных как ± 1 . (Треугольник Т является согласуется с меченым образцом , если Т содержит все положительные и ни один из негативных моментов, по предположению, образец допускает по меньшей...
СCC - параллельный оси прямоугольник. С1, … , CNC1,…,CnC_1,\dots,C_nC1∪⋯∪Cn⊊CC1∪⋯∪Cn⊊CC_1\cup\dots\cup C_n \subsetneq C Прямоугольник , сохраняющее разбиение на разбиение C = E_1 \ чашка \ ДоТы \ чашка E_N , таким образом, что N \ GEQ п , то e_i попарно-салона непересекающейся оси параллельных...
Вычислительная геометрия - это область, которую я нахожу довольно интересной, и я хотел бы посвятить месяц или два проекту, который познакомит меня с этим и поможет мне изучить ключевые концепции. Какой хороший способ подойти к этому и какие ключевые концепции я должен быть уверен, что я тоже...
Пусть отдельные точки находятся в . Мы говорим, что точки и являются соседями, если | ij | <3 \ pmod {n-2} , что означает, что каждая точка является соседом с точками с индексами в пределах 2 , обтеканием.R 2 i j1...n1...n1 ... nR2R2\mathbb{R}^2iiijjj|i−j|<3(modn−2)|i−j|<3(modn−2)|i-j| < 3...
Что известно о следующей проблеме? Для набора функций : 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) ≤...
Это задание является последующим вопросом к предыдущему посту Робина Котари о результатах определения полиномиального времени . В частности, я заинтересован в том, чтобы увидеть некоторые доказательства твердости для задач, которые, как считается, имеют примерно нижних границ, и я говорю грубо,...