Identyfikatory
Warianty tytułu
Algorytm szybkiej lokalizacji punktu na siatkach trójkątnych
Języki publikacji
Abstrakty
This paper is a study of application of persistent data structures to the planar and, in part, also spatial point location. In practice, a simplified method of building persistent red- black binary search tree is considered. It corresponds to the structure of a two-dimensional cell complex. Subsequent use of the structure for searching a certain point in space is shown. The computational mesh consists of triangular (in two dimensions) or tetrahedral (in three dimensions) cells. This fact allows significant simplifications to both implementation of the total order necessary to build the search tree as well as construction of the red-black binary search tree itself. The performance of the algorithm is verified for various meshes (consisting of up to 1846197 cells). Finally, certain further directions of the research are shown.
Artykuł przedstawia wyniki badań nad zastosowaniem dynamicznych struktur danych (ang. persistent data structures) do planarnej i przestrzennej lokalizacji punktu w siatce obliczeniowej, z wykorzystaniem czerwono-czarnych drzew poszukiwań binarnych, które odpowiadają strukturze dwuwymiarowego kompleksu komórek. Rozważana siatka obliczeniowa składa się z komórek trójkątnych (w dwóch wymiarach) albo czworościennych (w trzech wymiarach). Ten fakt zezwala na znaczne uproszczenia realizacja totalnego porządku niezbędnego do budowy drzewa poszukiwań, jak również konstrukcji samego czerwono-czarnego drzewa poszukiwań binarnych. Wydajność algorytmu jest sprawdzone dla różnych siatek obliczeniowych (zawierających od 1239 do 1846197 komórek). Wyniki eksperymentu numerycznego potwierdzają logarytmiczny czas lokalizacji i liniowo rosnące zużycie pamięci przy wzroście rozmiaru siatki.
Czasopismo
Rocznik
Tom
Strony
315--324
Opis fizyczny
Bibliogr. 4 poz., rys.
Twórcy
autor
autor
- Warsaw University of Technology, Institute of Aeronautics and Applied Mechanics, Poland, wichulski@meil.pw.edu.pl
Bibliografia
- 1. de Berg M., van Kreveld M., Overmars M., Schwarzkopf O., 1997, Computational Geometry: Algorithms and Applications, Springer-Verlag
- 2. Cormen T.H., Leiserson C.E., Rivest R.L., 1990, Introduction to Algorithms, The MIT Press
- 3. Discroll J.R., Sarnak N., Sleator D.D., Tarjan R.E., 1989, Making data structures persistent, J. Comput. Syst. Sci., 38, 1, 267-280
- 4. Preparata F.P., Tamassia R., 1992, Efficient point location in a convex spatial cell-complex, SIAM J. Comput., 21, 2, 267-280
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BWM4-0007-0036