Кіріспе

Жазық бөліктің түрі

Математикада Вороной диаграммасы – берілген объектілер жиынтығының әрқайсысына жақын орналасқан аймақтарға жазықтықты бөлу. Оны теселяция деп те жіктеуге болады. Ең қарапайым жағдайда, бұл объектілер жазықтықтағы шектеулі нүктелер ғана болады (тұқымдар, орналасқан жерлер немесе генераторлар деп аталады). Әр тұқым үшін сәйкес аймақ бар, ол Вороной жасушасы деп аталады және ол басқа тұқымдарға қарағанда осы тұқымға жақын жатқан жазықтықтың барлық нүктелерінен тұрады. Нүктелер жиынтығының Вороной диаграммасы осы жиынтықтың Делоней үшбұрыштауымен (триангуляциясымен) байланысты. Вороной диаграммасы математик Георгий Воронойдың құрметіне аталған, сондай-ақ Вороной теселяциясы, Вороной ыдырауы, Вороной бөлігі немесе Дирихле теселяциясы (Питер Густав Лежен Дирихле атымен) деп те аталады. Вороной жасушалары Альфред Х. Тиссеннің есімімен Тиссен полигондары деп те белгілі. Вороной диаграммасының ғылым мен техника, сондай-ақ көркем өнер салаларында практикалық және теориялық қолданыстары кең.

Ең қарапайым жағдай

Ең қарапайым жағдайда, бірінші суретте көрсетілгендей, Евклид жазықтығында шекті нүктелер жиыны берілген. Бұл жағдайда әрбір сайт осы берілген нүктелердің бірі болып табылады, ал оған сәйкес Вороной ұяшығы Евклид жазықтығындағы барлық нүктелерден тұрады, мұнда ол нүктеге ең жақын сайт болып табылады: осы нүктеден сайтқа дейінгі қашықтық кез келген басқа сайтқа дейінгі ең аз қашықтықтан кем немесе тең болады. Басқа бір сайт үшін , осы сайтқа қарағанда жақын немесе оған тең қашықтықтағы нүктелер жабық жарты кеңістік құрайды, оның шекарасы – сызық сегментінің перпендикуляр биссектрисі. Ұяшық – мұндай жарты кеңістіктердің қиылысы, сондықтан ол дөңес көпбұрыш болып табылады. Вороной диаграммасындағы екі ұяшық шекараны ортақтасқанда, ол екі жақын сайтқа тең қашықтықтағы жазықтықтағы барлық нүктелерден тұратын сызық сегменті, сәуле немесе түзу болып табылады. Диаграммада үш немесе одан көп шекаралар кездесетін нүктелер – үш немесе одан көп жақын сайтқа бірдей қашықтықтағы нүктелер.

Ресми анықтама

Болсын – метрикалық кеңістік, ал – қашықтық функциясы. Болсын – индекстер жиыны, ал – кеңістіктегі бос емес ішкі жиындардың (сайттардың) жинағы. Сайтқа байланысты Вороной ұяшығы немесе Вороной аймағы – бұл кеңістіктегі барлық нүктелердің жиыны, олардың сайтқа дейінгі қашықтығы басқа сайттарға дейінгі қашықтығынан кем емес, мұнда – басқа индекс. Яғни, егер – нүкте мен ішкі жиын арасындағы қашықтықты білдірсе, онда Вороной диаграммасы – жай ғана ұяшықтар жинағы. Принцип бойынша, кейбір сайттар қиылысуы мүмкін, тіпті бір-бірімен сәйкес келуі де мүмкін (мысалы, дүкендерді білдіретін сайттар үшін), бірақ әдетте олардың бөлек екендігі қабылданады. Бұған қоса, анықтамада шексіз көп сайттарға рұқсат етіледі (бұл параметр сандар геометриясы және кристаллография салаларында қолданылады), бірақ көбінесе тек шекті көптеген сайттар қарастырылады. Егер кеңістік – шекті өлшемді Евклид кеңістігі болса, әр сайт – нүкте болса, сондай-ақ нүктелер саны шекті және олардың барлығы әртүрлі болса, онда Вороной ұяшықтары – дөңес политоптар болып табылады және оларды төбелері, қабырғалары, екі өлшемді жақтары және т.б. арқылы комбинаторлық түрде көрсетуге болады. Кейде туындаған комбинаторлық құрылым Вороной диаграммасы деп аталады. Дегенмен, жалпы жағдайда Вороной ұяшықтары дөңес немесе тіпті байланысты болмауы мүмкін. Әдеттегі Евклид кеңістігінде ресми анықтаманы әдеттегі терминдермен қайта жазуға болады. Әрбір Вороной көпбұрышы – генераторлық нүктемен байланысты. Евклид кеңістігіндегі барлық нүктелер жиыны болсын. – Вороной аймағын құрайтын нүкте, – құрайтын , және – құрайтын , және т.б. Осылайша, Тран және авторлар айтқандай, "Вороной көпбұрышындағы барлық орналасқан жерлер Евклид жазықтығындағы Вороной диаграммасындағы кез келген басқа генераторлық нүктеден гөрі сол көпбұрыштың генераторлық нүктесіне жақын".

