Efficient computation of the convex hull on sets of points stored in a k - tree compact data structure
- PDF / 2,331,325 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 188 Views
Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure Juan Felipe Castro1 · Miguel Romero1 · Gilberto Gutiérrez1 · Mónica Caniupán1 Carlos Quijada-Fuentes1
·
Received: 11 October 2019 / Accepted: 2 July 2020 © Springer-Verlag London Ltd., part of Springer Nature 2020
Abstract In this paper, we present two algorithms to obtain the convex hull of a set of points that are stored in the compact data structure called k 2 -tr ee. This problem consists in given a set of points P in the Euclidean space obtaining the smallest convex region (polygon) containing P. Traditional algorithms to compute the convex hull do not scale well for large databases, such as spatial databases, since the data does not reside in main memory. We use the k 2 tr ee compact data structure to represent, in main memory, efficiently a binary adjacency matrix representing points over a 2D space. This structure allows an efficient navigation in a compressed form. The experimentations performed over synthetical and real data show that our proposed algorithms are more efficient. In fact they perform over four order of magnitude compared with algorithms with time complexity of O(n log n). Keywords Algorithms · Data structures · Spatial databases · Computational geometry · Compact data structures · Convex hull
1 Introduction Today technologies such as smart phones, Global Positioning Systems (GPS), or satellites make possible to collect and transfer large amount of geographical data. These data are used for many applications such as Google maps to locate places, and so on. There are
B
Mónica Caniupán [email protected] Juan Felipe Castro [email protected] Miguel Romero [email protected] Gilberto Gutiérrez [email protected] Carlos Quijada-Fuentes [email protected]
1
Universidad del Bío-Bío, Bío-Bío, Chile
123
J. F. Castro et al.
some applications that need to answer several interested problems that need geographical information, such as, to find the closest neighbor to a given point p, the skyline query, or the convex hull, which is analyzed in this work. The convex hull is a well-know problem in computational geometry [8]. This problem is defined as follows: Given a set of points P in the Euclidean space, obtaining the smallest convex region (polygon) containing P. There are several proposed algorithms to compute the convex hull, such as the solutions reported in [12,15,18,23]. Traditional algorithms to compute the convex hull do not scale well for large databases, such as spatial databases, since the data does not reside in main memory, but mostly on disks. A good algorithm is the one reported in [3] where the set of points is stored in a multidimensional hierarchical data structure (such as an R-tree index [11]) that allows to speed up the computation. In this paper, we explore the computation of the convex hull for a set of points represented in a compact data structure called k 2 -tr ee [4]. Compact data structures are data structures that use a small amount o
Data Loading...
