School of Computing

Quadtrees as an Abstract Domain

Jacob M. Howe, Andy King, and Charles Lawrence-Jones

Electronic Notes in Theoretical Computer Science, 267(1):182-196, October 2010 [doi].


Quadtrees have proved popular in computer graphics and spatial databases as a way of representing regions in two dimensional space. This hierarchical data-structure is flexible enough to support non-convex and even disconnected regions, therefore it is natural to ask whether this data-structure can form the basis of an abstract domain. This paper explores this question and suggests that quadtrees offer a new approach to weakly relation domains whilst their hierarchical structure naturally lends itself to representation with boolean functions.

Download publication 219 kbytes (PDF)

Bibtex Record

author = {Jacob M. Howe and Andy King and Charles Lawrence-Jones},
title = {Quadtrees as an {A}bstract {D}omain},
month = {October},
year = {2010},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {10.1016/j.entcs.2010.09.008},
url = {},
    publication_type = {article},
    submission_id = {29349_1287397361},
    journal = {Electronic Notes in Theoretical Computer Science},
    volume = {267},
    number = {1},
    publisher = {Elsevier},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014