Jump to content

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

From Wikipedia, the free encyclopedia

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


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

[edit]

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

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

[edit]

Թույլ տանք բացակով (ոչ դադարկ սահմանել) ապահովված հեռավորության ֆունկցիայով . Թույլ տանք ինդեքսների ամբողջություն և թույլ տանք (դասավորված հավաքածու) ոչ դատարկենթաբազմություն (կայքերի) տարածության մեջ  : Վորոնեի բջիջը կամ Վորոնեի շրջանը, , կապված կայքից այն բոլոր կետերի հավաքածուն է ում որոնցից հեռավորությունը մինչև մեծ չէ,քան այլ կայքերից հեռավորությունը ,որտեղ յուրաքնչյուր ինդեքս տարբերվում է -ից: Այլ խոսքով,եթե նշանակում է հեռավորություն կետի և ենթաբազմության, այնուհետև

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

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

[edit]

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

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

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

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

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

[edit]

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

Օրինակներ

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

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

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

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

[edit]

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

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

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

[edit]

Մի շարք 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]

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

[edit]

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

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

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

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

Դիմումներ

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

Տես նաև

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

Նշումներ

[edit]
  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. ^ a b Mark de Berg, Marc van Kreveld, Mark OvermarsOtfried 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.

Կարծիքներ

[edit]

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

[edit]