Quadtrees as an Abstract Domain

Howe, J. M., King, A. & 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

[img]
Preview
PDF
Download (164kB) | Preview

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.

Item Type: Article
Uncontrolled Keywords: Weakly relational domains, abstract interpretation, quadtrees, boolean formulae
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: School of Informatics > Department of Computing
URI: http://openaccess.city.ac.uk/id/eprint/1969

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics