Редактирование: Триангуляция Делоне на Сфере

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 29: Строка 29:
  
 
{{Лемма
 
{{Лемма
|about=1
 
|id=1
 
 
|statement=Алгоритм найдет ближайшую точку
 
|statement=Алгоритм найдет ближайшую точку
 
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.  
 
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.  
Строка 39: Строка 37:
  
 
{{Лемма
 
{{Лемма
|about=2
 
|id=2
 
 
|statement=Среднее число точек, лежащих внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>V_{i + 1}</tex> равно <tex>O(1)</tex>.
 
|statement=Среднее число точек, лежащих внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>V_{i + 1}</tex> равно <tex>O(1)</tex>.
 
|proof=Рассмотрим точки триангуляции <tex>\{A_i\}</tex>. Для каждой точки <tex> A_i</tex> проведем окружность с центром в ней, проходящую через ближайшую к ней точку. Посчитаем во сколько окружностей в среднем попадет точка какая-то точка <tex>U</tex>.  
 
|proof=Рассмотрим точки триангуляции <tex>\{A_i\}</tex>. Для каждой точки <tex> A_i</tex> проведем окружность с центром в ней, проходящую через ближайшую к ней точку. Посчитаем во сколько окружностей в среднем попадет точка какая-то точка <tex>U</tex>.  
Строка 56: Строка 52:
  
 
{{Лемма
 
{{Лемма
|about=3
 
|id=3
 
 
|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне)
 
|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне)
 
|proof=Пусть есть функция <tex>circle(q, p, i)</tex>, возвращающая <tex>1</tex>, если точка <tex>p</tex> принадлежит окружности с центром в точке <tex>q</tex>, проходящую через ближайшую  к <tex>q</tex> на <tex>i</tex> уровне точку, а иначе <tex>0</tex>.
 
|proof=Пусть есть функция <tex>circle(q, p, i)</tex>, возвращающая <tex>1</tex>, если точка <tex>p</tex> принадлежит окружности с центром в точке <tex>q</tex>, проходящую через ближайшую  к <tex>q</tex> на <tex>i</tex> уровне точку, а иначе <tex>0</tex>.
 
 
Пусть <tex>Points_i</tex> {{---}} множество точек на <tex>i</tex>-ом уровне.
 
Пусть <tex>Points_i</tex> {{---}} множество точек на <tex>i</tex>-ом уровне.
 
<tex>X</tex> {{---}} степень вершины внутри окружности, тогда:
 
<tex>X</tex> {{---}} степень вершины внутри окружности, тогда:
  
<tex dpi = 130>E(X) = \dfrac{\sum\limits_{q \in Points_{i - 1}}{\sum\limits_{p \in Points_{i - 1}}{circle(q, p, i) \cdot deg(p)}}}{\left| Points_{i - 1} \right|} =</tex>
+
<tex dpi = 150>E(X) = \frac{\sum\limits_{q \in Points_{i - 1}}{\sum\limits_{p \in Points_{i - 1}}{circle(q, p, i) \cdot deg(p)}}}{\left| Points_{i - 1} \right|} =</tex>
  
 
Меняем порядок суммирования, и получаем:
 
Меняем порядок суммирования, и получаем:
  
<tex dpi = 130>= \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{q \in Points_{i - 1}}{circle(q, p, i)}}}{\left| Points_{i - 1} \right|} \leqslant</tex>
+
<tex dpi = 150>= \frac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{q \in Points_{i - 1}}{circle(q, p, i)}}}{\left| Points_{i - 1} \right|} \leqslant</tex>
  
 
По предыдущей лемме получаем:
 
По предыдущей лемме получаем:
  
<tex dpi = 130>\leqslant \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{1 \dots \infty}{i \cdot p \cdot (1 - p) ^ i}}}{\left| Points_{i - 1} \right|} \approx</tex>
+
<tex dpi = 150>\leqslant \frac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{1 \dots \infty}{i \cdot p \cdot (1 - p) ^ i}}}{\left| Points_{i - 1} \right|} \approx</tex>
 
 
<tex dpi = 130>\approx \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p)}}{\left| Points_{i - 1} \right|} = \dfrac{O(n)}{n} = O(1)</tex>
 
}}
 
 
 
{{Лемма
 
|about=4
 
|id=4
 
|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>
 
|proof=По [[#2|лемме 2]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 3]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.
 
}}
 
  
{{Теорема
+
<tex dpi = 150>\approx \frac{\sum\limits_{p \in Points_{i - 1}}{deg(p)}}{\left| Points_{i - 1} \right|} = \frac{O(n)}{n} = O(1)</tex>
|about=Следствие
 
|statement=Локализация в среднем работает за <tex>O(\log{n})</tex>
 
 
}}
 
}}

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

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

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