Проблема Хопкрофта ⇐ Васина Википедия

[wiki_en]

В вычислительной геометрии «проблема Хопкрофта» - это проблема проверки для данной системы точек и прямых на евклидовой плоскости, лежит ли хотя бы одна из точек хотя бы на одной из прямых. В более общем плане можно задаться вопросом о количестве случаев пересечения точки с линией. Оба варианта задачи можно решить за время O(n^{4/3}), где n — общее количество точек и линий.
Один из способов решения проблемы включает в себя геометрический алгоритм «разделяй и властвуй». Для данной системы точек и линий можно использовать теорию ε-сети (вычислительная геометрия) | эпсилон-сети, чтобы разделить плоскость для заданного параметра r на O (r) треугольные подзадачи, каждая из которых пересекается на долю 1/r^2 линий и каждая содержит долю 1/r точек. В качестве альтернативы, применяя ту же технику к проективно-двойственной системе двойственных прямых и двойственных точек, можно получить подзадачи, каждая из которых включает долю 1/r входных линий и 1/r^2. доля баллов. Если сделать это один раз в каждом направлении, для r=n^{1/3}, это сведет проблему к подзадачам постоянного размера, которые можно решить напрямую. Эта идея (при более тщательном выборе параметра r) приводит к ограничению времени O(n^{4/3}\log^{1/3} n). Здесь дополнительный логарифмический коэффициент возникает из-за накладных расходов на присвоение точек и линий подзадачам, которые создаются таким образом.
Тот же двухэтапный процесс подразделения с выбором r, меньшего на логарифмический коэффициент, может свести данную проблему к подзадачам, размер которых является полилогарифмической функцией от n , в O(n^{4/3}). Повторение этой рекурсии процесса (информатика)|рекурсивно до тех пор, пока входные данные не будут сокращены до подзадач постоянного размера, приведет к ограничению времени в виде n^{4/3}2^{O(\log^* n ). Здесь \log^* n обозначает повторный логарифм.
Описанные выше алгоритмы работают исключительно за счет разделения плоскости, в которой заданы входные точки и линии, и ее двойственной проективной плоскости. Джефф Эриксон доказал нижнюю границу, согласно которой алгоритмы, работающие таким образом, должны занимать время \Omega(n^{4/3}), что немного больше, чем границы времени, указанные выше.
В препринте 2024 года Андреев, Белов и Вихров анонсировали квантовый алгоритм решения задачи Хопкрофта, работающий за время \tilde O(n^{5/6}), где \tilde Обозначение O скрывает логарифмические коэффициенты. Это существенно ниже наиболее известного временного ограничения для классического алгоритма.







Вычислительная геометрия

Подробнее: https://en.wikipedia.org/wiki/Hopcroft%27s_problem