An overlapping Voronoi diagram-based system for multi-criteria optimal location queries

Ji Zhang, Po-Wei Harn, Wei-Shinn Ku, Min-Te Sun, Xiao Qin, Hua Lu, Xunfei Jiang

Research output: Contribution to journalJournal articlepeer-review

Abstract

This paper presents a novel Multi-criteria Optimal Location Query (MOLQ), which can be applied to a wide range of applications. After providing a formal definition of the novel query type, we propose an Overlapping Voronoi Diagram (OVD) model that defines OVDs and Minimum OVDs (MOVDs), and an OVD overlap operation. Based on the OVD model, we design advanced approaches to answer the query in Euclidean space. 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). Moreover, if there are changes to a limited number of objects, re-evaluating queries over updated object sets would be expensive. Thus, we also propose an MOVD updating model and an advanced algorithm to incrementally update MOVDs to avoid the high cost of query re-evaluation. Our experimental results show that the proposed algorithms can evaluate the novel query type effectively and efficiently.
Original languageEnglish
JournalGeoinformatica
Volume23
Issue number1
Pages (from-to)105-161
Number of pages57
ISSN1384-6175
DOIs
Publication statusPublished - 2019
Externally publishedYes

Cite this