Heuristics for Generating a Simple Polygonalization

• Teramoto Sachio

• Motoki Mitsuo

• Uehara Ryuhei

• Asano Tetsuo

書誌事項

タイトル別名

• 単純多角形の生成に関する発見的手法

抄録

Given a set S of n points in the plane, randomly generate a simple polygon with n sides using the points of S as its vertices, or compute a simple polygonalization of S. Since the counting problem seems to be quite difficult, heuristic approaches have been adopted during the past decade. We propose a triangulation-base heuristic algorithm which generates each possible simple polygon with a non-zero probability in O(n log n＋f)time, where f is the number of edge-flippings. This time complexity has an advantage over a known O(n^4 log n) algorithm.　：　平面上のｎ点からなる集合Sが与えられた時、Sの点を頂点として持つ単純ｎ角形をランダムに生成する問題について考える。これまで、カウンティング問題でさえ難しいと思われているため、発見的な手法の開発が行われてきた。本論文では、三角形分割を用いる発見的手法を提案する。これは、可能なすべての単純多角形を非負の確率で生成する O(n logn＋f)時間アルゴリズムである。ただし、ｆは辺のフリップ操作回数とする。この手法はこれまで知られているO(N^4 logn)時間アルゴリズムよりも効率的であると考えられる。

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/3274

収録刊行物

• 情報処理学会研究報告 : アルゴリズム研究会

  情報処理学会研究報告 : アルゴリズム研究会 2006-AL (106-6), 41-48, 2006-05

  情報処理学会

キーワード

• Computational geometry
• geometric enumeration
• simple polygon
• triangulation
• heuristics
• 計算幾何学
• 幾何学的数え上げ
• 単純多角形
• 三角形分割
• 発見的手法

詳細情報

• CRID: 1050845762466165760
• NII論文ID: 110004824071
• NII書誌ID: AN10539294
• ISSN: 09196072
• NDL書誌ID: 7936426
• Web Site: http://hdl.handle.net/10119/3274
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7936426
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles