Efficiency of Uniform Grids for Intersection Detection on Serial and Parallel Machines

The uniform grid data structure is a flat (non-hierarchical) grid whose resolution adapts to the data. An exhaustive analysis of the uniform grid data structure for determining intersections in a set of many small line segments is presented. Databases from cartography, VLSI, and graphics with up to 115,973 edges are used. For each data set the intersection time, the ratio of edge pairs tested to pairs found to intersect, and size of intermediate data structures was measured as a function of grid resolution. The execution time was relatively insensitive to the grid size over a range of up to a factor of 10. 115,973 edges were processed to find 135,050 intersections in 683 seconds on a Sun 3/50 workstation. This data structure is also ideally suited for implementation on a parallel machine. When executing on a 16 processor Sequent Balance 21000, total times averaged ten times faster than when using only one processor. Finding all 81,373 intersections in a 62,045 edge database took only 28 seconds elapsed time. This research shows that more complicated, hierarchical data structures, such as quadtrees, are not necessary for this problem.