Voronoi diagram is a method that divides the plane into smaller area based on the nearest distance to an object. Highest Order Voronoi Diagram is a new variant of the Voronoi diagram. The complexity of HSVD construction is on O($m^{4}$), where m is the number of generator points. Highest order Voronoi diagram can be used on the field of query processing such as reverse k-nearest neighbour (RKNN), k farthest neighbour (KFN), k nearest neighbour(KNN), etc.
From related works, there are method called Fast Labelling and Interchange Position (FLIP) and Left with Least-Angle Movement (LAM) used to construct highest order voronoi diagram. But, both of this method implemented on conventional computing and have limitation on number of points that can be processed and execution time is quite high. There is inefficiency of reuse a working set of data process by accessing disk repeatedly which caused the execution time is quite high and limit the number of points that can be processed. Beside that, conventional computing didn't utilize the available resources.
There are frameworks that can be used to utilize the available resources to optimize the computing process called Apache Spark. Apache Spark distribute the task to all available resources and work well on iterative process that reuse a set of data because of the ability to keep needed data in memory.
This minor thesis shows that with the help of Apache Spark framework, the number of point that can be processed increase to 24 with the execution time is 60\% faster than LAM implementation in average.
Keywords: voronoi diagram, highest order, apache spark, spatial