Přejít k obsahu


Reducing the number of points on the convex hull calculation using the polar space subdivision in E2

Citace:
SKALA, V., ŠMOLÍK, M., MAJDIŠOVÁ, Z. Reducing the number of points on the convex hull calculation using the polar space subdivision in E2. In Electronic Proceedings of the 29th Conference on Graphics, Patterns and Images (SIBGRAPI'16). Piscataway: IEEE, 2016. s. 40-47. ISBN: 978-1-5090-3568-7
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Reducing the number of points on the convex hull calculation using the polar space subdivision in E2
Rok vydání: 2016
Místo konání: Piscataway
Název zdroje: IEEE
Autoři: Prof. Ing. Václav Skala CSc. , Ing. Michal Šmolík , Ing. Zuzana Majdišová
Abstrakt CZ: Konvexní obálka bodů v E2 je používána v mnoha aplikacích. Navzdory nízké výpočetní náročnosti O(hlogN) trvá výpočet déle pokud je potřeba zpracovat velké množství dat. Prezentujeme nový algoritmus pro urychlení jakéhokoliv výpočtu planární konvexní obálky. Je založen na polárním dělení prostoru a urychluje výpočet každé planární konvexní obálky 3,7 krát a více. Algoritmus určuje středový bod použitím 10% dat; tento bod je zvolen jako počátek pro polární dělení prostoru. Dělení prostoru umožňuje rychlou a velice efektivní redukci daných bodů, které nemohou být na výsledné konvexní obálce. Navržený algoritmus iterativně aproximuje konvexní obálku, nechává pouze malý počet bodů pro závěrečné zpracování, kreé je provedeno pomocí ?standartního? algoritmu. Neeliminované body jsou zpracovány vybraným standartním algoritmem pro výpočet konvexní obálky. Algoritmus je jednoduchý a lehký na implementaci. Experimenty prokázaly také jeho robustnost.
Abstrakt EN: A convex hull of points in E2 is used in many applications. In spite of low computational complexity O(hlogN) it takes considerable time if large data processing is needed. We present a new algorithm to speed up any planar convex hull calculation. It is based on a polar space subdivision and speed up known convex hull algorithms of 3,7 times and more. The algorithm estimates the central point using 10% of the data; this point is taken as the origin for the polar subdivision. The space subdivision enables a fast and very efficient reduction of the given points, which cannot contribute to the final convex hull. The proposed algorithm iteratively approximates the convex hull, leaving only a small number of points for the final processing, which is performed using a ?standard? algorithm. Non-eliminated points are then processed by a selected standard convex hull algorithm. The algorithm is simple and easy to implement. Experiments proved numerical robustness as well.
Klíčová slova

Zpět

Patička