© 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}, }