Вычислительная геометрия ( англ. computational geometry ) - отрасль компьютерных наук посвящена изучению алгоритмов что описуюються в терминах геометрии. Основным стимулом развития вычислительной геометрии как дисциплины был прогресс в компьютерной графике и системах автоматизированного проектирования и автоматизированных систем технологической подготовки производства, однако многие задачи вычислительной геометрии является классическим по своей природе, и могут появляться при математической визуализации. Другим важным применением вычислительной геометрии является робототехника (планирование движения и задачи распознавания образов ), геоинформационные системы(геометрический поиск, планирование маршрута), дизайн микросхем, программирование станков с числовым программным управлением. Основными разделами вычислительной геометрии являются:
Комбинаторная вычислительная геометрияОсновной целью исследований в комбинаторной вычислительной геометрии является разработка эффективных алгоритмов и структур данных для решения задач которые заданы в терминах базовых геометрических объектов: точек, отрезков, многоугольников, многогранников, и других. Некоторые из этих задач выглядят такими простыми, что они вообще не рассматривались как задачи до момента изобретения компьютеров. Рассмотрим например задачу поиска ближайшей пары точек :
Можно вычислить расстояния между каждой парой точек, (их n (n-1) / 2 ), затем выбрать пару с наименьшим расстоянием. Такой полный перебор имеет сложность O ( n 2 ) есть время его выполнения пропорционально квадрату числа точек. Классическим результатом в вычислительной геометрии был алгоритм со сложностью O ( N Log N ). Также открыты рандомизированные алгоритмы, работающие за O ( n ) шагов, и детерминированные алгоритмы работающие за O ( N Log Log N ). Вычислительная геометрия главным образом сосредотачивается на вычислительной сложности, так как алгоритмы предназначены для работы над очень большими наборами данных, из десятков или сотен миллионов точек. Для больших наборов данных разница между O ( n 2 ) и O ( N Log N ) может быть такой же, как разница между днями и секундами. Классы задачОсновные задачи вычислительной геометрии можно классифицировать различными способами, и с различными критериями. Различают следующие классы: Статические задачиВ задачах этой категории на вход подаются определенные данные, и за ними алгоритм должен вычислить соответствующие результаты. Примерами фундаментальных задач такого рода являются:
Вычислительная сложность для этого типа задач оценивается по времени и пространства (размера памяти), которые необходимы для решения конкретной задачи. Задачи геометрического поиска (запросу)В задачах геометрического поиска входные данные состоят из двух частей: пространство поиска и запроса, которые различаются в разных видах задач. Обычно пространство поиска требует предварительной обработки, для обеспечения эффективного выполнения нескольких запросов. Примеры задач геометрического поиска:
Если пространство поиска фиксированный, вычислительная сложность задач обычно определяется
В случаях когда пространство поиска может варьироваться смотрите раздел "Динамические задачи". Динамические задачиДинамические задачи - это тип задач входные данные в которые постепенно изменяются (например добавляются или удаляются объекты). Алгоритмы решения таких задач включают в себя поддержку динамических структур данных. Любую задачу вычислительной геометрии можно решать динамично, но за счет дополнительных вычислительных ресурсов. Региональный поиск или построение опуколои оболочки можно проводить над множеством точек, которые изменяются. Вычислительная сложность для этого класса задач задается такими параметрами:
Некоторые задачи могут рассматриваться как принадлежащие нескольким категориям в зависимости от контекста. Например, рассмотрим следующие задачи:
ВариацииВо многих программах эта задача рассматривается как задача первого класса. Тем не менее, во многих случаях нужно определить курсор мыши лежит внутри данного многоугольника. Курсор постоянно перемещается, а многоугольник не меняется. Аналогично можно проверять определенный летательный аппарат который показан на экране радара не пересек границу страны. Такие задачи можно считать задачами геометрического запроса. А в CAD-системах сам многокунтик может варьироваться, поэтому задача может считаться динамичной. |
Линейная алгебра матрицы. Решение Вернуться в оглавление: Высшая математика |