User:Ven Seyranyan./Ավազարկղ

Մաթեմատիկայում, Վորոնեի դիագրամը հատուկ տեսակ է տվյալ տարածության դասավորման ,օրինակ,մետրային տարածություն , կախված է տրված օբյեկտների (ենթաբազմությունների) ընտանիքից ունեցած հեռավորությունից տարածությյան մեջ:Այդ օբյեկտները սովորաբար անվանում են կայքեր կամ գեներատորներ (բայց օգտագործվում են ուրիշ անուններ, ինչպիսին է"սերմ") և ամեն մի այդպիսի օբյեկտի համար մեկը կապում է Վորոնեի համապատասխան բջջին, մասնավորապես տվյալ տարածության բոլոր կետերի փաթեթի հետ,որի հեռավորությունը տվյալ օբյեկտից այնքան էլ մեծ չէ,ինչքան այլ օբյեկտներից հեռավորությունը: Այն անվանվել է Գեորգի Վորոնեյ, և կոչվում է նաև Վորոնեի խճանկար, Վորոնեի դասավորություն, կամ Դիրիխլեի խճանկար (հետոԼեժեն Դիրիխլե): Վորոնեի դիագրամները մեծ քանակությամբ կարելի է գտնել Գիտություն և Տեխնոլոգիա բնագավառներում, նույնիսկ Արվեստի բնագավառում, և նրանք գտան բազմաթիվ տեսական և գործնական ծրագրեր:^[1]^[2]Սա տեխնոլոգիա է,որը թույլ է տալիս բաժանել այդպիսի բազմաչափ տարածությունները ենթատարածությունների:

Ամենապարզ դեպքը

Ամենապարզ և ամենածանոթ դեպքում (ցույց է տրված առաջին նկարում), մեզ տրվում է վերջավոր քանակությամբ կետեր {p₁,...,p_n} Էվկլիդյան հարթությունում : Այդ դեպքում ամեն կայք p_k դա ուղղակի կետ է և նրան համապատասխան Վորոնեի ցանցը (նաև անվանում են Վորոնեի շրջան կամ Դիրիխլեի բջիջ) R_k բաղկացած է բոլոր կետերից,հեռավորությունը մինչև p_k ավել չէ,քան իրենց հեռավորությունը այլ կայքերից.Յուրաքանչյուր այդպիսի բջիջ ստացվում է տարածության կեսի խաչմերուկից,և հետևաբար դա ուռուցիկ պոլիգոն է: Վորոնեի դիագրամի տեղամասերը,հարթության բոլոր կետերը,որոնք երկու միմյանց մոտ օբյեկտների համար գտնվում են միևնույն հեոավորության վրա. Վորոնեի գագաթները (հանգույցները)հանդիսանում են երեք(կամ ավել) հավասարահեռ կետեր:

Պաշտոնական սահմանումը

Թույլ տանք $\displaystyle {X}$ բացակով (ոչ դադարկ սահմանել) ապահովված հեռավորության ֆունկցիայով $d$ . Թույլ տանք $\displaystyle {K}$ ինդեքսների ամբողջություն և թույլ տանք $(P_{k})_{k\in K}$ (դասավորված հավաքածու) ոչ դատարկենթաբազմություն (կայքերի) տարածության մեջ $\displaystyle {X}$ : Վորոնեի բջիջը կամ Վորոնեի շրջանը, $\displaystyle {R_{k}}$ , կապված կայքից $\displaystyle {P_{k}}$ այն բոլոր կետերի հավաքածուն է $\displaystyle {X}$ ում որոնցից հեռավորությունը մինչև $\displaystyle {P_{k}}$ մեծ չէ,քան այլ կայքերից հեռավորությունը $\displaystyle {P_{j}}$ ,որտեղ $j$ յուրաքնչյուր ինդեքս տարբերվում է $k$ -ից: Այլ խոսքով,եթե $d(x,A)=\inf\{d(x,a)\,|\,a\in A\}$ նշանակում է հեռավորություն $x$ կետի և $A$ ենթաբազմության, այնուհետև

