Формулировка (чётко, математически).
Пусть кривая $C=\gamma ([0,1])\subset {\mathbb{R}}^2$ — непрерывный (обычно предполагают простую, кусочно‑$C^2$ или гладкую) образ параметризации $\gamma :[0,1]\to {\mathbb{R}}^2$. Обозначим множество всех ломаных с не более чем $n$ отрезками через ${\mathcal{P}}_n$. Требуется найти
$$\underset{P\in {\mathcal{P}}_n}{\min }{d}_H(C,P),$$ где хаусдорфово расстояние задаётся как
$$d_H(A,B)=\max \{\underset{a\in A}{\sup }\underset{b\in B}{\inf }\Vert a-b\Vert ,\underset{b\in B}{\sup }\underset{a\in A}{\inf }\Vert b-a\Vert \}.$$
Варианты задачи, которые стоит выделить отдельно:
- вершины ломаной обязаны принадлежать кривой (\emph{inscribed}): ${\mathcal{P}}_n^{\mathrm{in}}$ — оптимизация по точкам разбиения параметра;
- вершины свободны в плоскости (\emph{free}): полная сводимая оптимизация по координатам;
- ограничение дополнительными условиями (сохранять касательные, быть монотонной и т.д.);
- аппроксимация в терминах минимального числа отрезков при заданной точности $\epsilon$ (обратная задача).
Ключевые вопросы для исследования
- существование и единственность оптимума в каждом варианте;
- вычислительная сложность (решение, NP‑трудность/полиномиальность) для \emph{in} и \emph{free} вариантов;
- бонды сверху/снизу на $d_H$ в терминах геометрических характеристик кривой (кривизна, локальная feature size, total curvature);
- структурные свойства оптимальной ломаной (условия оптимальности, «эквилатерация» погрешности и т.д.);
- аппроксимационные алгоритмы с гарантией (PTAS, FPTAS или жёсткие границы).
Геометрические идеи и подходы (конкретные направления исследования)
1) Вариант «вершины на кривой» (inscribed)
- Редукция к разбиению параметра: погрешность аппроксимации отрезком зависит только от параметров концов поддуги, поэтому задача «для заданного $\epsilon$ — уложиться в ≤$n$ отрезков?» сводится к задачам разбиения [0,1].
- Проверка для заданного $\epsilon$: строить жадно максимально длинные дуги, аппроксимируемые одним отрезком с ошибкой $\le \epsilon$. Если требуется ≤$n$ отрезков — решаемо за полиномиальное время (при условии, что для пары параметров можно вычислить ошибку).
- Предвычисление матрицы ошибок $E(i,j)=d_H(\gamma ([t_i,t_j]),[\gamma (t_i),\gamma (t_j)])$ и динамическое программирование / двоичный поиск по $\epsilon$.
- Вычисление $E(i,j)$ использует геометрию дуги: для гладкой дуги это задача нахождения максимального отклонения по нормали (одномерная оптимизация).
2) Вариант «свободные вершины» (free)
- Это непрерывная оптимизация с неналоженной структурой: гораздо сложнее, возможно NP‑трудная. Предложения:
- вариационный подход: рассматривать как минмакс задачу и применять методы небольшого числа параметров (координаты вершин) с оптимизацией по минимакс критерию;
- релаксации (выпуклые аппроксимации, семидефинированные релаксации для квадратичных ошибок), затем локальная доработка;
- жёсткие геометрические соображения: оптимальные вершины часто попадают внутрь «трубок» вдоль оси кривой (medial axis, центр осцилляционных окружностей).
3) Управление погрешностью через кривизну и локальную feature size
- Для дуги с ограниченной кривизной ${\kappa }_{\max }$ отклонение дуги длины $l$ от хорды примерно оценивается (для малых $l$) как
$$\delta \lesssim \frac{{\kappa }_{\max }{l}^2}{8}.$$ Отсюда естественное правило адаптивной дискретизации: выбирать длины отрезков $l$ так, чтобы $l\lesssim \sqrt{8\epsilon /{\kappa }_{\max }}$.
- Использовать локальную feature size $\mathrm{lfs}(x)$ (расстояние до медиальной оси) как масштабный параметр: плотность узлов $\sim 1/\sqrt{\mathrm{lfs}}$ или по требованию $\epsilon$.
4) Использование опорных геометрических структур
- Медальная ось/кора — управляет минимальными радиусами локальной кривины и мешает аппроксимации: точки близкие к медиальной оси требуют более плотной аппроксимации.
- Выпуклая оболочка и полосы (tubular neighborhoods): минимальная полоса ширины $2\epsilon$, содержащая кривую — поиск ломаной, лежащей в центре полосы.
- Опорные прямые и огибающие: оптимальная ломаная часто стремится следовать «центру» полосы, симметризуя ошибки.
5) Теория минимакс‑аппроксимации (аналог теоремы эквилатерации)
- Исследовать структуру оптимума: для одномерной функции есть эквилатерация; для кривой ожидать условия типа «на границах сегмента существуют точки, где расстояние равняется оптимальной $\epsilon$» и баланс углов/касательных — формулировать необходимые условия оптимальности (можно пытаться вывести через лагранжевы множители).
6) Алгоритмические и сложностные направления
- Для inscribed: реализовать и проанализировать алгоритм «жадное разбиение + двоичный поиск по $\epsilon$»; оценить сложность с учётом точности вычисления отклонения.
- Для free: исследовать сложность проблемы (решение, вероятная NP‑трудность или даже аппроксимационная трудность); искать приближённые алгоритмы с гарантией.
- Разработать адаптивные схемы на основе приближённых кривизны и локального feature size с гарантией количества сегментов для данной $\epsilon$.
Предлагаемые конкретные открытые задачи (формулировки для исследования)
1. Доказать или опровергнуть полиномиальную разрешимость задачи минимизации $d_H(C,P)$ для варианта free (вершины свободны). Если NP‑трудна — дать строгое сведение.
2. Для гладкой простой кривой с ограниченной кривизной ${\kappa }_{\max }$ получить точные верхние и нижние оценки на минимальное число сегментов $n(\epsilon )$, необходимые для $d_H\le \epsilon$, в терминах ${\kappa }_{\max }$, длины дуги $L$ и/или total curvature $T$.
3. Построить алгоритм с гарантией (время и конечное число сегментов) для free‑варианта с аппроксимацией к оптимуму до множителя $c$ (аппроксимация по стоимости $d_H$).
4. Вывести «условия эквилатерации» (необходимые/достаточные) для оптимальной ломаной и использовать их для численной схемы поиска оптимума.
5. Исследовать зависимость оптимальной ломаной от шума в данных (устойчивость решения по хаусдорфовой топологии).
Коротко о практических подходах
- Для реальных данных: сначала собрать candidate‑узлы на кривой (по арк‑длина/по curvature/по feature size), затем решать дискретную задачу DP/минимакса; для свободных вершин — инициализация от inscribed решения и локальная оптимизация (например, минимизировать максимум расстояний через субградиентные методы).
- Использовать комбинацию аналитических оценок (кривизна) и численных процедур (жадность + DP + локальный градиент).
Заключение (одно предложение)
Исследование должно сочетать строгую математическую постановку (minimax/decision версии), оценку в терминах геометрических характеристик кривой (кривизна, lfs, total curvature) и разработку эффективных алгоритмов для двух ключевых вариантов (inscribed и free) с анализом сложности и аппроксимационных гарантий.