Farzad Bayat - Department of Electrical and Computer Engineering, Faculty of Engineering, Kharazmi University
Zahra Nilforoushan - Department of Electrical and Computer Engineering, Faculty of Engineering, Kharazmi University

Tree search algorithms are vital for the search methods in structured data. Such algorithms deal with nodes which can be taken from a data structure. One famous tree data structure is split tree. In this paper, to compute the split tree in polar coordinates, a method has been introduced. Assuming that the algorithm inputs (in form of points) have been distributed in the form of a circle or part of a circle, polar split tree can be used. For instance, we can use these types of trees to transmit radio and telecommunication waves from host stations to the receivers and to search the receivers. Since we are dealing with data points that are approximately circular distributed, it is suggested to use polar coordinates. Furthermore, there are several researches by search algorithms for the central anchor which leads to the assignment of a virtual polar coordinate system. In this paper, the structure of Cartesian split tree will be explained and the polar split tree will be implemented. Then, by doing nearest neighbor search experiments, we will compare the polar split tree and polar quad tree in terms of searching time and amount of distance to the closest neighbor and in the end, better results will be achieved.

Split Tree; Polar Split Tree; Quad Tree; Polar Quad Tree; Nearest Neighbor Search.