Клее өлшемдер мәселесі: Есептеу геометриясындағы қиындықтар

Кіріспе

Есептеу геометриясы мәселесі

Есептеу геометриясында Клейдің өлшем мәселесі — (көпөлшемді) тікбұрышты диапазондық кеңістіктердің бірігімінің өлшемін қаншалықты тиімді есептеуге болатынын анықтау мәселесі. Мұндағы d өлшемді тікбұрышты диапазон — нақты сандардың d интервалының декарт көбейтіндісі ретінде анықталады, ол Rd жиынының ішкі жиыны болып табылады. Бұл мәселе Виктор Клейдің атымен аталады, ол интервалдардың бірігімінің ұзындығын есептеу алгоритмін ұсынған (d = 1 жағдайы), кейіннен бұл алгоритм есептеу күрделілігі теориясы тұрғысынан ең тиімді екені дәлелденді. 2 өлшемді тікбұрышты диапазондық кеңістіктердің бірігімінің ауданын есептеудің есептеу күрделілігі қазір белгілі, бірақ d ≥ 3 жағдайы әлі де шешілмеген мәселе болып қала береді.

Тарих және алгоритмдер

1977 жылы Виктор Кли келесі мәселені қарастырды: нақты түзудегі n интервалдар жиынтығы берілгенде, олардың біріктірілген кесіндісінің ұзындығын есептеңіз. Ол содан кейін осы мәселені шешу үшін алгоритм ұсынды, оның есептеу күрделілігі (немесе «жұмыс уақыты») – бұл тұжырымның мағынасын үлкен O белгісінен қараңыз. Интервалдарды сұрыптауға негізделген бұл алгоритмді кейін Майкл Фредман мен Брюс Вайд (1978) оңтайлы деп көрсетті. Кейін 1977 жылы Джон Бентли осы мәселенің 2 өлшемді аналогын қарастырды: n тіктөртбұрыштар жиынтығы берілгенде, олардың біріктірілген ауданын табыңыз. Ол сондай-ақ күрделілігі бар алгоритмді алды, қазір Бентли алгоритмі деп аталатын, мәселені n 1 өлшемді мәселелерге келтіруге негізделген: бұл аумақ бойынша тік сызықты жылжыту арқылы жасалады. Бұл әдіс арқылы біріктірілген ауданды оның өзін нақты құрастырмай-ақ есептеуге болады. Бентли алгоритмі қазір 2 өлшемді жағдайда да оңтайлы деп танылған және компьютерлік графика, басқа салалармен қатар, қолданылады. Бұл екі мәселе – 1 және 2 өлшемді жалпы сұрақтардың ерекше жағдайлары: n d өлшемді тіктөртбұрышты диапазон жиынтығы берілгенде, олардың біріктірілген өлшемін есептеңіз. Бұл жалпы мәселе Клидің өлшем проблемасы деп аталады. d өлшемді жағдайға жалпыланғанда, Бентли алгоритмінің жұмыс уақыты келесідей болады. Бұл оңтайлы емес болып шығады, өйткені ол d өлшемді мәселені тек n (d-1) өлшемді мәселелерге бөледі және бұл кіші мәселелерді одан әрі бөле алмайды. 1981 жылы Ян ван Леувен мен Дерек Вуд динамикалық төрттік ағаштарды пайдалану арқылы d ≥ 3 үшін осы алгоритмнің жұмыс уақытын жақсартты. 1988 жылы Марк Овермарс пен Чи Яп d ≥ 3 үшін жаңа алгоритм ұсынды. Олардың алгоритмі мәселені 2 өлшемді компоненттерге бөлу және осы компоненттерді тиімді түрде жинақтау үшін kd-ағашына ұқсас дерек құрылымын қолданады; 2 өлшемді мәселелер өздері тральдік құрылымды пайдалану арқылы тиімді шешіледі. Бентли алгоритміне қарағанда асимптотикалық жағынан жылдам болғанымен, оның дерек құрылымдары айтарлықтай көп орынды пайдаланады, сондықтан ол тек n немесе d үлкен мәселелерде қолданылады. 1998 жылы Богдан Члебус d = 3 немесе 4 болатын ерекше жағдайларда бірдей асимптотикалық жұмыс уақытын қамтитын қарапайым алгоритм ұсынды. 2013 жылы Тимоти М. Чан динамикалық дерек құрылымдарын қажет етпейтін және логарифмдік коэффициентті жоятын, d ≥ 3 үшін ең жақсы белгілі жұмыс уақытын төмендететін алгоритмді жасады.