R_{k}=\{x\in X\,\,|\,\,d(x,P_{k})\leq d(x,P_{j})\,\,{\text{for all}}\,\,j\neq k\}.

Վորոնեի դիագրամը դա ուղղակի գնացք է $(R_{k})_{k\in K}$ բջիջներից. Որոշ կայքեր կարող են խաչվել և նույնիսկ համընկնել(ստորև առաջարկված`կայքերի համար,որոնք խանութներ են ներկայացնում),բայց սովորաբար նրանք միացված չեն:Դրանից բացի, սահմանման մեջ կան մեծ թվով կայքեր (այդ պարամետրը կիրառվում է երկրաչափություն թվերից և բյուրեղագրությունում), բայց նորից, շատ դեպքերում միայն վերջավոր շատ կայքեր են համարվում: Կոնկրետ դեպքում, երբ տարածությունը հանդես է գալիս վերջավոր ծավալային Էվկլիդյան տարածությունում, յուրաքանչյուր կայք`դա կետ է,կա վերջավոր շատ բալեր և նրանք բոլորը տարբեր են , ապա Վորոնեի բջիջներ են հանդիսանում ուռուցիկ պոլիգոն և նրանք կարող են ներկայացվել համակցական ձևով`նրանց գագաթների ,կողմեր,երկկողմանի պատկերի և այլնի օգտագործմամբ:Հաճախ կանչված համակցված կառուցվածքը անվանվում է Վորոնեի դիագրամ:Սակայն ընդհանուր առմամբ Վորոնեի բջիջները կարող են չլինել ուռուցիկ կամ նույնիսկ կապված:

Նկարազարդում

Որպես պարզ նկարազարդում, հաշվի աոեք խանութների խումբը հարթ քաղաքում:Ենթադրենք մենք ուզում ենք գնահատել տվյալ խանութի հաճախորդների քանակը: Բոլոր այլ հավասար պայմաններում(գին, ապրանքներ, մատակարարման որակ և այլն),հիմնավորված է ենթադրել,որ հաճախորդները կընտրեն իրենց նախընտրած խանութը պարզապես հեռավորության նկատառումներից ելնելով.նրանք գնում են այն խանութը,որը գտնվում է մոտակայքում:Այդ դեպքում Վորոնեի բջիջները $\displaystyle {R_{k}}$ տվյալ խանութից $\displaystyle {P_{k}}$ կարող է օգտագործվել այս խանութ գնացող պոտենցիալ հաճախորդների թվի մոտավոր գնահատական տալու համար,(որը մեր հարթ քաղաքում ձեւավորված է կետի միջոցով ): Մինչ այժմ ենթադրվում էր, որ քաղաքում կետերի միջեւ հեռավորությունը չափվում է ստանդարտ հեռավորության օգնությամբ,այն է,ծանոթ Էվկլիդյան հեռավորություն: $d((a_{1},a_{2}),(b_{1},b_{2}))={\sqrt {(a_{1}-b_{1})^{2}+(a_{2}-b_{2})^{2}}}$ . Սակայն, եթե հաշվի առնենք այն դեպքն, ուր հաճախորդները գնում են խանութներ միայն տրանսպորտային միջոցներով, և ճանապարհային ուղիները զուգահեռ են $x$ և $y$ կացինների համար, ինչպես Մանհետոնում,ապա հեռավորության գործառույթը կլինի ավելի իրատեսական $\ell _{1}$ հեռավորություն, իսկ ավելի կոնկրետ: $\displaystyle {d((a_{1},a_{2}),(b_{1},b_{2}))=|a_{1}-b_{1}|+|a_{2}-b_{2}|}$ .

10 հարթ քաղաքի խանութները և նրանց Վորոնյան բջիջները (Էվկլիդըան հեռավորություն).

Նույն 10 խանութները և այժմ Մանհետն հեռավորություն. Վորոնեի բջիջները երկու դեպքում էլ տարբեր են.

Հատկություններ

Երկակի գրաֆիկ Վորոնեի դիագրամի համար ( Էվկլիդյան տարածության համաձայն կայքի կետերից ) համապատասխան Դոլոնեի եռանկյունավորում նույն կետերի հավաքածուի համար:
Մոտակա կետերի զույգ համապատասխանում է երկու հարակից բջիջների Վորոնեի դիագրամում:
Ենթադրում են էվկլիդյան հարթության և խմբով տրված տարբեր կետերի հաստատում :Այդ դեպքում երկու կետեր հանդիսանում են կից ուռուցիկ կեղևիվրա, եթե միայն, նրանց Վորոնեի բջիջները բաժանվում են անսահման երկար մասերի:
Եթե տարածությունը նորմալացված տարածության և հեռավորությունը մինչ ամեն կայքը հասնում է(օրինակ, երբ կայքը գտնվում է կոմպակտ հավաքածուում կամ փակ գնդակ),ապա յուրաքանչյուր Վորոնյան բջիջ կարող է ներկայացվել որպես գծային հատվածների միասնություն`կայքերից ծագող ^[3].Ինչպես ցույց է տրված այստեղ,այս հատկությունը անպայման չի անցկացնում,երբ տարածությունները չեն հաղթահարված:

Ընդհանուր պայմաններին համաձայն (տարածքները, հնարավոր է անվերջ ծավալային հավասարաչափ ուռուցիկ տարածքներ, այստեղ կարող է լինել անսահման շատ կայքեր ընդհանուր ձեւով եւ այլն) Վորոնեի բջիջները օժտված են որոշակի կայուն հատկությամբ: օբյեկտի ձևերի ոչ մեծ փոփոխություն,օրինակ, թարգմանումից կամ աղավաղումից առաջացած փոփոխություն,առաջացնում է Վորոնեի բջիջների ձևերի որոշակի փոքր փոփոխություն:Սա Վորոնեի դիագրամի երկրաչափական կայունությունն է ^[4]. Ինչպես ցույց է տված այդտեղ,այդ սեփականությունը ընդհանրապես չի պահվում,նույնիսկ եթե տարածությունը երկչափանի է (բայց ոչ միանվագ ուռուցիկ, և ,մասնավորապես, ոչ Էկլիդյան )և կայքերը հանդիսանում են կետեր:

Պատմությունը և հետազոտությունը

Վորոնեի դիագրամի ֆորմալ օգտագործումը համընկնում է Դեկարտ 1644. Դիրիխլեօգտագործել է Վորոնեի երկչափ և եռաչափ դիագրամներ` իր քառակուսային ձևերի հետազոտությունում 1850թ.: Բրիտանական բժիշկը Ջոն Սնոու օգտագուծեց Վորոնեի դիագրամը 1854թ.,որպեսզի ներկայացնի,թե ինչպես մարդկանց մեծամասնությունը,որոնք մահացել են Soho խոլերիայի համաճարակը ապրում էին մոտ վարակված Broad փողոցի պոմպերին քան ցանկացած այլ ջրային պոմպի: Վորոնեի դիագրամները անվանել են ազգությամբ ռուս մաթեմատիկ Գեորգի Ֆեոդորովիչ Վորոնոյ (կամ Վորոնոյ) ով հետազոտեց և որոշեց հիմնական n-չափանի դեպքը 1908թվականին:Վորոնեի դիագրամները,որոնք օգտագործվում են Երկրաֆիզիկայու և Մթնոլորտային պայմաններ-ում,որպեսզի վերլուծեն տարածության մեջ տարածված տվյալները (ինչպիսիք են տեղատարափի չափերը) անվանում են Տիսենի պոլիգոններ ամերիկացի օդերևութաբան Ալֆրեդ Խ. Տիսսեն. Խտացրած ֆիզիկայի խնդիրներում,նման խճանկարները հայտնի են նաև որպես Վիգներ-Զայց բջիջների խումբանվանմամբ: Վորոնեի խճանկարը բաղկացած է փոխադարձ վանդակներից իներցիակոչվում են Brillouin գոտիներ:Ընդհանուր վանդակների համար,որոնք գտնվում են Ստի խմբում,այդպիսի բջիջները ուղղակի անվանում են արմատական դաշտեր. Ընդհանուր առմամբ մետրային տարածության դեպքում, բջիջների հաճախ անվանում են մետրային հիմանական պոլիգոններ: Այս հասկացության այլ համարժեք անվանումները (կամ դրա կոնկրետ կարևոր դեպքերը) : Վորոնեի բազմանիստեր, Վորոնեի պոլիգոններ, ազդեցության տիրույթը(ները) , Վորոնեի տարրալուծում, Վորոնեի խճանկար(ներ), Դիրիխլեի խճանկար(ներ):

Օրինակներ

Վորոնեի խճանկարի կանոնավոր Վանդակների միավորները երկու կամ երեք հարթություններում առաջացնում են շատ ծանոթ խճանկարներ:

2D վանդակը տալիս է անկանոն բջիջներով խճանկար,հավասար վեցանկյունների հետ կետի սիմետրիկությամբ;կանոնավոր եռանկյուն վանդակի դեպքում դա հանդիսանում է սիմետրիկ ; ուղղանկյուն վանդակի դեպքում վեցանկյունները փոքրացնում են մինչև ուղղանկյունները շարքերում և սյուներում; [Հրապարակ (երկրաչափություն) ]] վանդակավոր տալիս կանոնավոր խճանկար եւ հրապարակներուa քառակուսի վանդակը տալիս է կանոնավոր վանդակներով խճանկար ; նշենք որ ուղղանկյունները և քառակուսիները կարող են նաև գեներացվել այլ վանդակներից (օրինակի,վանդակ`որոշված վեկտորներով (1,0) և (1/2,1/2) տալիս է քառակուսիներ): Տես here որպես դինամիկ տեսողական օրինակ:
Սովորական քառակուսի վանդակը տալիս է քառակուսի բջիջ.
Վեցանկյուն փակ փաթեթավորված վանդակները տալիս են խճանկար տարածության վրա շեղանկյուն .
Կենտրոնացված խորանարդի դեմքով վանդակները տալիս են խճանկար տարածության վրա շեղանկյան հետ.
Կենտրոնացված խորանարդի մարմնով վանդակները տալիս են խճանկար տարածության վրակտրված ութանիստ.
Զուգահեռ հարթությունները` կանոնավոր եռանկյուն վանդակներով,մյուս կենտրոնների հետ համեմատած,տալիս են վեցանկյուն պրիզմային բջիջներ(մեղրախորիսխներ).
Մի շարք կենտրոնացված մարմիններով քառանկյուն վանդակները տալիս են խճանկարի կառուցվածքը տարածության վրա վեցանկյուն.

(x, y) Կետերի հավաքածուի համար x հետ դիսկրետ շարք X-ով և yդիսկրետ շարքով Y,մենք ստանում ենք ուղղանկյուն սալիկներ` կետերով,որոնք պարտադիր չէ,որ գտնվեն իրենց կենտրոններում:

