Interfacing graphs

• Autorzy: Kämpke, T.
• Języki publikacji: EN

Abstrakty

EN

Transformations of vertex sequences of regular grid graph into paths of an arbitrary connected graph are facilitated according to various coarsening and approximation operations, including minimum cost alterations and minimum cost re-routings. The sequence transformations are supposed to support issues of man-machine interaction, which implies lack of an ultimate formal design objective. Furthermore, this implies that formal methods and algorithms have to be combined in a pragmatic fashion. For planar graph, the notion of Voronoi regions is modified to graph Voronoi regions which partition the plane according to proximity to verttices and edges simultaneously. The non-planar case is reduced to the planar case by adding all intersection points of vertex connections to the original vertex set and by splitting vertex connections accordingly. This allows grid point sequences to be intermediately transformed to so-called mixed or region sequences which are eventualy transformed to vertex sequences by production rule-like operations. The algorithmic preprocessing burden of partitioning and indexing the euclidean plane via the graph Voronoi regions or approximations thereof is practically larger and typically more complicated than any of the run time computations.

Słowa kluczowe

EN

graph Voronoi region; grid graph; regular expression; touch screen

• Czasopismo: Machine Graphics and Vision
• Rocznik: 2000
• Tom: Vol. 9, No. 4
• Strony: 797-824
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Kämpke, T.

• Forschungsinstitut für anwendungsorientierte Wissensverarbeitung FAW, Helmholtzstr. 16, 89081 Ulm, Germany,