The EXCELL Method for Efficient Geometric Access to Data

Abstract

The extendible cell (EXCELL) method provides a data structure for efficient geometric access. It stores geometric data into computer storage blocksm corresponding to disjoint variable sized rectangular cells accessible by an address calculation type directory. We describe the method for point files and files of more complicated figures analyzing performance. We report algorithms for the nearest neighbour and point-in-polygon-network problems and describe applications to geographical data bases, hidden line elimination and geometric modeling.