Ավելի բարձր կարգի Վորոնեի դիագրամներ

Չնայած Վորոնեի նորմալ բջիջը որոշված է որպես կետերի համախումբ,որոնք ամենամոտն են եզակի կետին S-ում, n-րդ կարգի Վորոնեի բջիջը որոշվում է` որպես կետերի հավաքածու,որոնք ունեն որոշակի n կետերի հավաքածու S-ում,ինչպես նրա n մոտիկ հարևանները : Ավելի բարձր կարգի Վորոնեի դիագրամները նույնպես բաժանում են տարածությունը:

Ավելի բարձր կարգի Վորոնեի դիագրամը կարող է ռեկուրսիվ գեներացվել: n-րդ կարգի Վորոնեի դիագրամ set S համախմբից ստեղծելու համար, սկսեք (n − 1)-կարգի դիագրամի պատվիրումից և փոխարինել յուրաքանչյուր բջիջը`գեներացված X = {x₁, x₂, ..., x_n−1} հետ, հավաքածուի վրա; Վորոնեի դիագրամ S − X.

Վորոնեի դիագրամի ամենահեռու կետը

Մի շարք n կետերի խմբի համար (n−1)^th-կարգի Վորոնեի դիագրամը կոչվում է Վորոնեի դիագրամի ամենահեռու կետ: Տրված կետերի համախմբի համար S = {p₁, p₂, ..., p_n} Վորոնեի դիագրամի հեռավոր կետերը բաժանում են հարթությունը բջիջների,որոնցում միևնույն P հանդիսանում է ամենահեռու կետը: Հարկ է նշել,որ P կետը ունի բջիջ Վորոնեի դիագրամի ամենահեռու կետում,այն և միայն այն դեպքում,եթե այդ գագաթը ուռուցիկ կեղև P-ից է:Այսպիսով,թող H = {h₁, h₂, ..., h_k}լինի ուռուցիկ կեղև P,,որում մենք որոշում ենք Վորոնեի դիագրամի ամենահեռու կետը,ինչպես հարթության բաժանումը k բջիջների,մեկը`ամեն մի H կետում,այն հատկության համաձայն,որ q կետը գտնվում է բջջում,որը համապատասխանում է h_i եթե և միայն այն դեպքում dist(q, h_i) > dist(q, p_j) յուրաքանչյուր p_j ∈ S h_i ≠ p_j հետ: Որտեղ dist(p, q)հանդիսանում էէվկլիդյան հեռավորություներկու կետերի միջև p և q.^[5] ^[6]

Ընդհանրացումներ և տատանումներ

Ինչպես բխում է սահմանումից,Վորոնեի բջիջները կարող են սահմանվել մետրայինի համար,բացի Էվկլիդյանից (օրինակ,այն Մահալանոբյան կամՄանհետոն) հեռավորություններ.Սակայն այդ դեպքում Վորոնեի բջիջների սահմանները կարող են լինել ավելի բարդ,քան Էվկլիդյանի դեպքում,քանի որ երկու կետերի միջև հավասարահեռ տեղամասերը կարող են չլինել ենթատարածք codimension 1-ից , նույնիսկ 2-չափանիի դեպքում.

Կշռված Վորոնեի դիագրամը հանդիսանում է այն,որում կետերի զույգի ֆունկցիաները Վորոնեի բջջի բացահայտման համար,հանդիսանում է հեռավորության ֆունկցիան,որը փոփոխվում է բազմապատկական կամ ընդհանուր կշիռներով,հանձնարարված գեներատորի միավորով: Ի տարբերություն Վորոնեի բջիջների,որոնք սահմանված են հեռավորության միջոցով,և հանդիսանում են մետրային,այս դեպքում Վորոնեի բջիջներից մի քանիսը կարող են դատարկ լինել:

Վորոնեի մոտավոր սխեման կետերի համախումբ է:Ուշադրություն դարձրեք Վորոնեի բջիջների ոչ հստակ սահմանների գույների փոփոխությանը:

Վորոնեի դիագրամի n կետերը d-չափանի տարածությունում պահանջում են $O(n^{\lceil d/2\rceil })$ տարածություն`պահպանման համար:Այսպիսով,Վորոնեի դիագրամները հաճախ չեն օգտագործվում d > 2 համար:Այլընտրանքային է համարվում մոտավոր Վորոնեի դիագրամիների օգտագործումը,որտեղ Վորոնեի վանդակները ունեն ոչ հստակ սահմաններ,որոնք կարող են լինել մոտավոր.^[7] Այլ տարբերակ,երբ յուրաքանչյուր կայք հանդիսանում է ոչ հստակ շրջան և արդյունքում բջիջները դառնում են ոչ հստակ.^[8] Վորոնեի դիագրամները կապված են նաև այլ երկրաչափական կառույցների հետ,ինչպիսիք են միջակա առանցքներ , ուղիղ կմախք, և դիագրամների սահման:

