City Research Online

Quadtrees as an Abstract Domain

Howe, J. M., King, A. and Lawrence-Jones, C. (2010). Quadtrees as an Abstract Domain. Electronic Notes Theoretical Computer Science, 267(1), pp. 89-100. doi: 10.1016/j.entcs.2010.09.008

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 datastructure can form the basis of an abstract domain. This paper explores this question and suggests that quadtrees offer a new approach to weakly relational domains whilst their hierarchical structure naturally lends itself to representation with boolean functions.

Publication Type: Article
Publisher Keywords: Weakly relational domains, abstract interpretation, quadtrees, boolean formulae
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
URI: http://openaccess.city.ac.uk/id/eprint/1969
[img]
Preview
PDF
Download (164kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login