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 articleResearchpeer-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
ISSN1384-6175
Publication statusPublished - 2019

Fingerprint

diagram
costs
evaluation
Costs
cost

Cite this

Zhang, J., Harn, P-W., Ku, W-S., Sun, M-T., Qin, X., Lu, H., & Jiang, X. (2019). An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries. Geoinformatica, 23(1), 105-161.
Zhang, Ji ; Harn, Po-Wei ; Ku, Wei-Shinn ; Sun, Min-Te ; Qin, Xiao ; Lu, Hua ; Jiang, XunFei. / An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries. In: Geoinformatica. 2019 ; Vol. 23, No. 1. pp. 105-161.
@article{e7b26f242b354ef8b85a66efe20c9bfe,
title = "An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries",
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.",
author = "Ji Zhang and Po-Wei Harn and Wei-Shinn Ku and Min-Te Sun and Xiao Qin and Hua Lu and XunFei Jiang",
year = "2019",
language = "English",
volume = "23",
pages = "105--161",
journal = "Geoinformatica",
issn = "1384-6175",
publisher = "Springer",
number = "1",

}

Zhang, J, Harn, P-W, Ku, W-S, Sun, M-T, Qin, X, Lu, H & Jiang, X 2019, 'An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries', Geoinformatica, vol. 23, no. 1, pp. 105-161.

An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries. / Zhang, Ji; Harn, Po-Wei; Ku, Wei-Shinn; Sun, Min-Te; Qin, Xiao; Lu, Hua; Jiang, XunFei.

In: Geoinformatica, Vol. 23, No. 1, 2019, p. 105-161.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries

AU - Zhang, Ji

AU - Harn, Po-Wei

AU - Ku, Wei-Shinn

AU - Sun, Min-Te

AU - Qin, Xiao

AU - Lu, Hua

AU - Jiang, XunFei

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

M3 - Journal article

VL - 23

SP - 105

EP - 161

JO - Geoinformatica

JF - Geoinformatica

SN - 1384-6175

IS - 1

ER -

Zhang J, Harn P-W, Ku W-S, Sun M-T, Qin X, Lu H et al. An Overlapping Voronoi Diagram-based System for Multi-Criteria Optimal Location Queries. Geoinformatica. 2019;23(1):105-161.