Դիմումներ

Վորոնեի դիագրամի վաղ դիմումներից է եղել Ջոն Սնոուուսումնասիրման համաճարակաբանություն համար 1854 խոլերիայի պոռթկում Սոհոում, Անգլիա. Նա ցույց է տվել հարաբերակցությունը, Լոնդոնի տարածքի քարտեզի վրա,օգտագործելով հատուկ ջրի պոմպ, եւ մահացության շատ դեպքերով տարածքներ,որոնք առաջացել են պայթյունների պատճառով:
Կետի գտնվելու վայրը տվյալների կառուցվածքը կարող է հիմնավորվել Վորոնեի դիագրամի գագաթում,որպեսզի պատասխանենք մոտակա հարևանի հարցերին,որի նպատակն է,գտնել օբյեկտ,որը կհանդիսանա տվյալ հարցին ամենամոտը:Մոտակա հարևան հարցերը ունեն բազմաթիվ դիմումներ:Օրինակ,կարող են ցանկանալ գտնել մոտակա հիվանդանուցը,կամ ամենանմանատիպ օբյեկտը տվյալ տվյալների բազայում:Շատ դիմումներ ունի վեկտորային քվանտավորումը,լայն օգտագուրծվող տվյալների սեղմումում.

Վորոնեի տրված դիագրամում կարող ենք նաև գտնելխոշորագույն դատարկ շրջանը մի շարք կետերում նաև առաջարկվող բազմանկյունում,օրինակ կառուցել նոր սուպերմարկետ բոլոր գոյություն ունեցող հնարավորությունների սահմաններում, որոնք գտնվում են մի որոշակի քաղաքում.

