Multi-criteria optimal location query with Overlapping Voronoi diagrams

Ji Zhang, Wei Shinn Ku, Min Te Sun, Xiao Qin, Hua Lu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2014
Subtitle of host publication17th International Conference on Extending Database Technology, Proceedings
EditorsVincent Leroy, Vassilis Christophides, Vassilis Christophides, Stratos Idreos, Anastasios Kementsietsidis, Minos Garofalakis, Sihem Amer-Yahia
PublisherOpenProceedings.org, University of Konstanz, University Library
Pages391-402
Number of pages12
ISBN (Electronic)9783893180653
DOIs
StatePublished - 2014
Event17th International Conference on Extending Database Technology, EDBT 2014 - Athens, Greece
Duration: 24 Mar 201428 Mar 2014

Publication series

NameAdvances in Database Technology - EDBT 2014: 17th International Conference on Extending Database Technology, Proceedings

Conference

Conference17th International Conference on Extending Database Technology, EDBT 2014
Country/TerritoryGreece
CityAthens
Period24/03/1428/03/14

Keywords

  • Optimal location query
  • Voronoi Diagram

Fingerprint

Dive into the research topics of 'Multi-criteria optimal location query with Overlapping Voronoi diagrams'. Together they form a unique fingerprint.

Cite this