Есть восьми- (семи-, 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. Ну естественно, если все стоимости умножить на одну и ту же константу, то результаты сравнения не поменяются. Значит, искать на самом деле надо не точку, а луч, составляющий максимальный угол со всеми плоскостями… или, другими словами, соотношение стоимостей.

На плоскости всё тривиально. Из всех прямых выберутся две, потом от них возьмём биссектрису и всё зашибись. В трёх измерениях уже начинает быть интересно…