HV/VH trees: a new spatial data structure for fast region queries

Rosenberg compared linked lists, quad trees with bisector lists, and kD trees, and showed that kD trees significantly outperformed their two rivals on region queries. Quad trees bisector lists performed poorly because of their need to search bisector lists at successive levels, therefore, later improvements to quad trees look the form of eliminating the bisector lists in one way or the other to achieve better region-query performed. In this paper, we explode the myth that bisector lists imply slow region queries by introducing a new data structure, HV/VH trees, which, even though it uses bisector lists, is as fast as than kD trees and two improved forms of quad trees on region queries performed on data from real VLSI designs. Furthermore, we show that HV/VH trees achieve this superb performance while using the least amount of memory.