Publication detail
Geometric Data Structures and Their Selected Applications
ŠEDA, M.
Czech title
Geometrické datové struktury a jejich aplikace
English title
Geometric Data Structures and Their Selected Applications
Type
conference paper
Language
en
Original abstract
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 fundamentally 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 straight connections between pairs of points (minimum spanning tree) or allowing the addition of auxiliary points to the set to obtain shorter spanning networks (minimum Steiner tree).
Czech abstract
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. 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ůzný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ých bodů tak, aby byla získána síť o kratší celkové délce (minimální Steinerův strom).
English abstract
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 fundamentally 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 straight connections between pairs of points (minimum spanning tree) or allowing the addition of auxiliary points to the set to obtain shorter spanning networks (minimum Steiner tree).
Keywords in Czech
Voronoiův diagram, Delaunayho triangulace, graf viditelnosti
Keywords in English
Voronoi diagram, Delaunay triangulation, visibility graph
RIV year
2006
Released
24.02.2006
Publisher
COMPUTICA
Location
Praha
ISBN
975-00803-0-0
Book
Computer Science
Pages count
6
BIBTEX
@inproceedings{BUT18008,
author="Miloš {Šeda},
title="Geometric Data Structures and Their Selected Applications",
booktitle="Computer Science",
year="2006",
month="February",
publisher="COMPUTICA",
address="Praha",
isbn="975-00803-0-0"
}