Approximation of Voronoï cell attributes using parallel solution

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26110%2F19%3APU131818" target="_blank" >RIV/00216305:26110/19:PU131818 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.advengsoft.2019.03.012" target="_blank" >http://dx.doi.org/10.1016/j.advengsoft.2019.03.012</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.advengsoft.2019.03.012" target="_blank" >10.1016/j.advengsoft.2019.03.012</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Approximation of Voronoï cell attributes using parallel solution

Popis výsledku v původním jazyce

This paper concerns an algorithm for fast parallel approximation of selected attributes of hyper-dimensional Voronoï cells in a unit hypercube. The presented algorithm does not require the construction of a corresponding Voronoï diagram (usually by employing the Quick Hull algorithm) which typically is a highly computationally demanding task, especially when performed in higher dimensions. The algorithm is suitable for both the clipped and periodic variants of Voronoï tessellation and provides a significant speedup in a convenient range of practical usage. For the purposes of approximation of selected scalar properties of Voronoï cells, only the distances of points in sample are evaluated using an adequately fine underlying orthogonal mesh. The algorithm estimates e.g. the volumes and centroids of Voronoï cells, radii and coordinates of centers of the corresponding Delaunay hyper-circles. The paper also provides quite accurate explicit error estimators for the extracted attributes due to rasterization and thus the user is given a control over the accuracy by selecting an appropriate discretization density. Among numerous fields in which Voronoï diagrams are being utilized, the authors are concerned with optimization of point samples for the Design of Experiments and also with weighting of integration points in Monte Carlo type integration. In these applications, selected scalar topological descriptors of Voronoï diagrams are being repeatedly computed. As the full Voronoï diagram is not of interest but the resulting cell volumes or shape descriptions have to be repeatedly computed, the presented parallel solution seems highly suitable for these applications.

Název v anglickém jazyce

Approximation of Voronoï cell attributes using parallel solution

Popis výsledku anglicky

This paper concerns an algorithm for fast parallel approximation of selected attributes of hyper-dimensional Voronoï cells in a unit hypercube. The presented algorithm does not require the construction of a corresponding Voronoï diagram (usually by employing the Quick Hull algorithm) which typically is a highly computationally demanding task, especially when performed in higher dimensions. The algorithm is suitable for both the clipped and periodic variants of Voronoï tessellation and provides a significant speedup in a convenient range of practical usage. For the purposes of approximation of selected scalar properties of Voronoï cells, only the distances of points in sample are evaluated using an adequately fine underlying orthogonal mesh. The algorithm estimates e.g. the volumes and centroids of Voronoï cells, radii and coordinates of centers of the corresponding Delaunay hyper-circles. The paper also provides quite accurate explicit error estimators for the extracted attributes due to rasterization and thus the user is given a control over the accuracy by selecting an appropriate discretization density. Among numerous fields in which Voronoï diagrams are being utilized, the authors are concerned with optimization of point samples for the Design of Experiments and also with weighting of integration points in Monte Carlo type integration. In these applications, selected scalar topological descriptors of Voronoï diagrams are being repeatedly computed. As the full Voronoï diagram is not of interest but the resulting cell volumes or shape descriptions have to be repeatedly computed, the presented parallel solution seems highly suitable for these applications.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

20101 - Civil engineering

Projekt

<a href="/cs/project/GA16-22230S" target="_blank" >GA16-22230S: Rozvoj pokročilých simulačních metod pro statistickou analýzu konstrukcí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

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ů

Název periodika

ADVANCES IN ENGINEERING SOFTWARE

ISSN

0965-9978

e-ISSN

1873-5339

Svazek periodika

132

Číslo periodika v rámci svazku

132

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

11

Strana od-do

7-17

Kód UT WoS článku

000465171000002

EID výsledku v databázi Scopus

2-s2.0-85063760753