Временная сложность теоремы о разделяющей оси
Как бы вы определили сложность на основе количества полигонов (треугольников)? Пожалуйста, исправьте или подтвердите мой подход здесь. Предполагая, что у нас есть пирамида и мы начинаем добавлять вершины. Из шести вершин я вижу такой шаблон:
number of polygons = number of vertices * 2 - 2
В SAT я проецирую каждую вершину объекта на каждую его нормаль. Таким образом, формула N*V, где N такое же, как число полигонов, так:
(V*2-2)*V = 2V^2 - 2V
Это правильно? Если да, то что это за сложность? Должен ли я назвать это комбинацией квадратичного и линейного? Благодарю.
РЕДАКТИРОВАТЬ: Теперь, глядя на это, я думаю, это зависит от того, как я триангуляции, это может быть также:
number of polygons = number of vertices * 2 - 4
Не уверен, что это минимально, но это не должно изменить сложность. Это просто константа. Так что V*2-A возможно. Пожалуйста, дайте мне знать, если есть какая-то формула. Я нашел только формулу многогранника Эйлера, которая также касается ребер.