Multi-Criteria Optimal Location Query with Overlapping Voronoi Diagrams
Ji Zhang, Wei‐Shinn Ku, Min Sun, Xiao Qin, Hua Cai Lu · VBN Forskningsportal (Aalborg Universitet) · 2014
This paper presents a novel optimal location selection problem, which can be applied to a wide range of applications.After providing a formal definition of the novel query type, we explore an intuitive approach that sequentially scans all possible object combinations in the search space.Then, we propose an Overlapping Voronoi Diagram (OVD) model that defines OVDs and Minimum OVDs, and construct an algebraic structure under an OVD overlap operation.Based on the OVD model, we design an advanced approach to answer the query.Due to the high complexity of Voronoi diagram overlap computation, we improve the overlap operation by replacing the real boundaries of Voronoi diagrams with their Minimum Bounding Rectangles (MBR).We also propose a cost-bound iterative approach that efficiently processes a large number of Fermat-Weber problems.Our experimental results show that the proposed algorithms can evaluate the novel query type effectively and efficiently.