Վորոնոյի դիագրամ

Վորոնոյի դիագրամ
Տեսակ	ալգորիթմ
Դաս	partition of a set? և Դիագրամ
Անվանված է	Գեորգի Վորոնոյ

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

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

Ամենապարզ և ամենածանոթ դեպքում (ցույց է տրված առաջին նկարում), մեզ տրվում է վերջավոր քանակությամբ կետեր {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 խանութները և այժմ Մանհետն հեռավորություն. Վորոնեի բջիջները երկու դեպքում էլ տարբեր են.

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

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

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

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

Օրինակներ

Սա Վորոնեի դիագրամի հատված է մի շարք պատահական միավորներով մի 3D չափանի վանդակումարկղում։ Ընդհանրապես 3D չափանի Վորոնեի խճանկարի անմիջապես խաչաձև բաժին չէ 2D Վորոնեի խճանկարը. (Այդ բջիջները բոլորը հանդիսանում են հավաքածու բազմանիստ.)

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

• 2D վանդակը տալիս է անկանոն բջիջներով խճանկար, հավասար վեցանկյունների հետ կետի սիմետրիկությամբ; կանոնավոր եռանկյուն վանդակի դեպքում դա հանդիսանում է սիմետրիկ ; ուղղանկյուն վանդակի դեպքում վեցանկյունները փոքրացնում են մինչև ուղղանկյունները շարքերում և սյուներում; Հրապարակ (երկրաչափություն) վանդակավոր տալիս կանոնավոր խճանկար և հրապարակներուa քառակուսի վանդակը տալիս է կանոնավոր վանդակներով խճանկար; նշենք որ ուղղանկյունները և քառակուսիները կարող են նաև գեներացվել այլ վանդակներից (օրինակի, վանդակ՝ որոշված վեկտորներով (1,0) և (1/2,1/2) տալիս է քառակուսիներ)։ Տես here Արխիվացված 2012-04-30 Wayback Machine որպես դինամիկ տեսողական օրինակ։
• Սովորական քառակուսի վանդակը տալիս է քառակուսի բջիջ.
• Վեցանկյուն փակ փաթեթավորված վանդակները տալիս են խճանկար տարածության վրա շեղանկյուն.
• Կենտրոնացված խորանարդի դեմքով վանդակները տալիս են խճանկար տարածության վրա շեղանկյան հետ.
• Կենտրոնացված խորանարդի մարմնով վանդակները տալիս են խճանկար տարածության վրակտրված ութանիստ.
• Զուգահեռ հարթությունները՝ կանոնավոր եռանկյուն վանդակներով, մյուս կենտրոնների հետ համեմատած, տալիս են վեցանկյուն պրիզմային բջիջներ(մեղրախորիսխներ).
• Մի շարք կենտրոնացված մարմիններով քառանկյուն վանդակները տալիս են խճանկարի կառուցվածքը տարածության վրա վեցանկյուն.

(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.

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

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

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

The Voronoi diagram of n points in d-dimensional space requires $O(n^{\lceil d/2\rceil })$ storage space. Therefore, Voronoi diagrams are often not feasible for d > 2. An alternative is to use approximate Voronoi diagrams, where the Voronoi cells have a fuzzy boundary, which can be approximated. Another alternative is when any site is a fuzzy circle and as a result the cells become fuzzy too.

Վորոնեի դիագրամները կապված են նաև այլ երկրաչափական կառույցների հետ, ինչպիսիք են միջակա առանցքներ, ուղիղ կմախք, և դիագրամների սահման։

Դիմումներ

• Վորոնեի դիագրամի վաղ դիմումներից է եղել Ջոն Սնոուուսումնասիրման համաճարակաբանություն համար 1854 խոլերիայի պոռթկում Սոհոում, Անգլիա. Նա ցույց է տվել հարաբերակցությունը, Լոնդոնի տարածքի քարտեզի վրա, օգտագործելով հատուկ ջրի պոմպ, և մահացության շատ դեպքերով տարածքներ, որոնք առաջացել են պայթյունների պատճառով։
• Կետի գտնվելու վայրը տվյալների կառուցվածքը կարող է հիմնավորվել Վորոնեի դիագրամի գագաթում, որպեսզի պատասխանենք մոտակա հարևանի հարցերին, որի նպատակն է, գտնել օբյեկտ, որը կհանդիսանա տվյալ հարցին ամենամոտը։ Մոտակա հարևան հարցերը ունեն բազմաթիվ դիմումներ։ Օրինակ, կարող են ցանկանալ գտնել մոտակա հիվանդանուցը, կամ ամենանմանատիպ օբյեկտը տվյալ տվյալների բազայում։ Շատ դիմումներ ունի վեկտորային քվանտավորումը, լայն օգտագուրծվող տվյալների սեղմումում.
• Վորոնեի տրված դիագրամում կարող ենք նաև գտնելխոշորագույն դատարկ շրջանը մի շարք կետերում նաև առաջարկվող բազմանկյունում, օրինակ կառուցել նոր սուպերմարկետ բոլոր գոյություն ունեցող հնարավորությունների սահմաններում, որոնք գտնվում են մի որոշակի քաղաքում.
• Վորոնեի դիագրամը՝ Վորոնեի դիագրամի ամենահեռու կետի հետ միասին օգտագործվում է էֆեկտիվ ալգորիմների հաշվարկման համար, որպեսզի հաշվարկեն շրջակա կետերի շարքը։
• Վորոնեի դիագրամը օգտակար է պոլիմերների ֆիզիկայում։ Այն կարող է օգտագործվել պոլիմերի ազատ ծավալ ցույց տալու համար.
• Վորոնեի մոտեցումը ակտիվ օգտագործվում է շրջանի / շրջան գնահատման համար՝ օգտագործելով տվյալների համախումբը համակարգում` չափիչ մեքենա.
• Կլիմայագիտությունում, Վորոնեի դիագրամները օգտագործվում են, որպեսզի հաշվարկեն տարածքի տարափը, մի շարք կետերի չափումների հիման վրա։ Այս օգտագործման մեջ, նրանք ընդհանրապես այսուհետ հիշվում են որպես Տիսսենի պոլիգոններ։
• Վորոնեի դիագրամները օգտագործվում են, որպեսզի ուսումնասիրեն անտառների աճի և անտառային ծածկի օրինակները, և կարող է նաև օգտակար լինել մշակման կանխատեսող մոդելներ կառուցելիս՝ անտառային հրդեհների համար.
• Վորոնեի դիագրամները օգտագործվում են նաև համակարգչային գրաֆիկայում, և առաջացնում որոշ տեսակի օրգանական փնտրում.
• Ինքնավար նավարկության ռոբոտը, Վորոնեի դիագրամները օգտագործվում են, որպեսզի գտնեն հստակ ուղիները. Եթե կետերը՝ խոչընդոտներ են, ապա գրաֆիկի եզրերը կլինեն երթուղիներ հեռու խոչընդոտներից (և տեսականորեն ցանկացած բախումներ).
• Նյութերի գիտությունում, բազմաթափանցիկ միկրոկառուցվածքները մետաղական համաձուլվածքներում սովորաբար ներկայանում են՝ օգտագործելով Վորոնեի խճանկարի բաղադրիչները։
• Վորոնեի պոլիգոնները օգտագործվում են լեռնահանքերում, որպեսզի գնահատեն արժեքավոր նյութերի, հանքային կամ այլ ռեսուրսների պաշարները։ Հետախուզական հորատում օգտագործվում են որպես միավորների փաթեթ Վորոնեի պոլիգոնում.
• Մեքենայի ուսուցումում, Վորոնեի դիագրամները օգտագործվում են, որպեսզի կատարեն1-NN դասակարգումը.

Տես նաև

Ալգորիթմներ

• 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

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

• Centroidal Voronoi tessellation
• Computational geometry
• Delaunay triangulation
• Mathematical diagram
• Natural neighbor interpolation
• Nearest neighbor search
• Nearest-neighbor interpolation
• Voronoi pole

Կարծիքներ

• 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. էջեր 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). էջեր 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 (օգնություն)CS1 սպաս․ բազմաթիվ անուններ: 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. էջեր 148–157. doi:10.1007/3-540-50335-8_31. ISBN 3-540-52055-4.

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

• Real time interactive Voronoi / Delaunay diagrams with draggable points, Java 1.0.2, 1996–1997 Արխիվացված 2011-11-11 Wayback Machine
• Real time interactive Voronoi and Delaunay diagrams with source code
• Demo for various metrics
• Mathworld on Voronoi diagrams
• Qhull for computing the Voronoi diagram in 2-d, 3-d, etc.
• Voronoi Diagrams: Applications from Archaeology to Zoology
• Voronoi Diagrams in CGAL, the Computational Geometry Algorithms Library
• Voronoi Web Site : using Voronoi diagrams for spatial analysis Արխիվացված 2008-09-05 Wayback Machine
• More discussions and picture gallery on centroidal Voronoi tessellations Արխիվացված 2013-06-16 Wayback Machine
• Voronoi Diagrams by Ed Pegg, Jr., Jeff Bryant, and Theodore Gray, Wolfram Demonstrations Project.
• Nice explanation of voronoi diagram and visual implementation of fortune's algorithm Արխիվացված 2014-12-27 Wayback Machine

Վիքիպահեստն ունի նյութեր, որոնք վերաբերում են «Վորոնոյի դիագրամ» հոդվածին։