Complementary quadtree

摘要

A new pointerless quadtree representation method is proposed for application to geographic information systems, image processing and computer graphics. The colour of grey nodes in the new tree structure is redefined as the dominant colour among their four sons, and each node is encoded complementarity. The new scheme, termed complementary quadtree,not only reduces the storage space by over 30% compared to linear quadtree, but also guarantees gentle approximation and is efficient in computing geometric properties and in certain set operations.