© University of Kent - Contact | Feedback | Legal | FOI | Cookies
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].Abstract
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
@article{3051,
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 = {http://www.cs.kent.ac.uk/pubs/2010/3051},
publication_type = {article},
submission_id = {29349_1287397361},
journal = {Electronic Notes in Theoretical Computer Science},
volume = {267},
number = {1},
publisher = {Elsevier},
}