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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Ամենապարզ դեպքը[խմբագրել]

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

Պաշտոնական սահմանումը[խմբագրել]

Թույլ տանք  \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 խանութները և այժմ Մանհետն հեռավորություն. Վորոնեի բջիջները երկու դեպքում էլ տարբեր են.


Հատկություններ[խմբագրել]

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

Պատմությունը և հետազոտությունը[խմբագրել]

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

Օրինակներ[խմբագրել]

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

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

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

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

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

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

Վորոնեի դիագրամի ամենահեռու կետը[խմբագրել]

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

Ընդհանրացումներ և տատանումներ[խմբագրել]

Ինչպես բխում է սահմանումից, Վորոնեի բջիջները կարող են սահմանվել մետրայինի համար, բացի Էվկլիդյանից (օրինակ, այն Մահալանոբյան կամՄանհետոն) հեռավորություններ. Սակայն այդ դեպքում Վորոնեի բջիջների սահմանները կարող են լինել ավելի բարդ, քան Էվկլիդյանի դեպքում, քանի որ երկու կետերի միջև հավասարահեռ տեղամասերը կարող են չլինել ենթատարածք 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.[7] Another alternative is when any site is a fuzzy circle and as a result the cells become fuzzy too.[8]

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

Դիմումներ[խմբագրել]

  • Վորոնեի տրված դիագրամում կարող ենք նաև գտնելխոշորագույն դատարկ շրջանը մի շարք կետերում նաև առաջարկվող բազմանկյունում,օրինակ կառուցել նոր սուպերմարկետ բոլոր գոյություն ունեցող հնարավորությունների սահմաններում, որոնք գտնվում են մի որոշակի քաղաքում.
  • Վորոնեի դիագրամը` Վորոնեի դիագրամի ամենահեռու կետի հետ միասին օգտագործվում է էֆեկտիվ ալգորիմների հաշվարկման համար, որպեսզի հաշվարկեն շրջակա կետերի շարքը:[5]
  • Վորոնեի դիագրամը օգտակար է պոլիմերների ֆիզիկայում: Այն կարող է օգտագործվել պոլիմերի ազատ ծավալ ցույց տալու համար.
  • Կլիմայագիտությունում, Վորոնեի դիագրամները օգտագործվում են, որպեսզի հաշվարկեն տարածքի տարափը, մի շարք կետերի չափումների հիման վրա: Այս օգտագործման մեջ, նրանք ընդհանրապես այսուհետ հիշվում են որպես Տիսսենի պոլիգոններ:
  • Վորոնեի դիագրամները օգտագործվում են, որպեսզի ուսումնասիրեն անտառների աճի և անտառային ծածկի օրինակները, և կարող է նաև օգտակար լինել մշակման կանխատեսող մոդելներ կառուցելիս` անտառային հրդեհների համար.
  • Վորոնեի դիագրամները օգտագործվում են նաև համակարգչային գրաֆիկայում, և առաջացնում որոշ տեսակի օրգանական փնտրում.
  • Ինքնավար նավարկության ռոբոտը, Վորոնեի դիագրամները օգտագործվում են, որպեսզի գտնեն հստակ ուղիները. Եթե կետերը`​ խոչընդոտներ են, ապա գրաֆիկի եզրերը կլինեն երթուղիներ հեռու խոչընդոտներից (և տեսականորեն ցանկացած բախումներ).
  • Նյութերի գիտությունում, բազմաթափանցիկ միկրոկառուցվածքները մետաղական համաձուլվածքներում սովորաբար ներկայանում են` օգտագործելով Վորոնեի խճանկարի բաղադրիչները:
  • Վորոնեի պոլիգոնները օգտագործվում են լեռնահանքերում, որպեսզի գնահատեն արժեքավոր նյութերի, հանքային կամ այլ ռեսուրսների պաշարները: Հետախուզական հորատում օգտագործվում են որպես միավորների փաթեթ Վորոնեի պոլիգոնում.

Տես նաև[խմբագրել]

Ալգորիթմներ
Հարակից թեմաներ

Նշումներ[խմբագրել]

  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
  3. Daniel Reem, Վորոնեի դիագրամի ընդհանուր գեներատորի հաշվարկման ալգորիթմը ընդհանուր նորմալացված տարածությունում, Վեցերորդ միջազգային սիմպոզիումի աշխատանքում Վորոնեի դիագրամի համաձայն գիտության և տեխնիկայի ոլորտում (ISVD 2009), 2009, pp. 144–152
  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
  5. 5,0 5,1 Mark de Berg, Marc van Kreveld, Mark OvermarsOtfried Schwarzkopf (2008)։ Computational Geometry, Third edition, Springer-Verlag։  7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
  6. Skyum, Sven (1991). «A simple algorithm for computing the smallest enclosing circle». Information Processing Letters 37(1991)121–125. , Contains a simple algorithm to compute the farthest-point Voronoi diagram.
  7. S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721–730.
  8. Jooyandeh, Mohammadreza; Mohades, Ali; Mirzakhah, Maryam (2009). «Uncertain Voronoi Diagram». Information Processing Letters (Elsevier) 109 (13): 709–712. doi:10.1016/j.ipl.2009.03.007. http://jooyandeh.info/Publications/UncertainVoronoiDiagram.pdf. 
  9. Tom M. Mitchell (1997)։ Machine Learning, International Edition 1997, McGraw-Hill, 233։ ISBN 0-07-042807-7։ 

Կարծիքներ[խմբագրել]

Արտաքին հղումներ[խմբագրել]

Commons-logo.svg