Қасиеттері

Вороной диаграммасының қос графигі (нүктелік орындары бар Евклид кеңістігі жағдайында) сол нүктелер жиынтығы үшін Делоне үшбұрыштауімен сәйкес келеді. Ең жақын нүктелер жұбы Вороной диаграммасындағы екі іргелес ұяшыққа сәйкес келеді. Кеңістік Евклид жазықтығы деп есептелсін және нүктелердің дискретті жиынтығы берілген. Онда жиынның екі нүктесі, олардың Вороной жасушалары шексіз ұзын қабырғаны ортақтасса ғана, дөңгелек қабыршақта іргелес болады. Егер кеңістік нормаланған кеңістік болса және әрбір орынға дейінгі қашықтыққа жете алса (мысалы, орын компактты жиын немесе жабық шар болса), онда әрбір Вороной ұяшығы орындардан басталатын түзу кесінділерінің бірігімі ретінде бейнелене алады. Бұл қасиет қашықтыққа жете алмағанда міндетті түрде орындалмайды, бұл көрсетілгендей. Қарапайым жағдайларда (кеңістік мүмкін шексіз өлшемді біртекті дөңгелек кеңістік, орындардың саны шексіз болуы мүмкін және т.б.) Вороной жасушалары белгілі бір тұрақтылық қасиетіне ие: орындардың пішініндегі шағын өзгеріс, мысалы, аударма немесе бұрмалау салдарынан, Вороной жасушаларының пішінінде шағын өзгеріске әкеледі. Бұл Вороной диаграммасының геометриялық тұрақтылығы. Бұл қасиет жалпы жағдайда орындалмайды, бұл көрсетілгендей, тіпті кеңістік екі өлшемді болған жағдайда да (бірақ біртекті емес, әсіресе Евклидтік емес) және орындар нүктелер болса да.

Тарих және зерттеулер

Вороной диаграммаларын бейресми пайдалану 1644 жылы Декартқа дейін жетеді. Питер Густав Лежун Дирихле 1850 жылы квадраттық формаларды зерттеуде екі және үш өлшемді Вороной диаграммаларын қолданды. Британдық дәрігер Джон Сноу 1854 жылы Вороной диаграммасына ұқсас схеманы пайдаланып, Брод-стриттегі холера эпидемиясында қайтыс болған көптеген адамдар басқа су сорғыларына қарағанда, инфекциялық Брод-стрит сорғысына жақын тұрғанын көрсетті. Вороной диаграммалары 1908 жылы жалпы n өлшемді жағдайды анықтаған және зерттеген Георгий Феодосиевич Воронойдың құрметіне аталған. Геофизика және метеорологияда кеңістікте тараған деректерді талдау үшін қолданылатын Вороной диаграммалары американдық метеоролог Альфред Х. Тиессеннің есімімен Тиессен полигондары деп аталады, ол 1911 жылы сирек өлшемдерден жауын-шашын мөлшерін бағалау үшін оларды қолданған. Осы түсінік үшін басқа да эквивалентті атаулар (немесе оның ерекше маңызды жағдайлары): Вороной полиэдрлері, Вороной көпбұрыштары, ықпал ету аймақтары, Вороной бөлінісі, Вороной мозаикалары, Дирихле мозаикалары.

