Fast Display of Voronoi Diagrams over Planes and Spheres using Graphics Hardwares

DOI Web Site 1 Citations 12 References
  • Yamamoto Osami
    Department of Information System Engineering, Faculty of Engineering, Aomori University

Bibliographic Information

Other Title
  • グラフィックスハードウェアを用いた平面および球面上のボロノイ図の描画について
  • グラフィックスハードウェア オ モチイタ ヘイメン オヨビ キュウメン ジョウ ノ ボロノイズ ノ ビョウガ ニ ツイテ

Search this article

Description

We give a fast algorithm to display Voronoi diagrams over planes and spheres using graphics hardwares. Hoff et al. [4] shows that graphics hardwares that are designed to display three dimensional objects over computer screens can be utilized to make images of 2-dimensional Voronoi diagrams. In this paper we analyze the discrepancy of the images of weighted Voronoi diagrams generated by graphics hardware. Moreover, we show a theoretically faster algorithm for Voronoi diagrams over the Euclidean plane. The refined version of the algorithm is about 4 times faster than the original algorithm by [4]. But it has some accuracy problems. In the latter part of this paper, we show an algorithm for Voronoi diagrams over a sphere and analyze the discrepancy of the images.

Journal

Citations (1)*help

See more

References(12)*help

See more

Details 詳細情報について

Report a problem

Back to top