Přejít k obsahu


Delaunay Triangulation of Mowing Points

Citace: [] VOMÁČKA, T. Delaunay Triangulation of Mowing Points. In CESCG 2008. Vienna: Vienna University of Technology, 2008. s. 67-74. ISBN: 978-3-9502533-0-6
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Delaunay Triangulation of Mowing Points
Rok vydání: 2008
Místo konání: Vienna
Název zdroje: Vienna University of Technology
Autoři: Tomáš Vomáčka
Abstrakt CZ: Delaunayova trianglulace a její duální struktura - Voronoiův diagram jsou datové struktury s mnohými oblastmi využití v oboru výpočetní geometrie. Využití těchto struktur pro množiny pohyblivých bodů je také relativně dobře známou oblastí jejich aplikace a obecné přístupy k této problematice již byly popsány. Tento článek se soustředí na zřídka diskutovaný problém - výpočet času topologických událostí - tj. časů, kdy dochází ke změnám v použité datové struktuře. Náš algoritmus za tímto účelem využívá Sturmových posloupností polynomů, které nám umožňují rychle odhadnout polohu kořenů s možností počítat pouze takové kořeny polynomu, které jsou nezbytné pro správný běh programu.
Abstrakt EN: Delaunay triangulation and its dual structure - Voronoi diagram represent a multi-purpose data structures which are widely used in computational geometry. using these structures for sets of mowing data is also relatively well-known and the general approaches have already been discovered. This paper focuses on the rarely discussed problem - computing of the topological events - i.e., the exact times of structural changes in the data structures. Our algorithm uses the Sturm sequences of polynomials to quickly discover the roots, with a possibility to compute only those roots, which are necessary and will most probably be useful.
Klíčová slova

Zpět

Patička