Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Есептеу геометриясындағы проблемалар отбасы
Family of problems in computational geometry
Нүкте орналасу мәселесі есептеу геометриясының негізгі тақырыбы болып табылады. Ол геометриялық деректерді өңдеумен айналысатын салаларда қолданылады: компьютерлік графика, географиялық ақпараттық жүйелер (ГИС), қозғалыс жоспарлау және компьютерлік көмекпен жобалау (CAD). Ең жалпы түрінде мәселе мынадай: кеңістік бөлінген аймақтарға бөлінген кезде, сұраныс нүктесі қай аймақта орналасқанын анықтау. Мысалы, графикалық пайдаланушы интерфейсінің қай терезесінде берілген тышқанның басуы бар екенін анықтау мәселесі, нүкте орналасу мәселесінің бір мысалы ретінде қарастырылуы мүмкін, бұл жағдайда әр терезенің көрінетін бөліктерінен құрылған бөлініс пайдаланылады. Дегенмен, осы қолданба үшін арнайы дерек құрылымдары жалпы мақсаттағы нүкте орналасу дерек құрылымдарынан тиімдірек болуы мүмкін. Тағы бір ерекше жағдай – көпбұрыш ішіндегі нүкте мәселесі, онда нүкте бір көпбұрыштың ішінде, сыртында немесе шекарасында екені анықталуы керек. Көптеген қолданбаларда кеңістіктің бір бөлігіне қатысты бірнеше түрлі нүктенің орналасуын анықтау қажет. Бұл мәселені тиімді шешу үшін, сұраныс нүктесі берілгенде, сұраныс нүктесі орналасқан аймақты жылдам анықтайтын дерек құрылымын құру пайдалы (мысалы, Вороной диаграммасы).
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD). In its most general form, the problem is, given a partition of the space into disjoint regions, to determine the region where a query point lies. For example, the problem of determining which window of a graphical user interface contains a given mouse click can be formulated as an instance of point location, with a subdivision formed by the visible parts of each window, although specialized data structures may be more appropriate than general purpose point location data structures in this application. Another special case is the point in polygon problem, in which one needs to determine whether a point is inside, outside, or on the boundary of a single polygon. In many applications, one needs to determine the location of several different points with respect to the same partition of the space. To solve this problem efficiently, it is useful to build a data structure that, given a query point, quickly determines which region contains the query point (e. g. Voronoi Diagram).
Жазық корпус
Жазық жағдайда бізге беттер деп аталатын көпбұрыштардан тұратын S жазық бөлінісі беріледі және сұраныс нүктесі қай бетке тиесілі екенін анықтау қажет. Көпбұрыш ішіндегі нүктені табу алгоритмін қолданып, әрбір бетті күшпен іздеуге болады, бірақ бұл күрделілігі жоғары бөліністер үшін көбінесе тиімсіз. Әр түрлі тәсілдер оңтайлы дерек құрылымдарына алып келеді, олардың сақтау кеңістігі O(n) және сұраныс уақыты O(log n) құрайды, мұнда n – S-дегі барлық төбелердің саны. Айтарлықтай жеңілдету үшін, жазық бөлініс тіктөртбұрышты шектеудің ішінде орналасқан деп есептейміз.
In the planar case, we are given a planar subdivision S, formed by multiple polygons called faces, and need to determine which face contains a query point. A brute force search of each face using the point in polygon algorithm is possible, but usually not feasible for subdivisions of high complexity. Several different approaches lead to optimal data structures, with O(n) storage space and O(log n) query time, where n is the total number of vertices in S. For simplicity, we assume that the planar subdivision is contained inside a square bounding box.
Сабақтардың ыдырауы
Добкин мен Липтон 1976 жылы O(log n) уақытты қамтамасыз ететін ең қарапайым және ерте дерек құрылымын тапты. Ол S-тің әр төбесінен өтетін тік сызықтар арқылы S-ті бөлуге негізделген. Екі тік сызық арасындағы аймақ қабырға деп аталады. Әр қабырға солдан оңға қарай толықтай кесіп өтетін қиылыспайтын сызық сегменттерімен бөлінеді. Қабырға ішіндегі екі тікелей сегмент арасындағы аймақ S-тің бірегей жағына сәйкес келеді. Сондықтан біз нүкте табу мәселесін екі қарапайым мәселеге келтіреміз:
The simplest and earliest data structure to achieve O(log n) time was discovered by Dobkin and Lipton in 1976. It is based on subdividing S using vertical lines that pass through each vertex in S. The region between two consecutive vertical lines is called a slab. Notice that each slab is divided by non intersecting line segments that completely cross the slab from left to right. The region between two consecutive segments inside a slab corresponds to a unique face of S. Therefore, we reduce our point location problem to two simpler problems:
Тік қабырғаларға бөлінген жазықтықты ескере отырып, берілген нүкте қай қабырғада орналасқанын анықтаңыз. Солдан оңға қарай толықтай кесіп өтетін қиылыспайтын сегменттермен аймақтарға бөлінген қабырғаны ескере отырып, берілген нүкте қай аймақта орналасқанын анықтаңыз. Бірінші мәселені тік сызықтардың x координатасы бойынша O(log n) уақытында бинарлық іздеу арқылы шешуге болады. Екінші мәселені де бинарлық іздеу арқылы O(log n) уақытында шешуге болады. Сегменттер қиылыспайды және қабырғаны толықтай кесіп өтеді, сондықтан сегменттерді әр қабырғаның ішінде тік бағытта реттеуге болады. Бұл алгоритм нүктені логарифмдік уақытта табуға мүмкіндік береді және оны жүзеге асыру оңай болса да, қабырғаларды және олардың ішіндегі аймақтарды құру үшін қажетті жад O(n²) дейін жете алады, өйткені әр қабырға сегменттердің маңызды бөлігін кесіп өтуі мүмкін. Бірнеше автор екі жақын қабырғаны кесіп өтетін сегменттердің көбінесе бірдей екенін байқады. Сондықтан дерек құрылымының мөлшерін айтарлықтай азайтуға болады. Нақтырақ айтқанда, Сарнак пен Таржан тік сызықты l-ді солдан оңға қарай жазықтық бойынша жылжытады, сонымен бірге l-ді қиылыстыратын сегменттерді сақтайды. Бұл оларға жадты O(n) дейін азайтуға мүмкіндік береді, сонымен бірге O(log n) сұраныс уақытын сақтайды.
Given a subdivision of the plane into vertical slabs, determine which slab contains a given point. Given a slab subdivided into regions by non intersecting segments that completely cross the slab from left to right, determine which region contains a given point. The first problem can be solved by binary search on the x coordinate of the vertical lines in O(log n) time. The second problem can also be solved in O(log n) time by binary search. To see how, notice that, as the segments do not intersect and completely cross the slab, the segments can be sorted vertically inside each slab. While this algorithm allows point location in logarithmic time and is easy to implement, the space required to build the slabs and the regions contained within the slabs can be as high as O(n²), since each slab can cross a significant fraction of the segments. Several authors noticed that the segments that cross two adjacent slabs are mostly the same. Therefore, the size of the data structure can be significantly reduced. More specifically, Sarnak and Tarjan sweep a vertical line l from left to right over the plane, while maintaining the segments that intersect l in a Persistent red black tree. This allows them to reduce the storage space to O(n), while maintaining the O(log n) query time.
Монотонды бөліністер
Монотонды (вертикальді) тізбек – жол бойымен y координатасы ешқашан өспейтін жол. Қарапайым көпбұрыш (вертикальді) монотонды болады, егер ол екі монотонды тізбектен тұрса, ал бірінші және соңғы төбелері ортақ болса. Жазық бөліністің барлық беттерін монотонды ету үшін, оған кейбір қабырғаларды қосуға болады, нәтижесінде монотонды бөлініс пайда болады. Бұл процесс бөлініске ешқандай төбе қоспайды (демек, көлемі O(n) болып қалады) және жазықтықтан өткізу арқылы O(n log n) уақытында орындалуы мүмкін (көпбұрышты үшбұрыштауды қолдану арқылы сызықтық уақытта да орындауға болады). Сондықтан, осы бөлімде көрсетілгендей, деректер құрылымын монотонды бөліністермен шектеуде жалпылық жоғалтылмайды. Тақтаның ыдырауының кемшілігі – тік сызықтар ыдырауда қосымша сегменттер жасайды, бұл O(n) сақтау кеңістігіне қол жеткізуді қиындатады. Герберт Эдельсбруннер, Леонидас Дж. Гибас және Хорхе Столфи монотонды бөліністе тек қабырғаларды пайдаланатын оптималды деректер құрылымын тапты. Идея – тік сызықтарды пайдаланудың орнына тік монотонды тізбектерді пайдалану. Бұл жалпы идеяны нақты тиімді деректер құрылымына айналдыру оңай емес. Біріншіден, бөліністі шамамен бірдей өлшемдегі екі бөлікке бөлетін монотонды тізбекті есептеуге білуіміз керек. Екіншіден, кейбір қабырғалар бірнеше монотонды тізбектерге кіре алатындықтан, сақтау кеңістігі O(n) болатынын қамтамасыз етуге көңіл болуы керек. Үшіншіден, нүкте монотонды бөліністің сол немесе оң жағында екенін тексеру, егер наив түрде орындалса, O(n) уақыт алады. Алғашқы екі мәселені қалай шешу керектігі туралы толық мәліметтер осы мақалада қарастырылмайды. Біз үшінші мәселені қалай шешуге болатынын қысқаша айтамыз. Екілік іздеуді пайдаланып, нүкте монотонды тізбектің сол немесе оң жағында екенін O(log n) уақытында тексеруге болады. Нүкте орнын анықтау үшін O(log n) тізбектер арқылы ішкі екілік іздеуді орындау қажет болғандықтан, сұраныс уақыты O(log² n) болады. O(log n) сұраныс уақытына жету үшін бөлшекті каскадтауды қолдану керек, әртүрлі монотонды тізбектердің қабырғалары арасында көрсеткіштерді сақтау керек.
A (vertical) monotone chain is a path such that the y coordinate never increases along the path. A simple polygon is (vertical) monotone if it is formed by two monotone chains, with the first and last vertices in common. It is possible to add some edges to a planar subdivision, in order to make all faces monotone, obtaining what is called a monotone subdivision. This process does not add any vertices to the subdivision (therefore, the size remains O(n)), and can be performed in O(n log n) time by plane sweep (it can also be performed in linear time, using polygon triangulation). Therefore, there is no loss of generality, if we restrict our data structure to the case of monotone subdivisions, as we do in this section. The weakness of the slab decomposition is that the vertical lines create additional segments in the decomposition, making it difficult to achieve O(n) storage space. Herbert Edelsbrunner, Leonidas J. Guibas, and Jorge Stolfi discovered an optimal data structure that only uses the edges in a monotone subdivision. The idea is to use vertical monotone chains, instead of using vertical lines to partition the subdivision. Converting this general idea to an actual efficient data structure is not a simple task. First, we need to be able to compute a monotone chain that divides the subdivision into two halves of similar sizes. Second, since some edges may be contained in several monotone chains, we need to be careful to guarantee that the storage space is O(n). Third, testing whether a point is on the left or the right side of a monotone subdivision takes O(n) time if performed naïvely. Details on how to solve the first two issues are beyond the scope of this article. We briefly mention how to address the third issue. Using binary search, we can test whether a point is to the left or right of a monotone chain in O(log n) time. As we need to perform another nested binary search through O(log n) chains to actually determine the point location, the query time is O(log² n). To achieve O(log n) query time, we need to use fractional cascading, keeping pointers between the edges of different monotone chains.
Үшбұрышты өңдеу
m төбесі бар көпбұрыш m–2 үшбұрышқа бөлінеді. Бұл үшбұрыштан басталатын индукция арқылы көрсетілуі мүмкін. Көпбұрышты тиімді үшбұрыштау үшін көптеген алгоритмдер бар, ең жылдамдары ең нашар жағдайда O(n) уақытты қажет етеді. Сондықтан, біз әрбір көпбұрышты үшбұрыштарға бөліп, дерек құрылымымызды тек үшбұрыштардан ғана тұратын бөліністермен шектей аламыз. Киркпатрик O(n) сақтау кеңістігі және O(log n) сұраныс уақыты бар үшбұрышты бөліністердегі нүктені табуға арналған дерек құрылымын ұсынады. Басты идея – үшбұрыштардың иерархиясын құру. Сұрауды орындау үшін біз сұраныс нүктесін қамтитын жоғарғы деңгейдегі үшбұрышты табамыз. Жоғарғы деңгейдегі үшбұрыштардың саны тұрақтымен шектелгендіктен, бұл операция O(1) уақытында орындалуы мүмкін. Әрбір үшбұрыш иерархияның келесі деңгейіндегі қиылысатын үшбұрыштарға сілтемелерге ие, және сілтемелердің саны да тұрақтымен шектелген. Біз сұраныс нүктесін қамтитын үшбұрышты деңгей бойынша анықтап, сұрауды жалғастырамыз. Дерек құрылымы кері тәртіппен, яғни төменнен жоғарыға қарай салынады. Біз үшбұрышты бөліністен бастаймыз және алынып тасталатын төбелердің тәуелсіз жиынтығын таңдаймыз. Төбелерді алып тастағаннан кейін, біз бөліністі қайтадан үшбұрыштауды жүзеге асырамыз. Бөлініс үшбұрыштардан тұрғандықтан, ашкөз алгоритм төбелердің тұрақты үлесін қамтитын тәуелсіз жиынтықты таба алады. Сондықтан, алып тастау қадамдарының саны O(log n) құрайды.
A polygon with m vertices can be partitioned into m–2 triangles. Which can be shown by induction starting from a triangle. There are numerous algorithms to triangulate a polygon efficiently, the fastest having O(n) worst case time. Therefore, we can decompose each polygon of our subdivision in triangles, and restrict our data structure to the case of subdivisions formed exclusively by triangles. Kirkpatrick gives a data structure for point location in triangulated subdivisions with O(n) storage space and O(log n) query time. The general idea is to build a hierarchy of triangles. To perform a query, we start by finding the top level triangle that contains the query point. Since the number of top level triangles is bounded by a constant, this operation can be performed in O(1) time. Each triangle has pointers to the triangles it intersects in the next level of the hierarchy, and the number of pointers is also bounded by a constant. We proceed with the query by finding which triangle contains the query point level by level. The data structure is built in the opposite order, that is, bottom up. We start with the triangulated subdivision, and choose an independent set of vertices to be removed. After removing the vertices, we retriangulate the subdivision. Because the subdivision is formed by triangles, a greedy algorithm can find an independent set that contains a constant fraction of the vertices. Therefore, the number of removal steps is O(log n).
Трапециялы ыдырау
Бұл мәселеге кездейсоқ тәсіл трапециялық ыдырау немесе трапециялық картаға негізделген. Трапециялық ыдырау бастапқы бөліністегі әр төбеден жоғары және төмен қарай тік сәулелер жіберу арқылы алынады. Сәулелер жиекке соғысқанда тоқтап, бөліністе жаңа жиекті құрайды. Осылайша, біз O(n) жиектері мен төбелері бар плиталық ыдыраудың ішкі жиынтығын аламыз, себебі бастапқы бөліністегі әр төбе үшін біз тек екі жаңа төбе қосамыз және жиектер санын төртке арттырамыз. Трапециялық ыдырау бастапқы бөліністен сегменттерді біріктіру арқылы, кездейсоқ ретпен жасалуы мүмкін. Бастапқыда (ең бірде-бір сегмент қосылмас бұрын) трапециялық ыдырау бір трапециядан тұрады, ол бөліністің шектеу тіктөртбұрышы. Әр келесі қадамда, келесі сызық сегментінің бір ұшын ағымдағы трапециялық ыдырау ішінде табу үшін нүкте орналасу сұранысы қолданылады, содан кейін нәтижесіндегі трапециядан сол сегментті қамтитын көрші трапецияларға өтіледі, оларды бөліп, қайта біріктіріп, жақсартылған ыдырау құралады. Артқа қарай талдау, осы типтегі кездейсоқ инкрементті геометриялық алгоритмдерде жиі қолданылатын талдау түрі, әрбір енгізу үшін жасалатын трапециялардың күтілетін санын тұрақтымен шектейтінін көрсетеді, сондықтан осы алгоритмнің нүкте орналасудан басқа қадамдарының жалпы саны сызықтық. Осы алгоритм шеңберіндегі ағымдағы бөліністегі нүктелерді табу, алгоритм соңында соңғы трапециялық ыдырауда нүкте орналасу сұраныстары үшін қолданылатын бірдей құрылымды пайдалана отырып жүзеге асырылуы мүмкін. Бұл нүкте орналасу деректерінің құрылымы бағытталған ациклді граф түрінде болады, онда төбелер тазарту процесінің белгілі бір кезеңінде болған трапецияларды құрайды, ал бағытталған жиектер енді тазартуда жоқ трапецияларды оларды алмастырған трапециялармен байланыстырады. Нүкте орналасу сұранысы осы граф бойынша жолмен жүзеге асырылады, бастапқы трапециядан бастап, әр қадамда сұраныс нүктесін қамтитын алмастыру трапециясын таңдап, алмастырылмаған трапецияға жеткенге дейін. Кез келген сұраныс нүктесінен басталатын осы графтың іздеу тереңдігі күтілуде O(log n) құрайды. Деректер құрылымына қажет орын осы тазарту процесінде құрылған трапециялардың санына пропорционалды, бұл күтілуде O(n).
A randomized approach to this problem is based on trapezoidal decomposition, or trapezoidal map. A trapezoidal decomposition is obtained by shooting vertical bullets going both up and down from each vertex in the original subdivision. The bullets stop when they hit an edge, and form a new edge in the subdivision. This way, we obtain a subset of the slab decomposition, with only O(n) edges and vertices, since for each vertex in the original subdivision we only add two new vertices and increase the number of edges by four. A trapezoidal decomposition can be constructed by adding the segments from the original subdivision, one by one, in a random order. Initially (before no segments have been added) the trapezoidal decomposition consists of a single trapezoid, the bounding box of the subdivision. Each subsequent step uses a point location query to locate one endpoint of the next line segment, within the current trapezoidal decomposition, and then walks from the resulting trapezoid to neighboring trapezoids containing the same segment, subdividing and recombining them to form the refined decomposition. Backwards analysis, a form of analysis commonly used for this sort of randomized incremental geometry algorithm, shows that the expected number of trapezoids created for each insertion is bounded by a constant, and therefore that the total number of steps of this algorithm, outside of the point locations, is linear. The point locations in the current subdivision, performed within this algorithm, may be done using the same structure that, at the end of the algorithm, can be used for point location queries in the final trapezoidal decomposition. This point location data structure takes the form of a directed acyclic graph, where the vertices are the trapezoids that existed at some point in the refinement, and directed edges connect each trapezoid that is no longer in the refinement to the trapezoids that replaced it. A point location query is performed by following a path in this graph, starting from the initial trapezoid, and at each step choosing the replacement trapezoid that contains the query point, until reaching a trapezoid that has not been replaced. The expected depth of a search in this digraph, starting from any query point, is O(log n). The space for the data structure is proportional to the number of trapezoids created throughout this refinement process, which in expectation is O(n).
Жоғары өлшемдер
2 өлшемнен үлкен өлшемдер үшін сызықтық кеңістік және логарифмдік сұраныс уақыты бар жалпы нүкте орналасу деректері құрылымы белгілі емес. Сондықтан, біз сұраныс уақытын немесе сақтау кеңістігін құрбан етуіміз керек, немесе өзімізді кем жалпы түрдегі бөлініске шектеуіміз керек. Үш өлшемді кеңістікте O(n log n) кеңістікті пайдалана отырып, нүкте орналасу сұрақтарына O(log² n) уақыт ішінде жауап беруге болады. Жалпы идея – әрбір бөлініс нүктесін қамтитын n параллель жазықтықпен бөліністің қиылысына сәйкес келетін бірнеше жазықтық нүкте орналасу деректері құрылымдарын сақтау. Бұл идеяны тікелей қолдану сақтау кеңістігін O(n²) дейін арттырады. Слайдтық ыдыраудағыдай, бірізді деректер құрылымдарының ұқсастығын пайдалану арқылы сақтау кеңістігін O(n log n) дейін азайтуға болады, бірақ сұраныс уақыты O(log² n) дейін ұзарады. d өлшемді кеңістікте нүкте орналасу мәселесін беттерді рекурсивті түрде (d-1) өлшемді кеңістікке проекциялау арқылы шешуге болады. Сұраныс уақыты O(log n) болса, сақтау кеңістігі өте үлкен болуы мүмкін. d өлшемді деректер құрылымдарының жоғары күрделілігі арнайы бөліністерді зерттеуге әкелді. Мұның маңызды мысалы – гипержазықтықтардың орналасуы. n гипержазықтықтың орналасуы O(nd) ұяшықты анықтайды, бірақ нүкте орналасуын Chazelle-дің иерархиялық кесінділерін пайдалану арқылы O(log n) уақыт ішінде O(nd) кеңістікте орындауға болады. Бөліністердің тағы бір ерекше түрі – тікбұрышты (немесе ортогоналды) бөлініс. Тікбұрышты бөліністе барлық қабырғалары d ортогоналды осьтерінің біріне параллель болады. Бұл жағдайда нүкте орналасуына O(logᵈ⁻¹ n) уақыт ішінде O(n) кеңістікте жауап беруге болады.
There are no known general point location data structures with linear space and logarithmic query time for dimensions greater than 2. Therefore, we need to sacrifice either query time, or storage space, or restrict ourselves to some less general type of subdivision. In three dimensional space, it is possible to answer point location queries in O(log² n) using O(n log n) space. The general idea is to maintain several planar point location data structures, corresponding to the intersection of the subdivision with n parallel planes that contain each subdivision vertex. A naive use of this idea would increase the storage space to O(n²). In the same fashion as in the slab decomposition, the similarity between consecutive data structures can be exploited in order to reduce the storage space to O(n log n), but the query time increases to O(log² n). In d dimensional space, point location can be solved by recursively projecting the faces into a (d 1) dimensional space. While the query time is O(log n), the storage space can be as high as The high complexity of the d dimensional data structures led to the study of special types of subdivision. One important example is the case of arrangements of hyperplanes. An arrangement of n hyperplanes defines O(nd) cells, but point location can be performed in O(log n) time with O(nd) space by using Chazelle's hierarchical cuttings. Another special type of subdivision is called rectilinear (or orthogonal) subdivision. In a rectilinear subdivision, all edges are parallel to one of the d orthogonal axis. In this case, point location can be answered in O(logd 1 n) time with O(n) space.