Мысалдар

Екі немесе үш өлшемдегі нүктелердің реттелген торларының Вороной кескіндері көптеген таныс кескіндерге әкеледі. 2D тор турасызықсыз бал арасы кескінін береді, бұрыштарында симметриясы бар тең қабырғалы алтыбұрыштардан тұрады; егер тор үшбұрышты болса, кескін реттелген болады; егер тіктөртбұрышты болса, алтыбұрыштар қатар-жолдардағы тіктөртбұрыштарға айналады; шаршы тор шаршылардың реттелген кескінін береді; ескеріңіз, тіктөртбұрыштар мен шаршылар басқа торлар арқылы да жасалуы мүмкін (мысалы, (1,0) және (1/2,1/2) векторларымен анықталған тор шаршылар береді). Жасырақтың кубтік торы кубтік бал арасын береді. Алтыбұрышты тығыз жиналған тор трапециялы ромб додекаэдрлермен кеңістіктің кескінін береді. Бетіне ортақталған кубтік тор ромб додекаэдрлермен кеңістіктің кескінін береді. Денесіне ортақталған кубтік тор кесілген октаэдрлермен кеңістіктің кескінін береді. Бір-бірінің ортасына сәйкес келген реттелген үшбұрышты торлары бар параллель жазықтықтар алтыбұрышты призмалық бал арасын береді. Кейбір денесіне ортақталған тетрагональдық торлар ромбо-алтыбұрышты додекаэдрлермен кеңістіктің кескінін береді. Кейбір денесіне ортақталған тетрагональдық торлар ромбо-алтыбұрышты додекаэдрлермен кеңістіктің кескінін береді. Егер нүктелер жиыны (x, y) координаталарында, x дискретті X жиынында және y дискретті Y жиынында болса, онда біз нүктелері міндетті түрде ортасында емес тіктөртбұрышты плиткалар аламыз.

Жоғары дәрежелі Вороной диаграммалары

Нормалды Вороной ұяшығы S жиынындағы бір нүктеге ең жақын нүктелер жиынтығы ретінде анықталғанмен, n-ші ретті Вороной ұяшығы – S жиынындағы n нүктенің белгілі бір жиынтығын өзінің n ең жақын көршісі ретінде анықталатын нүктелер жиынтығы болып табылады. Жоғары ретті Вороной диаграммалары да кеңістікті бөліп жатады. Жоғары ретті Вороной диаграммаларын рекурсивті түрде жасауға болады. S жиыны үшін n-ші ретті Вороной диаграммасын жасау үшін (n-1)-ші ретті диаграммадан бастап, X = {x1, x2, ..., xn−1} арқылы құрылған әрбір ұяшықты S - X жиынында жасалған Вороной диаграммасымен ауыстырыңыз.

Ең алыс нүктесі Вороной диаграммасы

n нүктелер жиынтығы үшін (n - 1)-реттегі Вороной диаграммасы ең алыс нүктелік Вороной диаграммасы деп аталады. Берілген S = {p1, p2, ..., pn} нүктелер жиынтығы үшін ең алыс нүктелік Вороной диаграммасы жазықтықты мұндай ұяшықтарға бөледі, әрбір ұяшықта P жиынының бір ғана нүктесі ең алыс нүкте болып табылады. P жиынының нүктесінде ең алыс нүктелік Вороной диаграммасында ұяшық бар, егер және тек қана егер ол P жиынының дөңгелек қабығының төбесі болса. Егер H = {h1, h2, ..., hk} P жиынының дөңгелек қабығы болса, онда ең алыс нүктелік Вороной диаграммасы жазықтықты k ұяшыққа бөледі, H жиынындағы әр нүкте үшін бір ұяшықтан, мұнда q нүктесі hi нүктесіне сәйкес ұяшықта орналасқан, егер және тек қана егер d(q, hi) > d(q, pj) болса, барлық pj ∈ S үшін, мұнда hi ≠ pj, ал d(p, q) екі нүкте p және q арасындағы Евклидтік қашықтық. Ең алыс нүктелік Вороной диаграммасындағы ұяшықтардың шекаралары топологиялық ағаш құрылымын құрайды, оның жапырақтары шексіз сәулелер болып табылады. Кез келген шекті ағаш осылай ең алыс нүктелік Вороной диаграммасынан құрылған ағашқа изоморфты.

