| VRSTA GRADIVA | analitična raven (sestavni del), tekstovno gradivo, tiskano, 1.03 - kratki znanstveni prispevek |
| DRŽAVA IZIDA | Slovenija |
| LETO IZIDA | 2001 |
| JEZIK BESEDILA/IZVIRNIKA | angleški |
| PISAVA | latinica |
| AVTOR | Žalik, Borut - avtor |
| ODGOVORNOST | Kolingerová, Ivana - avtor |
| NASLOV | ǂAn ǂincremental construction algorithm for Delaunay triangulation based on two-level uniform subdivision |
| V PUBLIKACIJI | Contributions to geometric modelling and multimedia. - ISSN 1580-5689. - ǂVol. ǂ1, ǂno. ǂ5 (2001), str. 1-32. |
| KRATKA VSEBINA | The report introduces a new algorithm for constructing Delaunay triangulation in 2D. It belongs to the class of incremental construction algorithms. The bottleneck of these algorithms is the search for a triangle into which a point, which is tried to be integrated into triangulation, falls. We transform this problem to the closest point problem. The search for the closest point is sped-up by two-level uniform subdivision. In this way, the most important drawback of the unform subdivision, i.e., it does not give good results when geometric data are distributed non-uniformly, has been reduced. The algorithm has been compared to two other algorithms programmed by the authors of the paper: Guibas, Knuth, and Sharir's algorithm, and Fang and Piegl's algorithm using uniformly distributed data. The real data sets from geographical database have been employed. The presented algorithm is fasterthan referenced algorithms. It is also not memory demanding. Beside these, it will be shown that features of the algorithm do not getting worse when real data (non-uniformly distributed) are used. The worst case time complexity is O(▫$n[sub]2$▫), but this case is not expected in real situations. The time complexity obtained by measuring spent CPU time is much better: O(▫$n[sup]1,1$▫), where n is the number of points being triangulated. // V poročilu opišemo nov algoritem za konstrukcijo ravninskeDelaunayeve triangulacije. Algoritem spada v skupino inkrementalnih konstrukcijskih algoritmov. Ozko grlo tega tipa triangulacijskih algoritmovje iskanje, v kateri trikotnik pade trenutno vstavljena točka. Ta problem smo pretvorili v iskanje najbližje točke, ki smo ga realizirali z dvonivojsko delitvijo. Na ta način smo zmanjšali težavo, ki nastane pri neenakomerni porazdelitvi vhodnih točk. Predlagan algoritem primerjamo z algoritmom Guibasa, Knutha in Sharirja ter algoritmom Fanga in Piegla. uporabimo enakomerno delitev točk in delitev iz okolja GIS. Predlagan algoritem je hitrejši od refrenčnih lgoritmov. Ocena najslabše časovne zahtevnosti je O(▫$n[na]2$▫), vendar je pričakovana časovna zahtevnost mnogo boljša. Z meritvami časa CPE pokažemo, da je le-ta O(▫$n[na]1,1$▫). |
| OPOMBE | Bibliografija: str. 31-32 |
| OSTALI NASLOVI | Inkrementalni konstrukcijski algoritem ravninske Delaunayeve triangulacije z dvonivojsko enakomerno delitvijo ravnine |
| PREDMETNE OZNAKE | // računalniška geometrija // Delaunayeva triangulacija // GIS |
| UDK | 004.9:51 |