Кинетикалық дөңес корпус - Kinetic convex hull

A кинетикалық дөңес корпус деректер құрылымы а кинетикалық мәліметтер құрылымы сақтайды дөңес корпус үздіксіз қозғалатын нүктелер жиынтығының.[1] Оны ажырату керек динамикалық дөңес корпус дискретті өзгеріске ұшыраған нүктелерді өңдейтін мәліметтер құрылымы, мысалы, үздіксіз қозғалыстың орнына нүктелерді кірістіру немесе жою.

2D жағдай

Екі өлшемді кинетикалық дөңес корпус мәселесі үшін ең танымал мәліметтер құрылымы - Басч, Гуйбас, және Хершбергер. Бұл деректер құрылымы жауап береді, нәтижелі, ықшам және жергілікті.[1]

Мәліметтер құрылымы

The қосарланған нүктелер жиынтығының дөңес корпусы - бұл қос сызықтар жиынтығының жоғарғы және төменгі конверттері. Сондықтан, қозғалмалы сызықтар жиынтығының жоғарғы және төменгі конверттерін ұстап тұру, қозғалатын нүктелер жиынтығының дөңес қабығын сақтауға тең. Жоғарғы және төменгі конверттерді есептеу - бұл эквивалентті мәселелер, сондықтан сызықтар жиынтығының жоғарғы конвертін есептеу қозғалатын нүктелер жиегінің дөңес корпусын есептеуге тең. Статикалық сызықтар жиынтығының жоғарғы конвертін алгоритмді бөлу және бағындыру ол сызықтарды бірдей көлемдегі екі жиынға бөліп, екі жиынтықта рекурсивті түрде олардың жоғарғы конверттерін табу үшін шақырады, содан кейін пайда болған екі жоғарғы конверттерді біріктіреді. Біріктіру қадамы a көмегімен орындалады тік сызық. Ұпайлардың бірінші жиынтығын көк, ал екінші нүктелерін қызыл деп атаңыз.

Жоғарғы конверттерді біріктірудің сызықтық сыпыру алгоритмі қызыл және көк жоғарғы конверттердің барлық төбелерін солдан оңға қарай жүргізеді. Жақында кездескен қызыл және көк нүктелер сызық сыпырылған кезде сақталады. Нүктеге тап болғанда, алгоритм нүктенің қарама-қарсы түстің соңғы кездескен нүктесінен кейінгі кесіндіден жоғары немесе төмен екенін тексереді. Егер ол жоғарыда болса, онда бұл нүкте біріктірілген жоғарғы конвертке қосылады. Егер ол соңғы қосылған нүктеден өзгеше болса, қызыл және көк конверттер қиылысқан, сондықтан қиылысу нүктесі біріктірілген жоғарғы конвертке де қосылады.[2]

Осы алгоритмнен туындайтын жиектер мен төбелердің реттілігі тек нүктелердің реттелуіне және сызық-нүктелік салыстырулардың нәтижелеріне байланысты. Осылайша, нәтижені келесі сертификаттармен куәландыруға болады:

  • x-сертификаттар () тапсырысты қызыл және көк конверттердің шыңдарын куәландыру үшін қолданылады. Олар сертификаттар кинетикалық сұрыпталған тізім шыңдар жиынтығында. Әр нүкте 2 жолдан, ал сертификат 2 ұпайдан тұратындықтан, әр сертификат 4 жолдан тұрады.
  • у-сертификаттар () шыңның шетінен жоғары немесе төмен орналасқандығын растау үшін қолданылады. Сертификаттар алгоритм кезінде болатын барлық салыстырулар үшін пайда болады.

Осы сертификаттардың барлығында біріктіру қадамдары бірдей орындалады, сондықтан алынған жоғарғы конверт бірдей болады. Жоғарғы конверттерге арналған кинетикалық мәліметтер құрылымын осы сертификаттардың көмегімен статикалық жоғарғы конверт алгоритмін куәландыру арқылы жасауға болады. Алайда, бұл схема жергілікті емес, өйткені бір жол көптеген басқа сертификаттарға қатысады, егер ол басқа конверттен қанша нүкте кездессе, сол жағында немесе үстінде қалады.

