Abstract
Voronoi diagram is a method that divides the plane into smaller area based on the nearest distance to an object. There is a new variant of Voronoi diagram where each Voronoi cell has ordered generator points distances called Highest Order Voronoi Diagram (HSVD). The HSVD construction complexity is on O(m(4)), where m is the number of generator points. 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 methods implemented on conventional computing/sequential processing and have limitation on number of points that can be processed. Because on sequential processing the process executed sequentially, then there is a process awaits for another process to finish. Beside that, computing resources are only utilized sequentially. To overcome this issues, we can use distributed computing framework that focuses on the optimization of computing resources called Apache Spark. In this paper we adapt FLIP and LAM construction method in Apache Spark framework. Our observation shows that the processing time is 60% faster than previous implementation and also 17% increase on the number of point that can be processed.