Есть восьми- (семи-,
n-) -мерное евклидово пространство
R^
n. В нём задано до хрена (
m) полупространств (
H_
i = {
x | sum(
x_j *
n_ij |
j=1..
n) >=
c_i}). Вместе они задают, очевидно, выпуклый многогранник
H = intersect{
H_i |
i=1..
m}.
Требуется:
(1) Определить, является ли этот многогранник
- пустым (система неравенств несовместна, H = 0);
- ограниченным (существует сфера конечного радиуса R, что (forall x in H) |x| < R);
- неограниченным ((forall R in R) (exists x in H) (|x| > R)).
(2) Если он пустой, то найти наибольшее по мощности подмножество полупространств, пересечение которых непусто.
(3) Если многогранник
H непуст и ограничен, найти шар
B(
C,
r) максимального радиуса, полностью лежащий в
H.
(4) Если многогранник
H неограничен, найти шар
B(
C, 100), полностью лежащий в
H.
Откуда берутся такие задачи?
Да всё оттуда же, из практики. Есть набор операций, которые можно проделывать с точками, чтобы перевести один набор точек в другой. Есть формула, сопоставляющая каждой операции её стоимость. Соответственно, стоимость трансформации — это сумма по всем операциям их стоимостей. Чтобы распознать букву, надо попробовать перевести её по очереди во все шаблоны букв, и посчитать наименьшую стоимость.
И в теории всё хорошо и просто, а на практике эта формула параметризуется восемью параметрами, и их надо подобрать, исходя из тестовых картинок. Поэтому для каждой тестовой картинки возникают ограничения: d(x, '5') < d(x, 'S'); d(x, '5') < d(x, 'J')… которые по отношению к коэффициентам формулы будут линейными неравенствами. То есть — решение каждого неравенства есть вот такое полупространство, и чем дальше от плоскости, тем увереннее распознавание. Граничный случай — d(x, '5') = d(x, 'S') — тестовая картинка x может быть как цифрой 5, так и буквой S.
Хм. Однако в такой постановке оказывается, что все
c_i равны нулю, все плоскости проходят через точку 0, и для любой точки
x в
H все точки
ax для всех положительных вещественных
a тоже лежат в
H. Ну естественно, если все стоимости умножить на одну и ту же константу, то результаты сравнения не поменяются. Значит, искать на самом деле надо не точку, а луч, составляющий максимальный угол со всеми плоскостями… или, другими словами,
соотношение стоимостей.
На плоскости всё тривиально. Из всех прямых выберутся две, потом от них возьмём биссектрису и всё зашибись. В трёх измерениях уже начинает быть интересно…