In 1977, Victor Klee considered the following problem: given a collection of n intervals in the real line, compute the length of their union. He then presented an algorithm to solve this problem with computational complexity (or "running time") — see Big O notation for the meaning of this statement. This algorithm, based on sorting the intervals, was later shown by Michael Fredman and Bruce Weide (1978) to be optimal. Later in 1977, Jon Bentley considered a 2 dimensional analogue of this problem: given a collection of n rectangles, find the area of their union. He also obtained a complexity algorithm, now known as Bentley's algorithm, based on reducing the problem to n 1 dimensional problems: this is done by sweeping a vertical line across the area. Using this method, the area of the union can be computed without explicitly constructing the union itself. Bentley's algorithm is now also known to be optimal (in the 2 dimensional case), and is used in computer graphics, among other areas. These two problems are the 1 and 2 dimensional cases of a more general question: given a collection of n d dimensional rectangular ranges, compute the measure of their union. This general problem is Klee's measure problem. When generalized to the d dimensional case, Bentley's algorithm has a running time of This turns out not to be optimal, because it only decomposes the d dimensional problem into n (d 1) dimensional problems, and does not further decompose those subproblems. In 1981, Jan van Leeuwen and Derek Wood improved the running time of this algorithm to for d ≥ 3 by using dynamic quadtrees. In 1988, Mark Overmars and Chee Yap proposed an algorithm for d ≥ 3. Their algorithm uses a particular data structure similar to a kd tree to decompose the problem into 2 dimensional components and aggregate those components efficiently; the 2 dimensional problems themselves are solved efficiently using a trellis structure. Although asymptotically faster than Bentley's algorithm, its data structures use significantly more space, so it is only used in problems where either n or d is large. In 1998, Bogdan Chlebus proposed a simpler algorithm with the same asymptotic running time for the common special cases where d is 3 or 4. In 2013, Timothy M. Chan developed a simpler algorithm that avoids the need for dynamic data structures and eliminates the logarithmic factor, lowering the best known running time for d ≥ 3 to .

Белгілі шекаралар

Кез келген d үшін белгілі жалғыз төменгі шек – , және d=1 және d=2 үшін осы орындалу уақытымен оптималды алгоритмдер белгілі. Чан алгоритмі d ≥ 3 үшін жоғарғы шек береді, сондықтан d ≥ 3 үшін жылдам алгоритмдердің болуы немесе, керісінше, қатаң төменгі шектерді дәлелдеу мүмкіндігі ашық мәселе болып қалады. Атап айтқанда, алгоритмнің орындалу уақыты d-ге тәуелді болуы керек пе деген сұрақ ашық күйде қалады. Сонымен қатар, ерекше жағдайларды (мысалы, кіріс координаттары шектелген диапазон ішіндегі бүтін сандар болғанда) шеше алатын жылдам алгоритмдердің бар-жоқтығы да ашық мәселе болып қалады. 1D Клейдің өлшем мәселесі (интервалдардың бірігуі) p – барлық интервалдарды тесуге қажетті тесу нүктелерінің саны болғанда шешілуі мүмкін (ортақ нүктемен тесілген интервалдардың бірігуін экстремумдарды есептеу арқылы сызықтық уақытта есептеуге болады). Параметр p – кіріс конфигурациясына байланысты бейімделетін параметр, ал тесу алгоритмі Клейдің өлшем мәселесі үшін бейімделетін алгоритмді ұсынады.

Маңызды құжаттар

Please provide the English text you want me to translate. I need the content of the "English text" section to perform the translation. I will use the "Existing translation reference" only as a guide for terminology, prioritizing accuracy to the original English meaning.

Екіншілік әдебиет

Франко П. Препарата және Майкл И. Шамос (1985). Есептеу геометриясы (Springer Verlag, Берлин). Клейдің өлшемдер мәселесі, профессор Джефф Эриксонның есептеу геометриясы саласындағы ашық мәселелер тізімінен. (Соңғы күрделі өзгеріс 1998 жылдың 31 шілдесінде жасалған, 2005 жылдың 8 қарашасында қарастырылды.)