Виды геометрических моделей и их свойства

Абстрактно определим геометрический объект как совокупность точек в евклидовом пространстве. Каждая точка определяется набором своих координатных переменных: P = (x1, x2,.., xn). Для описания окружающих объектов мы строим твердые тела или тела. Тела в свою очередь описываются точками, линиями и поверхностями. Все они обладают определенными свойствами. Точки, линии, поверхности и тела будем называть геометрическими объектами.

Геометрическое описание -> алгебраическое описание -> алгоритм -> программа

Каждый из шагов имеет свои проблемы. Сначала мы начинаем с постановки задачи в геометрических терминах (например, найти точку пересечения такой-то прямой линии с такой-то плоскостью). Вопрос - какой алгебраический базис выбрать для реализации.

Переход от алгебраического описания к алгоритмическому может быть идентифицирован на 4-х уровнях: символический (системы компьютерной алгебры), аналитический (самый привлекательный, но труднодостижимый), численный, аппроксимирующий.

Типы сложности геометрических проблем:

- Проблема размерности.

Геометрия работает чрезвычайно неодинаково в пространствах разной размерности. Например, все просто с углами на плоскости, но значительно сложнее в 3-х измерениях.

- Проблема аналитической сложности.

Когда решаются геометрические задачи, связанные с нахождением пересечения объектов, гладкого объединения и т.д., возникающие системы уравнений могут быть линейными, квадратичными, кубическими, рациональными квадратичными, с квадратными корнями, с высокостепенные, с тригонометрическими функциями…

- Проблема комбинаторной сложности.

Возникает, когда имеем много данных: даже если мы имеем дело только с точками, то много точек могут вызвать проблемы. Сложные объекты, да еще различных геометрических типов резко усиливают как вычислительную сложность, так и проблемы со сходимостью алгоритмов и т.п.