Přejít k obsahu


Hybrid algorithm for delection of a point regular and Delaunay triangulation

Citace: [] ZEMEK, M., KOLINGEROVÁ, I. Hybrid algorithm for delection of a point regular and Delaunay triangulation. In Spring Conference on Computer Graphics SCCG 2009. Bratislava: Comenius University, 2009. s. 149-156. ISBN: 978-80-223-2644-5
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Hybrid algorithm for delection of a point regular and Delaunay triangulation
Rok vydání: 2009
Místo konání: Bratislava
Název zdroje: Comenius University
Autoři: Ing. Michal Zemek , Doc. Dr. Ing. Ivana Kolingerová
Abstrakt CZ: Tento článek popisuje randomizovaný algoritmus, který umožňuje sekvencí flipů vyjmout bod v tří-dimenzionální regulární a Delaunayově triangulaci. Všechny obdobné předchozí algoritmy testují regularitu každého nového tetrahedronu globálně, tj. vůči všem sousedním bodům odebíraného bodu. Navrhovaný hybridní algoritmus používá kombinaci lokálních a globálních testů regularity. Nejprve se pokusí odebrat bod náhodnou sekvencí flipů stěn, které splňují určitou lokální podmínku. Tento přístup vede vždy k cíli, v nejhorším případě ovšem může doba běhu růst nade všechny meze. Proto tento přístup kombinujeme s globálními testy regularity ? pokud se bod nepodaří vyjmout určitým počtem flipů, lokální test regularity je nahrazen globálním testem. V důsledku tak navrhovaný algoritmus potřebuje méně testů regularity než předchozí algoritmy.
Abstrakt EN: In this paper, we propose a randomized algorithm that allows to delete a point in three-dimensional regular or Delaunay triangulation by a sequence of flips. All the previous algorithms check regularity of each new tetrahedron globally, i.e. with respect to all vertices of tetrahedra incident to the point, which is being deleted. In contrast, the proposed hybrid algorithm uses a combination of local and global regularity tests. First, the proposed algorithm tries to delete a point by a randomized sequence of flips of faces satisfying a certain local condition. This simple approach will always delete the point successfully, but theoretically in an unbounded time in the worst case. Therefore we combine it with the global regularity tests - if the point is not deleted after a certain number of flips, the proposed algorithm replaces the local regularity test by the global regularity test. In consequence, the proposed algorithm needs less tests of regularity in average than the previous algorithms.
Klíčová slova

Zpět

Patička