Practical Efficiencies of Planar Point Location Algorithms (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• The planar point location problem is one of the most fundamental problems in computational geometry and stated as follows: Given a straight line planar graph (subdivision) with n vertices and an arbitrary query point Q, determine the region containing Q. Many algorithms have been proposed, and some of them are known to be theoretically optimal (O(log n) search time, O(n) space and O(n log n) preprocessing time). In this paper, we implement several representative algorithms in C, and investigate their practical efficiencies by computational experiments on Voronoi diagrams with 2^<10>-2^<17> vertices.

• 社団法人電子情報通信学会の論文
• 1994-04-25

著者

• Asano Takao

  Faculty Of Engineering Tohoku University

• Asano Takao

  Faculty Of Science And Engineering Chuo University

• Edahiro Masato

  C&c Research Laboratories Nec Corporation

• Kagami Satoshi

  Faculty Of Engineering The University Of Tokyo

• Edahiro Masato

  C&C Research Laboratories, NEC Corporation

関連論文

• An Approximation Algorithm for the Hamiltonian Walk Problem on Maximal Planar Graphs (Graphs and Combinatorics III)
• A Dynamic Algorithm for Placing Rectangles without Overlapping
• Practical Efficiencies of Planar Point Location Algorithms (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク