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.

A fully three-dimensional simulation tool for modeling the ion implantation in arbitrarily complex three-dimensional structures is described. The calculation is based on the Monte Carlo (MC) method. For MC simulations of realistic three-dimensional structures the key problem is the CPU-time consumption which is primarily caused by two facts. (1) A large number of ion trajectories (about 107) has to be simulated to get results with reasonable low statistical noise. (2) The point location problem is very complex in the three-dimensional space. Solutions for these problems are given in this paper. To reduce the CPU-time for calculating the numerous ion trajectories a superposition method is applied. For the point location (geometry checks) different possibilities are presented. Advantages and disadvantages of the conventional intersection method and a newly introduced octree method are discussed. The octree method was found to be suited best for three-dimensional simulation. Using the octree the CPU-time required for the simulation of one ion trajectory could be reduced so that it only needs approximately the same time as the intersection method in the two-dimensional case. Additionally, the data structure of the octree simplifies the coupling of this simulation tool with topography simulators based on a cellular method. Simulation results for a three-dimensional trench structure are presented.