Hybrid algorithm for delection of a point regular and Delaunay triangulation
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F09%3A00502516" target="_blank" >RIV/49777513:23520/09:00502516 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Hybrid algorithm for delection of a point regular and Delaunay triangulation
Popis výsledku v původním jazyce
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 respectto 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 alg
Název v anglickém jazyce
Hybrid algorithm for delection of a point regular and Delaunay triangulation
Popis výsledku anglicky
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 respectto 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 alg
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
JC - Počítačový hardware a software
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA201%2F09%2F0097" target="_blank" >GA201/09/0097: Triangularizované modely pro haptiku a virtuální realitu</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2009
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Spring Conference on Computer Graphics SCCG 2009
ISBN
978-80-223-2644-5
ISSN
—
e-ISSN
—
Počet stran výsledku
8
Strana od-do
—
Název nakladatele
Comenius University
Místo vydání
Bratislava
Místo konání akce
Budmerice
Datum konání akce
25. 4. 2009
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—