Алгоритм Хачияна(Khachiyan) для построения минимальног(по площади) эллипса вокруг заданного набора точек

Question

[Whiteha]

Пытаюсь написать программу на C++ вычисляющую минимальный(по площади) эллипс описываемый вокруг заданного множества точек. На stackoverflow был найден псевдокод матлаба реализующий оптимальный алгоритм Хачияна для решения данной проблемы.

Во время переписывания кода на C++ возникла пара проблем, на которые я со своими малыми познаниями линейной алгебры, не смог найти ответы.

Проблема 1 - второе действие в цикле while из данного на стековерфлоу псевдокода:
M = diag(Q' * inv(X) * Q); // Q' - transpose of Q
Для некоторых исходных наборов точек, как например {{1, 2}, {3, 4}, {5, 6}, {7, 8}} получается такая матрица X, для которой не существует обратной, и все последующие вычисления невозможны.
Вопрос: Как это нужно трактовать(все множество точек не должно лежать на одной линии?)?

Проблема 2 - интерпретация итоговой матричной формы записи уравнения эллипса.
Как я понял, итоговый результат представляется в виде двух матриц - матрицы c размерности 2x1 задающей центр искомого эллипса и матрицы A размерности 2x2 представляющей некие коэффициенты из записи уравнения эллипса как кривой второго порядка(?).
Вопрос: Как я могу привести данную матричную форму к каноническому виду(ну или к тому виду, из которой её будет удобнее визуализировать)?

Answer 1

[Bruyerholz]

Проблема 1:

Матрица Q имеет вид:



Матрица X имеет вид:



С учетом вида матрицы Q матрица X примет вид:



Если все x или y равны нулю, то все точки лежат на одной прямой. Это частный неинтересный случай. Если есть x и y ненулевые, то у нас не будет нулевых строк. Если определитель матрицы X равен нулю, то можно написать (выразить строки через друг друга; более простые случаи очевидны):



Тоже самое:



Домножаем первую строку на a, вторую на b, складываем:



Такая точка (в пространстве размерности N) единственна, при



Это очевидно для случая N = 2. Нарисуйте круг с квадратом радиуса равным 2 и прямую x + y = 2. Они будут касаться в одной точке. После того как нарисуете, это станет очевидно и для любого N.

Итак, мы доказали, что если определитель X равен нулю, то точки лежат на одной прямой.

Проблема 2:

C сайта матлаба нашел правую часть:



Нужно найти собственные значения и собственные вектора единичной длины (они должны быть ортогональны) для матрицы A, после чего используя точку



как центр, нужно провести собственный вектор длиной



(лямбда соответствует собственному вектору). Аналагично для другого. Эти вектора будут большой и малой полуосями для нашего эллипса. Дальше по возможностям визуализатора.

Как-то все сумбурно получилось.