Վորոնեի դիագրամը`Վորոնեի դիագրամի ամենահեռու կետի հետ միասին օգտագործվում է էֆեկտիվ ալգորիմների հաշվարկման համար,որպեսզի հաշվարկեն շրջակա կետերի շարքը:^[5]

Վորոնեի դիագրամը օգտակար է պոլիմերների ֆիզիկայում: Այն կարող է օգտագործվել պոլիմերի ազատ ծավալ ցույց տալու համար.

Վորոնեի մոտեցումը ակտիվ օգտագործվում է շրջանի / [[շրջան] գնահատման համար` օգտագործելով տվյալների համախումբը համակարգում `չափիչ մեքենա.

Կլիմայագիտությունում, Վորոնեի դիագրամները օգտագործվում են,որպեսզի հաշվարկեն տարածքի տարափը,մի շարք կետերի չափումների հիման վրա: Այս օգտագործման մեջ, նրանք ընդհանրապես այսուհետ հիշվում են որպես Տիսսենի պոլիգոններ:

Վորոնեի դիագրամները օգտագործվում են,որպեսզի ուսումնասիրեն անտառների աճի եւ անտառային ծածկի օրինակները, եւ կարող է նաեւ օգտակար լինել մշակման կանխատեսող մոդելներ կառուցելիս` անտառային հրդեհների համար.

