Finding nearest facility for multiple customers using voronoi diagram

Abstract

Searching for a facility near to many customers is such a problem that even an approximately correct answer can save lot of labor, time and money. A possible solution for decision makers to reach facility approximately nearer to all customers has been discussed. It took time of order O(n log n) as it is based on voronoi diagram of order O(n log n) and its own time is of linear order. The proposed algorithm tackled the problem of finding the nearest facility for multiple customers by considering two criteria. The first one was minimizing the aggregate distances i.e. sum of total distances covered by all the customers. The second one was minimizing the maximum difference i.e. the difference between the farthest customer and the nearest customer. The approach given here has used Plane sweep algorithm or Fortune's algorithm for voronoi diagram construction algorithm as its base algorithm because it is one the most efficient algorithm known for computing voronoi diagram.

Topics

    7 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)