Cтраница 1
Геометрические алгоритмы ( Часть 6) - это методы решения задач с использованием точек и линий ( и других простых геометрических объектов), которые стали использоваться лишь недавно. Мы рассмотрим алгоритмы для отыскания образующей поверхности, определенной набором точек, определения пересечений геометрических объектов, решения задач отыскания ближайших точек и для выполнения многомерного поиска. Многие из этих методов прекрасно дополняют более элементарные методы сортировки и поиска. [1]
Геометрические алгоритмы включают в себя манипулирование с объектами, которые не обрабатываются на уровне машинного языка. Поэтому пользователь должен описать эти сложные объекты посредством более простых типов данных, непосредственно представимых в машине. Такие описания принято называть структурами данных. [2]
Существует ли геометрический алгоритм построения вырожденных групп. [3]
Для этого сначала нужно найти простой способ изображения собственного энергетического состояния, а затем - простой геометрический алгоритм в фазовом пространстве, позволяющий вычислить скалярное произведение. Этот алгоритм сводится к перекрытию площадей фазового пространства, представляющих отдельные квантовые состояния. [4]
Задачи трассировки этапа 2 предназначены для определения геометрии соединений, и алгоритмы для решения этих задач назовем геометрическими алгоритмами. Основными алгоритмами в этом случае являются волновые, лучевые, канальные, итерационные и эвристические. [5]
Так ли необходимо проверять все треугольники, определяемые множеством из N точек, чтобы узнать, лежит ли некоторая точка в каком-либо из них. Грэхем в одной из первых работ, специально посвященных вопросу разработки эффективных геометрических алгоритмов [ Graham ( 1972) ], показал, что, выполнив предварительно сортировку точек, крайние точки можно найти за линейное время. Использованный им метод стал очень мощным средством в области вычислительной геометрии. [6]
Бхт полярой для, то увидим, что полюс на конике инцидентен своей собственной поляре. Такое преобразование точек в прямые и наоборот, называемое поляритетом, полезно при создании геометрических алгоритмов. [7]
Как указано в разд. Хотя точка считается вектором в декартовых координатах, желательно, чтобы выбор системы координат не слишком влиял на время работы геометрического алгоритма. Это приводит к тому, что модель вычислений должна допускать необходимое преобразование ( декартова базиса), причем его стоимость в расчете на одну точку может зависеть от числа измерений, но не от числа обрабатываемых точек. [8]
Для определения P ( i) по значению члена уравнения (10.206), заключенного в квадратные скобки, при условии, что известны значения ( 1 - t) m, t / ( l - t) и биномиальных коэффициентов, требуются восемь скалярных операций. Эта процедура, в сущности, представтяет собой применение схемы Горнера для вычисления многочленов Безье. При малых m ( m5) удобнее пользоваться геометрическим алгоритмом, поскольку его реализация требует небольшого числа вспомогательных операций, однако при больших т предпочтительнее схема Горнера. [9]
Однако и в анализе средней производительности существуют трудности. Во-первых, входная модель может неточно характеризовать входные данные, встречающиеся на практике, или же естественная модель входных данных может вообще не существовать. Мало кто будет возражать против использования таких моделей входных данных, как случайно упорядоченный файл, для алгоритма сортировки или случайный набор точек для геометрического алгоритма, и для таких моделей можно получить математические результаты, которые будут точными предположениями о производительности программ в реальных приложениях. Но как можно характеризовать входные данные для программы, которая обрабатывает текст на английском языке. Даже для алгоритмов сортировки в определенных приложениях рассматриваются другие модели кроме модели случайно упорядоченных данных. Во-вторых, анализ может требовать глубоких математических доказательств. Например, анализ случая средней производительности для алгоритмов union-find достаточно сложен. [10]
Нам, конечно, хотелось бы сказать: Даны N точек, равномерно распределенные на плоскости... Лебега [ Kendall, Moran ( 1963) ] 2), так что мы вынуждены определить конкретную область, из которой выбираются точки. К счастью, задаче вычисления E ( h) было уделено значительное внимание в литературе по статистике, и ниже приведен ряд теорем, которые имеют прямое отношение к анализу некоторых геометрических алгоритмов. [11]
Прежде всего они формулировались не так графические, а как геометрические, их условие отличалось от соответствующих задач начертательной геометрии и черчения только тем, что результат должен быть получен без применения чертежных инструментов. Содержанием поисковой части задания является определение линии пересечения двух многогранников. Геометрический алгоритм решения такой задачи студентам еще неизвестен. Его поиск составляет содержание первой части работы. [12]
Задачи автоматизации конструкторского проектирования делятся на задачи топологического и геометрического проектирования. Формализация задач топологического проектирования наиболее просто производится с помощью теории графов. Для автоматизации решения задач компоновки и размещения в основном используются комбинаторные алгоритмы и алгоритмы, основанные на методах математического программирования. Для решения задач трассировки применяются распределительные и геометрические алгоритмы. [13]
Она основана на описании геометрических объектов в терминах свойств конечных подмножеств. Например, некоторое множество выпукло тогда и только тогда, когда отрезок, определяемый любой парой его точек, лежит полностью в этом множестве. Неадекватность комбинаторной геометрии для нас заключается в том, что для большинства интересующих нас множеств число их конечных подмножеств бесконечно, а это препятствует их алгоритмической обработке. Работа последних лет в области геометрических алгоритмов направлена на избавление от этих недостатков и развитие математики, ведущей к созданию хороших алгоритмов. [14]