Осылайша, s-сертификаттарын енгізу қажет () бұл сызық көлбеуінің басқа сызық көлбеуінен үлкен немесе кем екенін куәландырады.

Барлық ab нүктелері үшін келесі сертификаттардың болуы біріктіру нәтижесінде пайда болатын жиектер мен төбелердің дәйектілігін растауға жеткілікті, әр жолға тек O (1) сертификаттары бар:[1]

Бірнеше айырмашылық жағдайындағы сертификаттардың суреті
Сертификаттар қызыл және көк конверттер қиылысының құрылымын қиылыстарды (жоғарғы сол жақта) немесе қиылыстардың жоқтығын (жоғарғы оң және төменгі) куәландыру арқылы куәландырады. Көрсеткілер қандай элементтер сертификатпен салыстырылатындығын көрсетеді.
  1. : . ең жақын шыңды білдіреді оның оң жағында. Бұл сертификат барлық нүктелер үшін сақталады нүктеден басқа түсі бар, , олардың артынан жүреді.
  2. : немесе . Бұл сертификат барлық нүктелер үшін сақталады осындай қиылысады . -ның үміткер шетін білдіреді , жоғарғы немесе төмен орналасқан басқа конверттің шеті .
  3. : немесе . Бұл сертификат барлық нүктелер үшін сақталады осындай қиылысады .
  4. : . Бұл сертификат барлық нүктелер үшін сақталады ол үшін және .
  5. : . Бұл сертификат барлық нүктелер үшін сақталады ол үшін және .
  6. : . Бұл сертификат барлық нүктелер үшін сақталады ол үшін және .
  7. : . Бұл сертификат барлық нүктелер үшін сақталады ол үшін және .
  8. : . Бұл сертификат барлық нүктелер үшін сақталады ол үшін және .

Бірінші сертификат, , қызыл және көк конверттегі ұпайлардың х реті бойынша куәландырады. Екінші және үшінші сертификаттар, және , қызыл және көк конверттердің қиылыстарын куәландырыңыз. Қалған 5 сертификат, , , , , және жоғарғы конверттерде жоқ жиектерді оның үстіндегі шеттердің көлбеу ретімен орналастырыңыз. Егер көлбеу тізбектің басында немесе соңында болса, немесе осыны растаңыз. Егер бұл реттіліктің ортасында болса , және осыны растаңыз және шеттері көлбеу болатын екі сызықтың қиылысу нүктесі оның үстінде екенін куәландырады. Осы бір немесе үш сертификат барлық шеттердің осы сызықтан жоғары екендігін дәлелдеуге жеткілікті. Алдыңғы схемадан айырмашылығы, барлық жолдар тек сертификаттардың тұрақты санына қатысты. Осы сертификаттар сәтсіз болған кезде, біріктірілген конверт пен сертификаттарды O (1) уақытта жаңартуға болады.

Дөңес корпусқа арналған кинетикалық мәліметтер құрылымы осы сертификаттардың көмегімен жоғарғы конверттердің рекурсивті бірігуін куәландырады. Сертификаттар сәтсіздікке ұшыраған сайын, олардың бірігуі жаңартылады, ал егер біріктіру нәтижесінде пайда болған конверт өзгерсе, онда өзгерістер біріктіру нәтижесіне байланысты барлық біріктірулер арқылы таралады.[1]

Өнімділік

