Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік геометрияда және роботтардың қозғалысын жоспарлауда көріну графигі — Евклид жазықтығындағы нүктелер мен кедергілер жиынтығының бір-бірін көре алатын орналасуларының графигі. Графиктегі әрбір түйін нүктенің орнын көрсетеді, ал әрбір қабырға олардың арасындағы көрінетін байланысты білдіреді. Яғни, егер екі орнды қосатын түзу кесіндісі ешқандай кедергіден өспесе, графикте олардың арасына қабырға салынады. Егер орналысқан нүктелер бір түзу бойында болса, оны реттелген тізбек ретінде қарастыруға болады. Сондықтан көріну графиктері уақыт қатарларын талдау саласына да қолданылады.
In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them. That is, if the line segment connecting two locations does not pass through any obstacle, an edge is drawn between them in the graph. When the set of locations lies in a line, this can be understood as an ordered series. Visibility graphs have therefore been extended to the realm of time series analysis.
Қолданбалар
Көріну графиктерін жазықтықтағы көпбұрышты кедергілер жиынтығы арасында Эвклид ең қысқа жолдарын табу үшін пайдалануға болады: екі кедергі арасындағы ең қысқа жол кедергілердің төбелерінде бұрылу мүмкін болғандықтан, түзу сызық сегменттерін ұстанады, сондықтан Эвклид ең қысқа жолы – бастапқы және мақсаттық нүктелерді және кедергілердің төбелерін түйіндер етіп алатын көріну графигіндегі ең қысқа жол болып табылады. Сондықтан, Эвклид ең қысқа жол мәселесі екі қарапайым кіші мәселеге бөлінеді: көріну графигін құру және Дикстра алгоритмі сияқты ең қысқа жол алгоритмін графқа қолдану. Кедергілерге қарағанда айтарлықтай үлкен көлемге ие роботтың қозғалысын жоспарлау үшін, роботтың көлемін ескеру үшін кедергілерді кеңейткеннен кейін ұқсас тәсіл қолданылуы мүмкін. Бұл нақты жағдай уақыт қатарлары, динамикалық жүйелер және граф теориясы арасында байланыс орнатады.
Visibility graphs may be used to find Euclidean shortest paths among a set of polygonal obstacles in the plane: the shortest path between two obstacles follows straight line segments except at the vertices of the obstacles, where it may turn, so the Euclidean shortest path is the shortest path in a visibility graph that has as its nodes the start and destination points and the vertices of the obstacles. Therefore, the Euclidean shortest path problem may be decomposed into two simpler subproblems: constructing the visibility graph, and applying a shortest path algorithm such as Dijkstra's algorithm to the graph. For planning the motion of a robot that has non negligible size compared to the obstacles, a similar approach may be used after expanding the obstacles to compensate for the size of the robot. This particular case builds a bridge between time series, dynamical systems and graph theory.
Қасиеттері
Қарапайым көпбұрыштың көріну графигінде көпбұрыштың төбелері нүктелер ретінде, ал көпбұрыш сырты жалғыз кедергі ретінде қарастырылады. Қарапайым көпбұрыштардың көріну графтары Гамильтон графтары болуы тиіс: көпбұрыш шекарасы көріну графигінде Гамильтон циклын құрайды. Барлық көріну графиктері де қарапайым көпбұрыш тудырмайды. Дегенмен, қарапайым көпбұрыштардың көріну графиктерінің тиімді алгоритмдік сипаттамасы әлі белгілі емес. Бұл графиктер көптеген жақсы құрылымдалған графиктер отбасыларына жатпайды: олар толық графиктер, шеңберлік графиктер немесе хордалық графиктер болмауы мүмкін. Алайда, қарапайым көпбұрыштардың көріну графтары cop win графтары болып табылады – бұл құбылысқа ерекшелік жасайды.
The visibility graph of a simple polygon has the polygon's vertices as its point locations, and the exterior of the polygon as the only obstacle. Visibility graphs of simple polygons must be Hamiltonian graphs: the boundary of the polygon forms a Hamiltonian cycle in the visibility graph. It is known that not all visibility graphs induce a simple polygon. However, an efficient algorithmic characterization of the visibility graphs of simple polygons remains unknown. These graphs do not fall into many known families of well structured graphs: they might not be perfect graphs, circle graphs, or chordal graphs. An exception to this phenomenon is that the visibility graphs of simple polygons are cop win graphs.
Қатысушы мәселелер
Көркемсурет галереясы мәселесі – бұл барлық басқа кедергі емес нүктелер осы жиынтықтан көрінетін нүктелердің минималды жиынтығын табу мәселесі. Көркемсурет галереясы мәселесінің кейбір түрлері көріну графигінде үстемдік жиынтықты табу түрінде қарастырылуы мүмкін. Полигон немесе қисықтар жүйесінің битангенттері – оларға жанасқан, бірақ жанасу нүктелерінде оларды кесіп өтпейтін түзулер. Полигон жиынтығының битангенттері полигонның төбелерін түйіндер ретінде және полигондардың өзін кедергілер ретінде пайдаланатын көріну графигінің ішкі жиынын құрайды. Евклид ең қысқа жолы мәселесіне көріну графигі арқылы қол жеткізуді барлық көріну жиектерін пайдаланудың орнына битангенттерден граф құру арқылы жылдамдатуға болады, себебі Евклид ең қысқа жолы кедергінің шекарасына тек битангент бойымен ғана кіре алады немесе шыға алады.
The art gallery problem is the problem of finding a small set of points such that all other non obstacle points are visible from this set. Certain forms of the art gallery problem may be interpreted as finding a dominating set in a visibility graph. The bitangents of a system of polygons or curves are lines that touch two of them without penetrating them at their points of contact. The bitangents of a set of polygons form a subset of the visibility graph that has the polygon's vertices as its nodes and the polygons themselves as the obstacles. The visibility graph approach to the Euclidean shortest path problem may be sped up by forming a graph from the bitangents instead of using all visibility edges, since a Euclidean shortest path may only enter or leave the boundary of an obstacle along a bitangent.