Список тем (year 2012) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пройденное за весенний семестр)
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 3 участников)
Строка 1: Строка 1:
 +
==Осенний семестр==
 +
* Кратчайший путь O(n^2). Overmars and Welzl’s Algorithm & rotation tree. [[Visibility_graph_и_motion_planning#Overmars_and_Welzl.E2.80.99s_Algorithm]]
 +
 
==Пройденное за весенний семестр==
 
==Пройденное за весенний семестр==
 
Материалы можно найти в [https://www.dropbox.com/sh/i8ka1e4dr7girdh/AABgCA2Y8RYym90xJNO_m7Wka dropbox] (там есть README - в котором есть некоторая индексация конспекта)
 
Материалы можно найти в [https://www.dropbox.com/sh/i8ka1e4dr7girdh/AABgCA2Y8RYym90xJNO_m7Wka dropbox] (там есть README - в котором есть некоторая индексация конспекта)
Строка 28: Строка 31:
 
*: [[Интервальная_арифметика]]
 
*: [[Интервальная_арифметика]]
 
*: ESSA: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps]
 
*: ESSA: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps]
 +
  
 
=== Выпуклые оболочки на плоскости. ===
 
=== Выпуклые оболочки на плоскости. ===
 
+
Я упустил, эти алгоритмы описаны здесь: [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]]
* Алгоритм Джарвиса. (доделать - картинки, возможно пояснения)
+
* <del>Алгоритм Джарвиса. (доделать - картинки, возможно пояснения)</del>
 
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
 
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
 
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0]
 
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0]
* Алгоритм Эндрюса-Грэхема.
+
* <del>Алгоритм Эндрюса-Грэхема.</del>
 
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
 
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
 
*: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/]
 
*: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/]
 
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
 
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
+
*: Дописать сюда: [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]]
 
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 этот вроде как раз подойдет]
 
*: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 этот вроде как раз подойдет]
* Выпуклая оболочка как аналог quick sort (без дополнительной памяти).
+
* <del>Выпуклая оболочка как аналог quick sort (без дополнительной памяти).</del>
 
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
 
*: [[Алгоритмы_построения_выпуклых_оболочек_множества_точек_на_плоскости]]
 
*: [http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html]
 
*: [http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html]
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:19, 4 сентября 2022

Осенний семестр

Пройденное за весенний семестр

Материалы можно найти в dropbox (там есть README - в котором есть некоторая индексация конспекта)

То, что можно доделать с прошлого года

Возможно есть еще что-то, тут все, что я нашел на скорую руку с этих ссылок:

Неотсортированные темы.

Устойчивая реализация алгоритмов вычислительной геометрии.


Выпуклые оболочки на плоскости.

Я упустил, эти алгоритмы описаны здесь: Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull