An improved search algorithm for kirkpatrick's point location method
Ahmad Izani Md. Ismail Abdullah Zawawi Talib · 8th International Multitopic Conference, 2004. Proceedings of INMIC 2004. · 2005
The point location problem is an important and fundamental problem in computational geometry. A point location method that is extensively used is Kirkpatrick's method. Previous attempts to improve the method were based on allowing only the vertices with degree not exceeding a certain value to be removed at each stage. In this paper we present an approach for reducing the query time based on a different perspective. Computational experiments that we conducted indicate the practical efficiencies and effectiveness of our approach.