Редактирование: Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
Пусть дано множество точек <tex>S</tex>, изначально пустое, и набор точек <tex>\{p_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется динамически поддерживать выпуклую оболочку <tex>S</tex>.
+
Пусть дано множество точек <tex>S</tex>, изначально пустое, и последовательность точек <tex>\{p_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется динамически поддерживать выпуклую оболочку <tex>S</tex>.
  
 
В статье описан алгоритм, требующий <tex>O(\log^2{n})</tex> времени на добавление/удаление точки.
 
В статье описан алгоритм, требующий <tex>O(\log^2{n})</tex> времени на добавление/удаление точки.
Строка 34: Строка 34:
 
== Объединение двух выпуклых оболочек ==
 
== Объединение двух выпуклых оболочек ==
  
Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями [[Целочисленный двоичный поиск|бинарного поиска]] для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> .  
+
Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями бинарного поиска для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> .  
  
 
Рассмотрим дополнительно 4 точки:
 
Рассмотрим дополнительно 4 точки:
  
<tex>p^{+}</tex> {{---}} следующая за <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{+} > p_{y}</tex> и ордината <tex>p_{y}</tex> {{---}} наименьшая.
+
<tex>p^{+}</tex> - следующая за <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{+} > p_{y}</tex> и ордината <tex>p_{y}</tex> - наименьшая.
  
<tex>p^{-}</tex> {{---}} предыдущая <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{-} < p_{y}</tex> и ордината <tex>p_{y}</tex> {{---}} наибольшая.
+
<tex>p^{-}</tex> - предыдущая <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{-} < p_{y}</tex> и ордината <tex>p_{y}</tex> - наибольшая.
  
<tex>q^{+}</tex> {{---}} следующая за <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{+} > q_{y}</tex> и ордината <tex>q_{y}</tex> {{---}} наименьшая.
+
<tex>q^{+}</tex> - следующая за <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{+} > q_{y}</tex> и ордината <tex>q_{y}</tex> - наименьшая.
  
<tex>q^{-}</tex> {{---}} предыдущая <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{-} < q_{y}</tex> и ордината <tex>q_{y}</tex> {{---}} наибольшая.
+
<tex>q^{-}</tex> - предыдущая <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{-} < q_{y}</tex> и ордината <tex>q_{y}</tex> - наибольшая.
  
 
Тогда в зависимости от взаимного расположения вектора <tex>\overrightarrow{qp}</tex> и точек <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> можно определить, какой из 9 случаев рассматривать, а именно:
 
Тогда в зависимости от взаимного расположения вектора <tex>\overrightarrow{qp}</tex> и точек <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> можно определить, какой из 9 случаев рассматривать, а именно:
  
:a) Все точки <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> расположены справа от вектора <tex>\overrightarrow{qp}</tex> (точка <tex>t</tex> находится слева (справа) от вектора <tex>\overrightarrow{qp}</tex>, если [[Предикат "левый поворот"|предикат "левый поворот"]] для точек <tex>q</tex>, <tex>p</tex>, <tex>t</tex> положительный (отрицательный)) {{---}} найден мост.
+
a) Все точки <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> расположены справа от вектора <tex>\overrightarrow{qp}</tex> (т.е. образуют с ним правый поворот) - найден мост.
  
:b) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex> {{---}} справа, <tex>q^{-}</tex> {{---}} слева от <tex>\overrightarrow{qp}</tex>
+
b) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex> - справа, <tex>q^{-}</tex> - слева от <tex>\overrightarrow{qp}</tex>
  
:c) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{-}</tex> {{---}} справа, <tex>q^{+}</tex> {{---}} слева от <tex>\overrightarrow{qp}</tex>
+
c) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{-}</tex> - справа, <tex>q^{+}</tex> - слева от <tex>\overrightarrow{qp}</tex>
  
:d) Как в случае b, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{+}</tex>
+
d) Как в случае b, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{+}</tex>
  
:e) Как в случае c, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{-}</tex>
+
e) Как в случае c, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{-}</tex>
  
:f) <tex>p^{-}</tex>, <tex>q^{+}</tex> {{---}} справа, <tex>p^{+}</tex>, <tex>q^{-}</tex> {{---}} слева от <tex>\overrightarrow{qp}</tex>
+
f) <tex>p^{-}</tex>, <tex>q^{+}</tex> - справа, <tex>p^{+}</tex>, <tex>q^{-}</tex> - слева от <tex>\overrightarrow{qp}</tex>
  
:g) <tex>p^{+}</tex>, <tex>q^{+}</tex> {{---}} справа, <tex>p^{-}</tex>, <tex>q^{-}</tex> {{---}} слева от <tex>\overrightarrow{qp}</tex>
+
g) <tex>p^{+}</tex>, <tex>q^{+}</tex> - справа, <tex>p^{-}</tex>, <tex>q^{-}</tex> - слева от <tex>\overrightarrow{qp}</tex>
  
:h) <tex>p^{-}</tex>, <tex>q^{-}</tex> {{---}} справа, <tex>p^{+}</tex>, <tex>q^{+}</tex> {{---}} слева от <tex>\overrightarrow{qp}</tex>
+
h) <tex>p^{-}</tex>, <tex>q^{-}</tex> - справа, <tex>p^{+}</tex>, <tex>q^{+}</tex> - слева от <tex>\overrightarrow{qp}</tex>
  
:i) <tex>p^{+}</tex>, <tex>q^{-}</tex> {{---}} справа, <tex>p^{-}</tex>, <tex>q^{+}</tex> {{---}} слева от <tex>\overrightarrow{qp}</tex>
+
i) <tex>p^{+}</tex>, <tex>q^{-}</tex> - справа, <tex>p^{-}</tex>, <tex>q^{+}</tex> - слева от <tex>\overrightarrow{qp}</tex>
  
 
Для случаев a-h на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее.
 
Для случаев a-h на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее.
Строка 89: Строка 89:
 
|}
 
|}
  
Рассмотрим подробно случай i. Пусть <tex>m</tex> {{---}} прямая, разбивающая <tex>P</tex> на <tex>A</tex> и <tex>C</tex>. Пусть также <tex>l_p</tex> и <tex>l_q</tex> {{---}} касательные к выпуклым оболочкам в точках <tex>p</tex> и <tex>q</tex> соответственно. Если <tex>s</tex> {{---}} точка пересечения <tex>l_p</tex> и <tex>l_q</tex> лежит ниже прямой <tex>m</tex>, то точка пересечения моста и выпуклой оболочки <tex>A</tex> может лежать в треугольнике, образованном прямыми <tex>l_p</tex>, <tex>l</tex> и <tex>m</tex>, или выше <tex>p</tex>. Тогда можем удалить часть <tex>C</tex> ниже <tex>q</tex> (см. рис. i1). Случай, когда <tex>s</tex> лежит выше <tex>m</tex>, аналогичен (см. рис. i2).
+
Рассмотрим подробно случай i. Пусть <tex>m</tex> {{---}} прямая, разбивающая <tex>P</tex> на <tex>A</tex> и <tex>C</tex>. Пусть также <tex>l_p</tex> и <tex>l_q</tex> {{---}} касательные к выпуклым оболочкам в точках <tex>p</tex> и <tex>q</tex> соответственно. Если <tex>s</tex> {{---}} точка пересечения <tex>l_p</tex> и <tex>l_q</tex> лежит ниже прямой <tex>m</tex>, то точка пересечения моста и выпуклой оболочки <tex>A</tex> может лежать в треугольнике, образованном прямыми <tex>l_p</tex>, <tex>l</tex> и <tex>m</tex>, или выше <tex>p</tex>. Тогда можем удалить часть <tex>C</tex> ниже <tex>q</tex>. Случай, когда <tex>s</tex> лежит выше <tex>m</tex>, аналогичен (см. рис.).
  
 
{|border="0" cellpadding="5" width=30% align=center
 
{|border="0" cellpadding="5" width=30% align=center

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: