Блоки 3, 4

Блок 1

Производится выбор первых (N + 1) граничных точек из массива всех граничных точек.

Блок 2

Процедура построения гиперплоскости через заданные N граничных точек занимает центральное место в данном алгоритме. Коэффициенты гиперплоскости (неравенства) определяются в результате решения системы линейных алгебраических уравнений (N + 1)-го порядка. Систему получают в результате составления уравнений гиперплоскостей, записав вместо переменных координаты N точек, через которые необходимо провести гиперплоскость:

. (1.2)

Так как количество неизвестных коэффициентов (N + I), то необходимо одному из них задать произвольное значение, например a = 1, Однако в этом случае невозможно построить гиперплоскости, параллельную оси координат X.

Аналогично, если присвоить значение другому коэффициенту b = 1 уравнений (3), то предлагаемый подход будет неприменим для построения гиперплоскостей, параллельных соответствующим осям координат, а при задании k ¹ 0 - для построения гиперплоскостей, проходящих через начало координат.

С целью устранения второго недостатка вводятся (N + 1)-я переменная z и дополнительная точка (точка 4 на рис.4). Тогда построение гиперплоскости осуществляется в (N + 1)-м пространстве, а произвольное значение присваивается коэффициенту при переменной z. Координаты дополнительной точки (точка 4) необходимо выбирать такими, чтобы ни одна из гиперплоскостей не была параллельна оси координат (N + 1)-й переменной z.Это требование выполняется, если значение хотя бы одной из координат дополнительной точки (не считая координаты по оси z) меньше минимального или больше максимального значения соответствующей координаты множества граничных точек. Значения остальных координат задаются произвольно.

 

 

 

 

В результате решения системы (N + 1)-го порядка (1.2) определяются значения коэффициентов (N + 1)-й гиперплоскости. Исключение из уравнений гиперплоскостей дополнительной переменной позволяет получить область в N-мерном пространстве (заштрихованная область на рис.1.3).

Блоки 3, 4

Производится проверка - первые ли (N + 1) гиперплоскостей построены. Если первые, то осуществляется поиск генеральной гиперплоскости. В противном случае выполняется проверка - все ли генеральные гиперплоскости найдены и использованы при построении гиперплоскостей для данной граничной точки.