Uniform grids are useful in many of the following applications. This idea is intended to be just sophisticated enough to solve the problem, without being so complicated that it is difficult to implement, including the messy special cases, and parallelize. (1977)

The concept, which is useful for culling pairs of objects that may intersect, is to overlay a uniform grid on the data. Then iterate over the elements, finding which grid cells each passes thru. Finally, iterate over the cells, comparing pairs of elements that pass thru the same cell. Implementing this properly requires some attention to detail. This method works well even when the data is unevenly distributed, where one's first impulse would be to use the, more complicated, quadtree.

One application is a parallelizable algorithm finds all the intersections among a large number of small line segments in E2. The time to find all K intersections among N line segments is an expected θ(N+K), altho an adversary can choose input to raise that to N2 . However no real data sets have exhibited that behavior. Data has been used from cartography, VLSI design, and nonuniform meshes. This is a common operation in many higher-level operations such as boolean combinations. Papers include:

  1. . Varol Akman, Wm Randolph Franklin, Mohan Kankanhalli and Chandrasekhar Narayanaswami. Computer Aided Design, 21(7):410-420, 1989. (paper).
    Paper.
  2. . Wm Randolph Franklin, Chandrasekhar Narayanaswami, Mohan Kankanhalli, David Sun, Meng-Chu Zhou and Peter YF Wu. In Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography, pages 100-109, Baltimore, Maryland, 2-7 April 1989. (paper).
    Paper.
  3. . Wm Randolph Franklin , Narayanaswami Chandrasekhar., Mohan Kankanhalli, Manoj Seshan and Varol Akman. In New Trends in Computer Graphics (Proc. Computer Graphics International'88), pages 288-297.Springer-Verlag, , 1988. (paper).
    Paper.
  4. . WR Franklin, N. Chandrasekhar, M. Kankanhalli and V. Akman, 1988. (paper).
    Paper.
  5. . Wm Randolph Franklin. Cartographica, 21(2--3):161-167, Summer -- Autumn 1984. monograph 32--33. (paper).
  6. . Wm Randolph Franklin. In Proc. Sixth International Symposium on Automated Cartography (Auto-Carto Six), pages 230-239, Ottawa, 1983.


<< Efficient Low Level Operations | Research Page List | LocalTopology >>