Վորոնեի դիագրամները օգտագործվում են նաև համակարգչային գրաֆիկայում,և առաջացնում որոշ տեսակի օրգանական փնտրում.

Ինքնավար նավարկության ռոբոտը , Վորոնեի դիագրամները օգտագործվում են,որպեսզի գտնեն հստակ ուղիները. Եթե կետերը` խոչընդոտներ են, ապա գրաֆիկի եզրերը կլինեն երթուղիներ հեռու խոչընդոտներից (եւ տեսականորեն ցանկացած բախումներ).

Նյութերի գիտությունում,բազմաթափանցիկ միկրոկառուցվածքները մետաղական համաձուլվածքներում սովորաբար ներկայանում են`օգտագործելով Վորոնեի խճանկարի բաղադրիչները:

Վորոնեի պոլիգոնները օգտագործվում են լեռնահանքերում,որպեսզի գնահատեն արժեքավոր նյութերի , հանքային կամ այլ ռեսուրսների պաշարները: Հետախուզական հորատում օգտագործվում են որպես միավորների փաթեթ Վորոնեի պոլիգոնում.

Մեքենայի ուսուցումում, Վորոնեի դիագրամները օգտագործվում են,որպեսզի կատարեն1-NN դասակարգումը.^[9]

Տես նաև

