| Název: | Application of concatenable queue for parallel computational geometry algorithms |
| Autoři: | Tereshchenko, Vasyl Chudakov, Semen |
| Citace zdrojového dokumentu: | WSCG 2020: full papers proceedings: 28th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, p. 56-62. |
| Datum vydání: | 2020 |
| Nakladatel: | Václav Skala - UNION Agency |
| Typ dokumentu: | conferenceObject konferenční příspěvek |
| URI: | http://wscg.zcu.cz/WSCG2020/2020-CSRN-3001.pdf http://hdl.handle.net/11025/38451 |
| ISBN: | 978-80-86943-35-0 |
| ISSN: | 2464–4617 (print) 2464–4625 (CD-ROM) |
| Klíčová slova: | sjednocená struktura dat;simulační problém;sada vzájemně propojených problémů;jednotné algoritmické prostředí;spojitelná fronta |
| Klíčová slova v dalším jazyce: | unified data structure;simulation problem;interrelated problems set;unified algorithmic environment;concatenable queue |
| Abstrakt v dalším jazyce: | This paper is devoted to the development of an algorithmic model that solves a set of interrelated computational geometry problems efficiently. To do this, an algorithmic environment with a unified data structure is created, which allows to implement complex use cases efficiently with respect to required computational resources. We build the environment based on the “divide and conquer” strategy. Once a convex hull is a key to a set of computational geometry problems, we offer a concatenable queue data structure to maintain it. The data structure is in the form of a modified balanced binary tree. This allows us to perform operations needed in algorithms for a set of problems in O(log2 n) time. Furthermore we offer a way to execute the algorithms both sequentially and in parallel. In the future the algorithmic environment can be improved to support other computational models with similar properties for solving problems. As an example, the Voronoi diagram or the Delaunay triangulation can be considered. |
| Práva: | © Václav Skala - UNION Agency |
| Vyskytuje se v kolekcích: | WSCG 2020: Full Papers Proceedings |
Soubory připojené k záznamu:
| Soubor | Popis | Velikost | Formát | |
|---|---|---|---|---|
| F05.pdf | Plný text | 748,42 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/38451Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.