Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure

Juan Felipe Castro, Miguel Romero, Gilberto Gutiérrez, Mónica Caniupán, Carlos Quijada-Fuentes

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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 k2-tree. 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 k2-tree 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(nlog n).

Original languageEnglish
Pages (from-to)4091-4111
Number of pages21
JournalKnowledge and Information Systems
Issue number10
StatePublished - 1 Oct 2020
Externally publishedYes


  • Algorithms
  • Compact data structures
  • Computational geometry
  • Convex hull
  • Data structures
  • Spatial databases


Dive into the research topics of 'Efficient computation of the convex hull on sets of points stored in a k-tree compact data structure'. Together they form a unique fingerprint.

Cite this