алгоритмическая ссылка
Mar. 8th, 2008 11:03 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva
Мне очень понравилась статья об алгоритме Форчуна (англ.) для вычислений диаграммы Вороного (если вы не знаете, что это такое, то по ссылке подробно объясняется). Написано ясным языком, и содержит несколько полезных демонстраций.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-03-08 09:19 am (UTC)no subject
Date: 2008-03-08 11:13 am (UTC)"содержит несколько полезных демонстраций" - по-русски так не говорят.
no subject
Date: 2008-03-08 03:35 pm (UTC)no subject
Date: 2008-03-08 04:08 pm (UTC)априори неясно, что имеется в виду, сначала я подумал, что в тексте по ссылке будет мультик, иллюстрирующий работу алгоритма или чего-то еще
еще была версия, что это калька с французского, и имеется в виду "доказательство"
апостериори тоже не вполне ясно, видимо имелся в виду "пример"
no subject
Date: 2008-03-09 11:23 am (UTC)no subject
Date: 2008-03-08 04:22 pm (UTC)Дан набор точек на плоскости {(x,y)}.
1) Помещаем плоскость в 3-мерное пространство, добавляя ещё одну координату z.
2) На нашу плоскость {(x,y,z): z=0} ставим параболоид вращения {(x,y,z): z=x^2+y^2} и для каждой точки из набора проецируем её на параболоид (x и y даны, по ним вычисляем z).
3) В пространстве находим выпуклую оболочку получившегося набора на параболоиде. Её граница в случае общего положения состоит из треугольников с вершинами из получившегося набора (для многомерной ситуации будут симплексы). Проецируя те из этих треугольников, внешняя нормаль к которым направлена вниз, обратно на плоскость, получим триангуляцию Делоне, двойственную структуре Вороного.
Конечно, остаются вопросы: как искать выпуклые оболочки, что делать в случаях необщего положения.
См. http://www.qhull.org/
no subject
Date: 2008-03-08 05:56 pm (UTC)no subject
Date: 2008-03-09 11:28 am (UTC)Я даже подумываю о том, чтобы прочесть лекцию по мотивам этой статьи в своем лицее. Можно будет приурочить к 140-летию Вороного.
no subject
Date: 2008-03-16 10:56 pm (UTC)Ahhh! Voronoi!
Date: 2008-03-20 07:31 am (UTC)Ahhh! Voronoi!
Date: 2008-03-20 07:31 am (UTC)