Research archive · original page Research.UniformGrid · last recorded update 2006-11-13
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 E'^2^'. 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 N'^2^' . 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:
-
Varol Akman, Wm Randolph Franklin, Mohan Kankanhalli, and Chandrasekhar Narayanaswami. Geometric computing and the uniform grid data technique. Computer Aided Design, 21(7):410–420, 1989.Paper.
BibTeX
@article{afkn-gcugd-89, author = "Akman, Varol and Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar", title = "Geometric Computing and the Uniform Grid Data Technique", journal = "Computer Aided Design", year = "1989", volume = "21", number = "7", pages = "410--420", fulltext = "https://wrfranklin.org/p/54-cad89-ug.pdf", href = "\bibhref{54-cad89-ug}", mykey = "akman chandra kankanhalli", keywords = "intersection, CAD, grids" } -
Wm Randolph Franklin, Chandrasekhar Narayanaswami, Mohan Kankanhalli, David Sun, Meng-Chu Zhou, and Peter YF Wu. Uniform grids: a technique for intersection detection on serial and parallel machines. In Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography, 100–109. Baltimore, Maryland, 2-7 April 1989.Paper.
BibTeX
@inproceedings{fnkszw-ugtid-89, author = "Franklin, Wm Randolph and Narayanaswami, Chandrasekhar and Kankanhalli, Mohan and Sun, David and Zhou, Meng-Chu and Wu, Peter YF", title = "Uniform Grids: A Technique for Intersection Detection on Serial and Parallel Machines", booktitle = "Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography", year = "1989", month = "2-7 April", address = "Baltimore, Maryland", pages = "100--109", fulltext = "https://wrfranklin.org/p/57-autocarto89-ug.pdf", href = "\bibhref{57-autocarto89-ug}", mykey = "chandra kankanhalli", keywords = "parallel computation, intersection, CAD, grids" } -
Wm Randolph Franklin, Narayanaswami Chandrasekhar., Mohan Kankanhalli, Manoj Seshan, and Varol Akman. Efficiency of uniform grids for intersection detection on serial and parallel machines. In Nadia Magnenat-Thalmann and D. Thalmann, editors, New Trends in Computer Graphics (Proc. Computer Graphics International'88), pages 288–297. Springer-Verlag, 1988.Paper.
BibTeX
@incollection{fcksa-eugid-88, author = "Franklin, Wm Randolph and Chandrasekhar., Narayanaswami and Kankanhalli, Mohan and Seshan, Manoj and Akman, Varol", editor = "Magnenat-Thalmann, Nadia and Thalmann, D.", title = "Efficiency of uniform grids for intersection detection on serial and parallel machines", booktitle = "New Trends in Computer Graphics (Proc. Computer Graphics International'88)", publisher = "Springer-Verlag", year = "1988", pages = "288--297", fulltext = "https://wrfranklin.org/p/50-gi88-ug.pdf", href = "\bibhref{50-gi88-ug}", mykey = "akman chandra kankanhalli", keywords = "parallel computation, intersection, grids" } -
WR Franklin, N. Chandrasekhar, M. Kankanhalli, and V. Akman. Fast intersection detection on serial and parallel machines using the uniform grid technique. 1988.Paper.
BibTeX
@Unpublished{fcka-fidspm-88, author = "Franklin, WR and Chandrasekhar, N. and Kankanhalli, M. and Akman, V.", title = "Fast intersection detection on serial and parallel machines using the uniform grid technique", year = "1988", note = "", fulltext = "https://wrfranklin.org/p/53-unpub88-fast.pdf", href = "\bibhref{53-unpub88-fast}", mykey = "akman kankanhalli chandra" } -
Wm Randolph Franklin. Adaptive grids for geometric operations. Cartographica, 21(2–3):161–167, Summer – Autumn 1984. monograph 32–33.
BibTeX
@article{f-aggo-84, author = "Franklin, Wm Randolph", title = "Adaptive Grids for geometric operations", journal = "Cartographica", volume = "21", number = "2--3", pages = "161--167", month = "Summer -- Autumn", year = "1984", note = "monograph 32--33", succeeds = "f-aggo-83", fulltext = "https://wrfranklin.org/p/23-cartographica86-grid.pdf", href = "\bibhref{23-cartographica86-grid}", keywords = "intersection, grids" } -
Wm Randolph Franklin. Adaptive grids for geometric operations. In Barry S Wellar, editor, Proc. Sixth International Symposium on Automated Cartography (Auto-Carto Six), Volume II: Automated Cartography: international perspectives on achievements and challenges, 230–239. Ottawa, 1983.
BibTeX
@inproceedings{f-aggo-83, author = "Franklin, Wm Randolph", editor = "Wellar, Barry S", title = "Adaptive Grids for geometric operations", booktitle = "Proc. Sixth International Symposium on Automated Cartography (Auto-Carto Six), Volume II: Automated Cartography: international perspectives on achievements and challenges", pages = "230--239", address = "Ottawa", year = "1983", precedes = "wrf-aggo-84", keywords = "intersection, grids" }
No publications match your search. Try another word or clear the search.