Publication detail

Approximation of volumes of Voronoi cells using parallel solution

MAŠEK, J. VOŘECHOVSKÝ, M.

Original Title

Approximation of volumes of Voronoi cells using parallel solution

Type

conference paper

Language

English

Original Abstract

The presented paper concerns an algorithm for fast approximation of volumes of hyper-dimensional Voronoi cells. One of many utilizations of known values of volumes of Voronoi cells is weighing of integration points in a Monte Carlo type integration. The discussed algorithm does not require the construction of the corresponding Voronoi diagram which typically is a highly computationally demanding task, especially when performed in higher dimensions. For the purposes of approximation of Voronoi cell volumes, only the mutual distances of points in sample are evaluated. The parallelized solution using GPU’s shared memory is described, emphasizing maximal efficiency of data transfer. The optimization of memory throughput is shown to be crucial for the problem at hand. The solution complexity is discussed as well as the convergence to the exact solution is provided.

Keywords

Voronoi cell volumes, CUDA, shared memory

Authors

MAŠEK, J.; VOŘECHOVSKÝ, M.

Released

25. 1. 2018

Publisher

Fakulta stavební, VUT v Brně

Location

Brno

ISBN

978-80-86433-69-1

Book

Proceedings of JUNIORSTAV 2018

Pages from

597

Pages to

601

Pages count

5

BibTex

@inproceedings{BUT145354,
  author="Jan {Mašek} and Miroslav {Vořechovský}",
  title="Approximation of volumes of Voronoi cells using parallel solution",
  booktitle="Proceedings of JUNIORSTAV 2018",
  year="2018",
  pages="597--601",
  publisher="Fakulta stavební, VUT v Brně",
  address="Brno",
  isbn="978-80-86433-69-1"
}