Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка 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.