A study on Voronoi diagrams with two-dimensional obstacles

DOI DOI Web Site Web Site 6 Citations 17 References

Bibliographic Information

Other Title
  • 障害物の配置された平面におけるボロノイ図に関する研究
  • 障害物の配置された平面におけるボロノイ図に関する研究--ドローネ網における最短距離を用いた作図法の提案
  • ショウガイブツ ノ ハイチサレタ ヘイメン ニ オケル ボロノイズ ニ カンスル ケンキュウ ドローネモウ ニ オケル サイタン キョリ オ モチイタ サクズホウ ノ テイアン
  • ドローネ網における最短距離を用いた作図法の提案
  • An approximate construction using the shortest-path distance of a Delaunay network

Search this article

Description

In this paper, we propose a method for constructing Voronoi diagrams with two-dimensional obstacles by a simple and practical computer algorithm, using the shortest-path distance of a Delaunay network of many random vertices, which we termed as rDn. By measuring the shortest-path distance of the rDn for the detour distance, this method provides an approximate solution for the Voronoi diagrams with obstacles. We verify the isotropy and stability of the ratio of the shortest-path distance of the rDn and the Euclid distance by a computer experiment. We then show the reliability of the approximate solution by comparing with the exact solution in a simple case, and the effectiveness of this method by solving a sample problem with free shaped obstacles.

Journal

Citations (6)*help

See more

References(17)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top