IEICE TRANSACTIONS on Fundamentals
Practical Efficiencies of Planar Point Location Algorithms
Summary :
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 arbitary 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 210 - 217 vertices.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.4 pp.608-614
- Publication Date
- 1994/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Satoshi KAGAMI, Masato EDAHIRO, Takao ASANO, "Practical Efficiencies of Planar Point Location Algorithms" in IEICE TRANSACTIONS on Fundamentals,
vol. E77-A, no. 4, pp. 608-614, April 1994, doi: .
Abstract: 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 arbitary 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 210 - 217 vertices.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e77-a_4_608/_p
Copy
@ARTICLE{e77-a_4_608,
author={Satoshi KAGAMI, Masato EDAHIRO, Takao ASANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Practical Efficiencies of Planar Point Location Algorithms},
year={1994},
volume={E77-A},
number={4},
pages={608-614},
abstract={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 arbitary 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 210 - 217 vertices.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Practical Efficiencies of Planar Point Location Algorithms
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 608
EP - 614
AU - Satoshi KAGAMI
AU - Masato EDAHIRO
AU - Takao ASANO
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1994
AB - 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 arbitary 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 210 - 217 vertices.
ER -
English
