Comparison of Finding the Location of the Nearest Health Facility Based On Knn-Voronoi Diagram

Abstract

Searching for an object is the implementation of one type of query that is often applied to spatial data. A common application is
to find K Nearest Neighbor (KNN) of a given number of query objects. With this network, the distance between object locations
depends on their network connectivity and it is computationally expensive to calculate the distance (e.g., shortest path) between
objects. The term location refers to the position of a point location relative to a geometric subdivision or a discontinuous set
of geometric objects. The best-known example is the point location problem, where a division of space into separate regions
is given, and the problem is identifying which regions contain a particular query point. This problem is widely used in fields
such as computer graphics, geographic information systems, and robotics. Point location is also used as a method for proximity
search, when applied in conjunction with a voronoi diagram. In this paper, we will discuss the method of identifying the location
of referral health facilities (faskes) such as hospitals, polyclinics, and the nearest health center. In this paper, we compare a new
approach that is Voronoi Continuous K Nearest Neighbor (VCKNN) to efficiently locate the nearest referral health facility and
evaluate KNN queries in a spatial network database using a first-order Voronoi diagram. This approach is based on partitioning
large networks into small Voronoi regions, and then pre-computing distances both within and across regions. Our empirical
experiments with multiple health facility location searches show that our proposed solution outperforms approaches based on
online distance calculations by up to an order of magnitude, and provides a factor of four increase in filter step selectivity
compared to index-based approaches. This study is shown by comparing the application of several search methods, especially
for Voronoi diagram-based searches.There is a method used for comparison, namely Kd-Trees, but the resulting performance
is still not satisfactory. Another method proposed is the Voronoi Continuous K Nearest Neighbor (VCKNN) algorithm which
uses Voronoi diagrams to help locate nodes as objects in spatial data.