Ալգորիթմներ

Bowyer–Watson algorithm – an algorithm for generating a Voronoi diagram in any number of dimensions.
Fortune's algorithm – an O(n log(n)) algorithm for generating a Voronoi diagram from a set of points in a plane.
Lloyd's algorithm

Հարակից թեմաներ

Նշումներ

^ Ֆրանս Aurenhammer (1991). Վորոնեի դիագրամները –հիմնական երկրաչափական տվյալների կառուցվածքի հետազոտություն են: ACM հետազոտությունների թվարկում, 23(3):345–405, 1991
^ Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Տարածական տեսելյացիայի –Վորոնեի դիագրամների կիրառությունները և հասկացությունները : 2-րդ հրատարակություն. John Wiley, 2000, 671 էջ ISBN 0-471-98635-6
^ Daniel Reem, Վորոնեի դիագրամի ընդհանուր գեներատորի հաշվարկման ալգորիթմը ընդհանուր նորմալացված տարածությունում, Վեցերորդ միջազգային սիմպոզիումի աշխատանքում Վորոնեի դիագրամի համաձայն գիտության և տեխնիկայի ոլորտում (ISVD 2009), 2009, pp. 144–152
^ Daniel Reem, Վորոնեի դիագրամի երկրաչափական կայունությունը կայքերի փոքր փոփոխությունների նկատմամբ , ամբողջական տարբերակ: arXiv 1103.4125 (2011),ընդլայնված վերացական Extended abstract in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ‏2011), pp. 254–263
^ ^a ^b Mark de Berg, Marc van Kreveld, Mark Overmars,և Otfried Schwarzkopf (2008). Computational Geometry (Third edition ed.). Springer-Verlag. {{cite book}}: |edition= has extra text (help)CS1 maint: multiple names: authors list (link) 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm. Cite error: The named reference "berg2008" was defined multiple times with different content (see the help page).
^ Skyum, Sven (1991). "A simple algorithm for computing the smallest enclosing circle". Information Processing Letters 37(1991)121–125. {{cite journal}}: |first2= missing |last2= (help), Contains a simple algorithm to compute the farthest-point Voronoi diagram.
^ S. Arya, T. Malamatos, և D. M. Mount, Մոտավոր Վորոնեի դիագրամների արդյունավետ տարածքները, աշխատանքներ 34th ACM Symp.հաշվողական տեսության համաձայն (STOC 2002), pp. 721–730.
^ Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). "Uncertain Voronoi Diagram" (PDF). Information Processing Letters. 109 (13). Elsevier: 709–712. doi:10.1016/j.ipl.2009.03.007.
^ Tom M. Mitchell (1997). Machine Learning (International Edition 1997 ed.). McGraw-Hill. p. 233. ISBN 0-07-042807-7.

Կարծիքներ

