Geometric Data Structures and Their Selected Applications

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F06%3APU62366" target="_blank" >RIV/00216305:26210/06:PU62366 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Geometric Data Structures and Their Selected Applications

Original language description

Finding the shortest path between two positions is a fundamental problem in transportation, routing, and communications applications. In robot motion planning, the robot should pass around the obstacles touching none of them, i.e. the goal is to find a collision-free path from a starting to a target position. This task has many specific formulations depending on the shape of obstacles, allowable directions of movements, knowledge of the scene, etc. Research of path planning has yielded many fundamentallly different approaches to its solution, mainly based on various decomposition and roadmap methods. In this paper, we show a possible use of visibility graphs in point-to-point motion planning in the Euclidean plane and an alternative approach using Voronoi diagrams that decreases the probability of collisions with obstacles. The second application area, investigated here, is focused on problems of finding minimal networks connecting a set of given points in the plane using either only s

Czech name

Geometrické datové struktury a jejich aplikace

Czech description

Hledání nejkratších cest z určené počáteční do koncové pozice je základní úlohou v dopravě, okružních problémech i komunikačních aplikacích. V úloze plánování pohybu robotu má robot projít z počáteční do koncové pozice ve scéně s překážkami tak, aby nedošlo ke kolizi s některou z překážek. Tato úloha má řadu specifických formulací, které závisí na tvaru překážek, povolenému způsobu pohybu, znalosti scény atd. Výzkum této problematiky přinesl několik odlišných přístupů řešení většinou založených na různných dekompozicích scény a metodách silniční mapy. V příspěvku zkoumáme možné využití grafů viditelnosti v plánování trasy robotu mezi dvěma pozicemi v euklidovské rovině a alternativní přístup využívající Voronoiovy diagramy, které snižují pravděpodobnost kolizí s překážkami. Druhá zde zkoumaná aplikační oblast se zaměřuje na problémy minimalizace sítí spojující množinu daných bodů v rovině využívající pouze přímá spojení mezi dvojicemi bodů (kostra grafu) nebo umožňující přidání pomocný

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2006

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Transactions on Engineering, Computing and Technology

ISSN

1305-5313

e-ISSN

—

Volume of the periodical

11

Issue of the periodical within the volume

2

Country of publishing house

TR - TURKEY

Number of pages

6

Pages from-to

61-66

UT code for WoS article

—

EID of the result in the Scopus database

—