Жалпылаулар мен өзгерістер

Анықтамадан көрініп тұрғандай, Вороной жасушалары Евклидтік емес, Махаланобис қашықтығы немесе Манхэттен қашықтығы сияқты басқа метрикалар үшін анықталуы мүмкін. Дегенмен, мұндай жағдайларда Вороной жасушаларының шекаралары Евклидтік жағдайдағыдан күрделірек болуы мүмкін, себебі екі нүкте үшін теңқашықтықтағы геометриялық орын екі өлшемді жағдайда да 1-өлшемнен кем кеңістік болуы мүмкін. Салмақты Вороной диаграммасы – бұл Вороной жасушасын анықтау үшін екі нүктенің функциясы, ол генераторлық нүктелерге тағайындалған көбейту немесе қосу салмақтарымен түзетілген қашықтық функциясы. Вороной жасушалары қашықтық метрикасы арқылы анықталған жағдайдан өзгеше, мұнда кейбір Вороной жасушалары бос болуы мүмкін. Power диаграммасы – бұл power қашықтығын қолдана отырып, шеңберлер жиынтығынан құрылатын Вороной диаграммасының бір түрі; оны әрбір шеңбердің радиусынан анықталатын салмақтың, шеңбер ортасынан Евклидтік қашықтықтың квадратына қосылатын салмақты Вороной диаграммасы ретінде де қарастыруға болады. Өлшемдік кеңістіктегі нүктелердің Вороной диаграммасы түйінге ие болуы мүмкін, оның нақты сипаттамасын сақтау үшін қажетті жад көлемі де сол шекте болуы керек. Сондықтан Вороной диаграммаларын орташа немесе жоғары өлшемдерде қолдану жиі қиын. Орынды үнемдеу үшін жуық Вороной диаграммаларын пайдалануға болады. Вороной диаграммалары сондай-ақ медиалдық ось (сурет сегментациясында, оптикалық таңбаларды тануда және басқа да есептеулік қолдануларда қолданылады), тік қаңқа және аймақ диаграммалары сияқты басқа геометриялық құрылымдармен байланысты.

Метеорология/Гидрология

Ол метеорологияда және инженерлік гидрологияда белгілі бір аумақтағы (су алабындағы) станциялардың жауын-шашын деректеріне салмақ беру үшін қолданылады. Көпбұрыштарды құрайтын нүктелер – жауын-шашын деректерін тіркейтетін әртүрлі станциялар. Кез келген екі станцияны жалғайтын түзуге перпендикуляр биссектристер салынады. Бұл станциялардың айналасында көпбұрыштардың пайда болуына себеп болады. Станция нүктесіне тиетін аудан станцияның ықпал ету аймағы деп аталады. Орташа жауын-шашын мөлшері формула арқылы есептеледі.

Гуманитарлық және әлеуметтік ғылымдар

Классикалық археологияда, әсіресе өнер тарихында, мүсін басының симметриясы үзілген бас қандай мүсінге тиіс екенін анықтау үшін талданады. Вороной жасушаларын қолданған мысал – жоғары ажыратымды көпбұрыш торды пайдаланған Сабуров басының анықталуы.

Табиғи ғылымдар

Биологияда Вороной диаграммасы көптеген биологиялық құрылымдарды, соның ішінде жасушаларды және сүйек микроархитектурасын модельдеу үшін қолданылады. Вороной кескіндері биологиялық тіндердің ұйымдасуына ықпал ететін физикалық шектеулерді түсінуге арналған геометриялық құрал ретінде жұмыс істейді. Гидрологияда Вороной диаграммасы бір аймақтың жауын-шашын мөлшерін, нүктелік өлшемдер сериясіне сүйене отырып есептеу үшін қолданылады. Бұл жағдайда олар көбінесе Тиессен көпбұрыштары деп аталады. Экологияда Вороной диаграммалары орман және орман шатырларының өсу үлгілерін зерттеу үшін қолданылады, сондай-ақ орман өрттерінің болжамдық модельдерін жасауға көмектеседі. Этологияда Вороной диаграммалары өзімшіл топ теориясындағы қауіп аймақтарын модельдеу үшін қолданылады. Есептеу химиясында лиганд байланыс орындары машиналық оқыту қолданбалары үшін Вороной диаграммасына түрлендіріледі (мысалы, белоктардағы байланыс қуыстарын жіктеу үшін). Басқа қолданбаларда молекуладағы ядролардың орналасуымен анықталатын Вороной жасушалары атомдық зарядтарды есептеу үшін қолданылады. Бұл Вороной деформация тығыздығы әдісін пайдалану арқылы жүзеге асырылады. Астрофизикада Вороной диаграммалары кескіндерде бейімделетін тегістеу аймақтарын жасау үшін қолданылады, олардың әрқайсысына сигнал ағыны қосылады. Бұл процедуралардың басты мақсаты – барлық кескіндерде сигнал мен шу арақатынасын салыстырмалы түрде тұрақты деңгейде ұстау. Есептеу сұйықтық динамикасында нүктелер жиынтығының Вороной кескіні шекті көлем әдістерінде қолданылатын есептеу домендерін анықтау үшін пайдаланылуы мүмкін, мысалы, жылжымалы торлы космология коды AREPO-да. Есептеу физикасында Вороной диаграммасы объектінің профилін Shadowgraph және протондық радиография арқылы жоғары энергия тығыздығы физикасында есептеу үшін қолданылады.

Денсаулық

Медициналық диагностикада Вороной диаграммаларына негізделген бұлшықет тінінің модельдерін нейромышелік ауруларды анықтауға болады.

Инженерлік

Полимерлік физикада Вороной диаграммасын полимерлердің бос көлемдерін көрсетуге болады. Материалдар ғылымында металл қорытпаларындағы поликристаллдық микроқұрылымдар көбінесе Вороной кескіндемелерін пайдаланып бейнеленеді. Аралдардың өсуі кезінде Вороной диаграммасы жеке аралдардың өсу жылдамдығын бағалау үшін қолданылады. Қатты дене физикасында Вигнер-Зайц жасушасы – қатты дененің Вороной кескіндемесі, ал Бриллюэн аймағы – кеңістіктік топтың симметриясына ие кристалдардың өзара (толқындық) кеңістігінің Вороной кескіндемесі. Авиацияда Вороной диаграммалары мұхиттық карталарға жабыстырылып, ұшу барысында ауыстыру үшін ең жақын әуежайды анықтауға қолданылады (ЕТОПС-ке қараңыз). Сәулетте Вороной үлгілері Алтын жағалау өнер орталығын қайта құру конкурсының жеңімпаз жобасы болды. Қалалық жоспарлауда Вороной диаграммасын жүк тиеу аймағы жүйесін бағалау үшін пайдалануға болады. Кен өндіруде Вороной полигондары құнды материалдардың, минералдардың немесе басқа да ресурстардың қорын бағалау үшін қолданылады. Барлау бұрғылаулары Вороной полигондарының нүктелері жиынтығы ретінде пайдаланылады. Жер бетінің метрологиясында Вороной кескіндемесі жер бетінің тегіс еместігін модельдеу үшін қолданылуы мүмкін. Робототехникада көп роботты жүйелердің кейбір басқару стратегиялары мен жол жоспарлау алгоритмдері қоршаған ортаның Вороной бөлінуіне негізделген.

Математика

Тораптық орналасу деректерінің құрылымын Вороной диаграммасының негізінде құруға болады, бұл жақын көршілерге қатысты сұраныстарға жауап беруге мүмкіндік береді, яғни берілген сұраныс нүктесіне ең жақын объектіні табуға болады. Жақын көршілерге қатысты сұраныстардың көптеген қолданыс орындары бар. Мысалы, ең жақын аурухананы табуға немесе деректер базасындағы ең ұқсас объектіні анықтауға болады. Маңызды қолданыс – деректерді сығымдауда кеңінен қолданылатын векторлық кванттау. Геометрияда Вороной диаграммасын нүктелер жиынтығының арасындағы ең үлкен бос шеңберді табу үшін, сондай-ақ оларды қоршап тұрған көпбұрыш ішінде пайдалануға болады; мысалы, белгілі бір қаладағы барлық қолданыстағы дүкендерден мүмкіндігінше алыс жаңа супермаркет салу үшін. Вороной диаграммасы және ең алыс нүктеге қатысты Вороной диаграммасы нүктелер жиынтығының дөңгелектігін есептеуге арналған тиімді алгоритмдерде қолданылады.

Ақпараттық техника

Желілік жүйелерде Вороной диаграммалары сымсыз желілердің өткізу қабілетін есептеу үшін қолданылады. Компьютерлік графикада Вороной диаграммалары 3D нысандарды қирату/жару геометриялық үлгілерін есептеуге пайдаланылады. Ол сондай-ақ органикалық немесе лава тәрізді текстураларды процедуралық түрде жасау үшін де қолданылады. Автономды роботтарды бағыттауда Вороной диаграммалары еркін жолдарды табуға көмектеседі. Егер нүктелер кедергілер болса, онда график қабырғалары кедергілерден ең алыс (және теориялық тұрғыдан кез келген соқтығыстардан) қашып өтуге мүмкіндік береді. Машиналық оқытуда Вороной диаграммалары 1 NN жіктемелерін жасау үшін қолданылады. Жаһандық кеңістікті қайта құруда, оның ішінде кездейсоқ сенсорлық орындар, тұрақсыз ояну ағыны, геофизикалық деректер және 3D турбуленттік деректермен Вороной тесселяциялары терең оқытумен бірге қолданылады. Пайдаланушы интерфейсін әзірлеуде Вороной үлгілерін белгілі бір нүкте үшін ең қолайлы күйін анықтау үшін пайдалануға болады.

Азаматтық және жоспарлау

Мельбурн қаласында мемлекеттік мектеп оқушылары тұратын жеріне ең жақын бастауыш немесе жоғары мектепке баруға әрқашан құқылы, бұл арақашықтық тік сызық бойынша өлшенетіндей. Сондықтан мектеп аймақтарының картасы Вороной диаграммасы болып табылады.

Нан пісіру зауыты

Украиналық шебер кондитер Динара Каско өзінің ерекше торттарын жасау үшін 3D принтерде шығарылған силикон қалыптарды құруда Вороной диаграммасының математикалық қағидаларын пайдаланады.

Алгоритмдер

Вороной диаграммаларын тікелей (диаграмманың өзі ретінде) немесе жанама түрде, Делоней триангуляциясынан басталып, кейін оның қос диаграммасын алу арқылы құруға арналған бірнеше тиімді алгоритмдер белгілі. Тікелей алгоритмдерге Фортуна алгоритмі жатады, ол жазықтықтағы нүктелер жиынтығынан Вороной диаграммасын құруға арналған O(n log(n)) алгоритмі. Бойер–Уотсон алгоритмі, кез келген өлшемдегі Делоней триангуляциясын құруға арналған O(n log(n)) – O(n²) алгоритмі, Вороной диаграммасының жанама алгоритмінде қолданылуы мүмкін. Jump Flooding алгоритмі тұрақты уақытта жуық Вороной диаграммаларын құрады және стандартты графикалық аппараттық құралдарда қолдануға ыңғайлы. Ллойд алгоритмі және оның Linde–Buzo–Gray алгоритмі арқылы жалпылануы (әзірге k-орталықтар кластерлеуі ретінде белгілі), Вороной диаграммаларын кіші программа ретінде пайдаланады. Бұл әдістер тұқымдық нүктелер жиынтығы үшін Вороной диаграммасын құру және тұқымдық нүктелерді олардың жасушаларының орталықтарына жақын жаңа орындарға жылжыту қадамдарымен алмасады. Бұл әдістер кез келген өлшемдегі кеңістікте Вороной диаграммасының ерекше түріне – центроидты Вороной мозаикасына (Centroidal Voronoi tessellation) итеративті түрде жуысу үшін қолданылуы мүмкін, онда сайттар өздерінің жасушаларының геометриялық орталықтары болып табылатын нүктелерге жылжытылған.

Воронои 3D-де

Вороной торларын 3D кеңістікте де жасауға болады.