Gustav Lejeune Dirichlet (1850). "Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen". Journal für die Reine und Angewandte Mathematik. 40: 209–227.
Voronoi, Georgy (1908). "Nouvelles applications des paramètres continus à la théorie des formes quadratiques". Journal für die Reine und Angewandte Mathematik. 133: 97–178. doi:10.1515/crll.1908.133.97.
Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams. 2nd edition. John Wiley, 2000, 671 pages ISBN 0-471-98635-6
Aurenhammer, Franz (1991). "Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure". ACM Computing Surveys. 23 (3): 345–405. doi:10.1145/116873.116880.
Bowyer, Adrian (1981). "Computing Dirichlet tessellations". The Computer Journal. Vol. 24, no. 2. pp. 162–166. doi:10.1093/comjnl/24.2.162.
Reem, Daniel (2009). "An algorithm for computing Voronoi diagrams of general generators in general normed spaces". Proceedings of the sixth International Symposium on Voronoi Diagrams in science and engineering (ISVD 2009). pp. 144–152. doi:10.1109/ISVD.2009.23.
Daniel Reem (2011). The geometric stability of Voronoi diagrams with respect to small changes of the sites. Full version: arXiv 1103.4125 (2011), Extended abstract: in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ‏2011), pp. 254–263.
Watson, David F. (1981). "Computing the n-dimensional tessellation with application to Voronoi polytopes". The Computer Journal. 24 (2): 167–172. doi:10.1093/comjnl/24.2.167.
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0. {{cite book}}: |edition= has extra text (help)CS1 maint: multiple names: authors list (link) Chapter 7: Voronoi Diagrams: pp. 147–163. Includes a description of Fortune's algorithm.
Rolf Klein (1989). Abstract voronoi diagrams and their applications. Lecture Notes in Computer Science. Vol. 333. Springer-Verlag. pp. 148–157. doi:10.1007/3-540-50335-8_31. ISBN 3-540-52055-4.

Արտաքին հղումներ

[1] Ֆրանս Aurenhammer (1991). Վորոնեի դիագրամները –հիմնական երկրաչափական տվյալների կառուցվածքի հետազոտություն են: ACM հետազոտությունների թվարկում, 23(3):345–405, 1991

[2] Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Տարածական տեսելյացիայի –Վորոնեի դիագրամների կիրառությունները և հասկացությունները : 2-րդ հրատարակություն. John Wiley, 2000, 671 էջ ISBN 0-471-98635-6

[Reem_alg-3] Daniel Reem, Վորոնեի դիագրամի ընդհանուր գեներատորի հաշվարկման ալգորիթմը ընդհանուր նորմալացված տարածությունում, Վեցերորդ միջազգային սիմպոզիումի աշխատանքում Վորոնեի դիագրամի համաձայն գիտության և տեխնիկայի ոլորտում (ISVD 2009), 2009, pp. 144–152

[Reem_geo_stable-4] Daniel Reem, Վորոնեի դիագրամի երկրաչափական կայունությունը կայքերի փոքր փոփոխությունների նկատմամբ , ամբողջական տարբերակ: arXiv 1103.4125 (2011),ընդլայնված վերացական Extended abstract in Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG ‏2011), pp. 254–263

[berg2008-5] Mark de Berg, Marc van Kreveld, Mark Overmars,և Otfried Schwarzkopf (2008). Computational Geometry (Third edition ed.). Springer-Verlag. {{cite book}}: |edition= has extra text (help)CS1 maint: multiple names: authors list (link) 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm. Cite error: The named reference "berg2008" was defined multiple times with different content (see the help page).

[6] Skyum, Sven (1991). "A simple algorithm for computing the smallest enclosing circle". Information Processing Letters 37(1991)121–125. {{cite journal}}: |first2= missing |last2= (help), Contains a simple algorithm to compute the farthest-point Voronoi diagram.

[7] S. Arya, T. Malamatos, և D. M. Mount, Մոտավոր Վորոնեի դիագրամների արդյունավետ տարածքները, աշխատանքներ 34th ACM Symp.հաշվողական տեսության համաձայն (STOC 2002), pp. 721–730.

[8] Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). "Uncertain Voronoi Diagram" (PDF). Information Processing Letters. 109 (13). Elsevier: 709–712. doi:10.1016/j.ipl.2009.03.007.

[9] Tom M. Mitchell (1997). Machine Learning (International Edition 1997 ed.). McGraw-Hill. p. 233. ISBN 0-07-042807-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]