Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 142

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 136 137 138 139 140 141 < 142 > 143 144 145 146 147 148 .. 180 >> Следующая


7.3. Трехмерные приложения

387

Е3), а 3)- проецируется на выпуклую область SD"_, лежащую на гиперплоскости л:4 = —1. Точки на ЗТ+ являются общим пересечением (или общей внутренностью) полупространств, определенных ограничениями. С другой стороны, точки на ЗТ_ имеют любопытную интерпретацию. Поскольку xt=—l, то ЗТ_ является множеством точек (хи х2, х3,—1), для которых + btx2 + ctx3 — dt < 0 для /=1, 2, N.

Если теперь отобразить каждую такую точку, лежащую на гиперплоскости Xi=l, преобразованием симметрии по отношению к началу координат в Е* (это преобразование заменяет Xi на —Xi для i=l, 2, 3), то получится множество таких точек, для которых щх\ + biX2 + CiX3 + di ^ 0, i = 1, ..., N, или

а,х + Ь{у + с,г + (11>0, i = 1, 2, .... N. (7.17)

Если сравнить эти неравенства с ограничениями (7.15), то станет очевидно, что они определяют общую внешность заданных полупространств. Следовательно, на гиперплоскости х4 = 1 объединенное множество точек может состоять из двух отдельных неограниченных выпуклых множеств, одно из которых будет общей внутренностью, а другое — общей внешностью заданных полупространств, как это показано для случая двух измерений на рис. 7.42. Назовем такую ситуацию гиперболическим случаем. Если все точки решения проецируются на положительную (или отрицательную ) открытую полусферу, то соответствующее множество из Е3 будет ограниченным, и такая ситуация называется эллиптическим случаем. Параболический случай имеет место тогда, когда существует единственное, но неограниченное множество в Е3, т. е. когда на S4 имеются как экваториальные, так и положительные (или отрицательные) точки. Во всех трех случаях множества точек образуют то, что мы будем называть обобщенным выпуклым полиэдром. Только эллиптический случай соответствует обычному ограниченному полиэдру.

Нашей целью является совместное вычисление и общей внутренности, и общей внешности. Заметим, что область 3) всегда содержится в одной из полусфер на 54, ограниченной гиперплоскостью л, заданной уравнением р\Х\ + р2х2 + р3х3 + + р4л:4 = 0. Луч (ррь рр2, рр3, рр4) при р ^ 0, нормальный к л, протыкает 54 в точке и. Если приложить к ?4 преобразование вращения R, которое переведет начало координат Е3 в точку и, то вся область 3) окажется в положительной полусфере. Ограничимся далее только эллиптическим случаем, который решается ранее описанным методом. Если бы был известен по-

13*

Гл. 7. Пересечения

лиэдр, образованный пересечением полупространств, то, применив к нему обратное преобразование вращения R-1, мы перевели бы его опять в искомые общую внутренность и общую внешность. Поэтому цель состоит в поиске вектора р = (pi, р2, Рз, р*) ¦

Поскольку 2) содержится в полупространстве piXi 4- р2х2 + + РзХз + Р4*4 ^ 0, то, полагая v,- = (a,-, ft,-, a, di), получаем

р ¦ v[ < 0, / = 1, 2, . . ., N

(где «•» обозначает, как обычно, скалярное произведение). Это можно переписать так:

aiPi + btp2 + см + dtp* i=l, 2, . . ., N,

т. e.

f atp{ + b[p2 + ctp3 + pi < 0 при dt = +l, X —aiPi — biP2 — ctp3 + р4 > 0 при di = —\.

Теперь дадим интерпретацию этим условиям. Пусть р{х + р2у + + p3z + pi = 0 обозначает плоскость в Е3. В зависимости от того, будет cf? = -f-1 или di = —1, точка (ai,bi,d) или точка (—ai, —bi, —ci) будет двойственной к плоскости а(х + bit/ + + Ciz + di = 0 при обычном поляритете. Поэтому плоскость aix + bit/ + ciz + di = 0 разделяет двойственные образы тех плоскостей, чьи индексы принадлежат соответственно /+ и /_ Это немедленно приводит к методу поиска р:

1. Образовать двойственные множества S+ из {я,:

и 5- из {я,: i'eL}. Построить выпуклые оболочки S+ и [За время O(NlogyV).]

2. Если пересечение этих выпуклых оболочек непусто (т. е. обладает внутренностью), то множество неравенств несовместно. Иначе, построить разделяющую плоскость р\х + р2у + + Рг% + Pi — 0. [За время O(N), используя метод, упомянутый в замечании 2 в разд. 7.2.5.]

Теперь можно построить соответствующее преобразование вращения L74 и применить его за время O(N), после чего завершить решение задачи, затратив дополнительно 0(N\ogN) времени, с помощью методов, описанных ранее.

Теорема 7.16. Общую внутренность и общую внешность множества из N полупространств в Е3 можно построить за время 9 (N log N) (т. е. за оптимальное время).

Оптимальность следует из того факта, что нижняя оценка ^(yVlogyV), полученная для пересечения N полуплоскостей, тривиально применима к рассматриваемой задаче.

7.4. Замечания и комментарии

7.4. Замечания и комментарии

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

Подход, предложенный Чазелле и Добкином [Chazelle, Dobkin (1980)] для решения задач о пересечениях, аналогичен обработке массовых запросов. В частности, вместо того, чтобы рассматривать пару геометрических объектов и вычислять их пересечение, они предложили рассматривать большие множества таких объектов и предобрабатывать их так, чтобы потом их попарные пересечения можно было проверять очень быстро (задача типа С.З). Они занимались объектами типа точек, прямых, плоскостей, многоугольников и полиэдров; для любых пар объектов такого типа (т. е. пар (многоугольник, многоугольник) или (плоскость, полиэдр) и т. п.) они предложили алгоритмы проверки факта их пересечения, принадлежащие классу «полилог»1). Например, случай пары (точка, полиэдр) был решен ими методом локализации точки на плоскости (разд. 2.2) путем стереографического проецирования этих полиэдра и точки на подходящую плоскость; в свою очередь решение этой задачи приводит путем прямого применения дихотомии (разд. 1.3.3) к решению задачи типа (плоскость, полиэдр).
Предыдущая << 1 .. 136 137 138 139 140 141 < 142 > 143 144 145 146 147 148 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed