Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions (Q2269835)

The authors present improved and simplified algorithms for map overlay, point location and range searching in an external memory for fat triangulations and low-density subdivisions. These are based on a quadtree which is defined to ensure that each leaf intersects only a constant number of edges of the subdivision. The authors also compare their results with the corresponding results given by \textit{L. Arge, D. E. Vengroff} and \textit{J. S. Vitter} [Algorithmica 47, 1--25 (2007; Zbl 1107.68118); and \textit{A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer} and \textit{E. A. Ramos} [Comput. Geom. Theory Appl. 11, 305--337 (2001; Zbl 1074.68669)].