Бұл деректер құрылымы жауап береді, жергілікті, ықшам, және нәтижелі. Бұл жоғарғы конвертті куәландыру үшін қолданылатын біріктірулердің логарифмдік тереңдігіне байланысты.[1]

  • Жауапты: Сертификат сәтсіз болған кезде, ол куәландыратын біріктіруді түзету үшін O (1) қажет. Егер алынған конверт өзгерсе, өзгеріс біріктірілген нәтижеге байланысты барлық біріктірулерге дейін таралуы керек. O бар (журнал n) мұндай бірігу, сондықтан жаңартуды O (журналда) жасауға болады n) жалпы уақыт.
  • Жергілікті: Әрбір жол көбіне О-ға қатысады (журнал n) сертификаттар. Себебі, әр жол әр біріктірілу кезінде сертификаттардың тұрақты санына қатысады, ал әр жол O (журналда) болады n) біріктіреді.
  • Ықшамдық: Бұл деректер құрылымында қолданылатын сертификаттардың максималды саны O (n журнал n). Себебі, әрбір біріктіру біріктірілген жолдар санына сызықтық бірнеше сертификаттарды қамтиды. Жоғарғы конвертті сертификаттау n жолдар үшін екі ішкі жиынның жоғарғы конвертін біріктіру үшін сертификаттар қажет n/ 2 жол және конверттерді біріктіруге арналған сертификаттар. Сонымен, сертификаттар саны, C (n), жоғарғы конвертті куәландыру үшін қажет n сызықтар C қайталануын қанағаттандырадыn) = 2C (n/ 2) + O (n), C (1) = O (1) бар. Бойынша Бөлу және бағындыру қайталануларына арналған теореманы меңгеру, C (n) = O (n журнал n).
  • Тиімділік: Осы алгоритммен өңделген оқиғалардың максималды саны алгебралық немесе жалған алгебралық траекториялары квадратқа жақын, барлығына .[3][4] Сызықтық қозғалатын нүктелердің дөңес корпустары өзгеруі мүмкін рет.[5] Осылайша, бұл мәліметтер құрылымы тиімді.

Жоғары өлшемдер

Ан табу нәтижелі 2-ден жоғары өлшемдерде қозғалатын нүктелердің дөңес корпусын ұстап тұруға арналған кинетикалық мәліметтер құрылымы ашық мәселе болып табылады.[1]

Өзара байланысты мәселелер

Кинетикалық дөңес корпусты келесі мәселелерді шешу үшін пайдалануға болады:[6]

Әдебиеттер тізімі

  1. ^ а б c г. e f Бас, Джулиен; Гуйбас, Леонидас Дж .; Хершбергер, Джон (сәуір, 1999). «Мобильді деректерге арналған деректер құрылымы» (PDF). J. алгоритмдері. 31 (1): 1–28. CiteSeerX  10.1.1.134.6921. дои:10.1006 / jagm.1998.0988.
  2. ^ Хершбергер, Джон (1989 ж. 21 желтоқсан). «Жоғарғы конвертті табу n сызық сегменттері O (n журнал n) уақыт ». Ақпаратты өңдеу хаттары. 33 (4): 169–174. дои:10.1016/0020-0190(89)90136-1.
  3. ^ Агарвал, Панкай К .; Шварцкопф, Отфрид; Шарир, Миха (1996 ж. Қаңтар). «Төменгі конверттердің қабаттасуы және оның қосымшалары». Дискретті және есептеу геометриясы. 15 (1): 1–13. CiteSeerX  10.1.1.54.5488. дои:10.1007 / BF02716576.
  4. ^ Шарир, Миха (1994). «Үлкен өлшемдегі төменгі конверттердің жоғарғы шектері. Дискретті және есептеу геометриясы». Дискретті және есептеу геометриясы. 12 (1): 327–345. дои:10.1007 / BF02574384.
  5. ^ Агарвал, Панкай К .; Гуйбас, Леонидас Дж .; Гершбергер, Джон; Вич, Эрик (2001 ж. Қаңтар). «Қозғалмалы нүктелер жиілігін сақтау». Дискретті және есептеу геометриясы. 26 (3): 353–374. CiteSeerX  10.1.1.47.8510. дои:10.1007 / s00454-001-0019-x.
  6. ^ Агарвал, Панкай К .; Гуйбас, Леонидас Дж .; Гершбергер, Джон; Veach, Эрик (тамыз 1997). «Қозғалатын нүктелер жиілігін сақтау». Информатикадағы дәрістер 1272 том. Алгоритмдер мен мәліметтер құрылымы бойынша 5-семинар (WADS '97). 31-44 бет. дои:10.1007/3-540-63307-3_46.