A study on Voronoi diagrams with two-dimensional obstacles

• Imai Kotaro

  the University of Tokyo

• Fujii Akira

  the University of Tokyo

Bibliographic Information

Other Title

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

Abstract

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

• Journal of the City Planning Institute of Japan

  Journal of the City Planning Institute of Japan 42.3 (0), 457-462, 2007

  The City Planning Institute of Japan

Keywords

• Voronoi diagram with obstacles
• Detour distance
• Delaunay network
• Dijkstra method

Details

• CRID: 1390001204215972224
• NII Article ID: 10019724016
• NII Book ID: AN10276504
• DOI: 10.11361/journalcpij.42.3.457
• ISSN: 21850593
• ISSN: 09160647
• NDL BIB ID: 8968416
• Web Site: http://id.ndl.go.jp/bib/8968416
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I8968416
• Web Site: https://www.jstage.jst.go.jp/article/journalcpij/42.3/0/42.3_457/_pdf
• Text Lang: ja
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed