The UCSB brown-bag forum on spatial thinking presents

Global properties from local topology

W. Randolph Franklin, Rensselaer Polytechnic Institute (Troy NY USA)

12:00 p.m. Tuesday, November 10, 2015 | Phelps Hall 3512 (map)

zermattAbstract. This talk will show how to use only local topological properties of polygons and maps to compute various global properties, and even to overlay pairs of maps. This extends the power of local topology beyond local properties like the 9-intersection matrix.  Typically, we require only the location of each vertex, plus the directions of its adjacent edges and the names and sectors of its adjacent faces.  No more global info, such as the complete edges or faces, is needed.  Area, center of gravity, perimeter length, and similar properties are computable with a simple map-reduce over the data. With this formulation, coding is easier, fewer special cases need be considered, and the computations parallelize easily.  The target may be either a shared memory CPU like an Intel Xeon, or an Nvidia GPU processor. Overlaying two 2D maps is also easy.  Salles Magalhaes has implemented EPUG-OVERLAY, which can overlay the US Block Boundaries and US Water Bodies maps, with a total of 54,000,000 vertices and 739,000 faces, in only 322 elapsed seconds (excluding I/O) on our dual 8-core Xeon workstation.  That time is using 16 cores, and is 11x faster than using one core. Unlike other overlay implementations, EPUG-OVERLAY computes the overlay with no roundoff error whatsoever, because it uses rational numbers.

W. Randolph Franklin is a Professor in the Electrical, Computer, and Systems Engineering Dept, Rensselaer Polytechnic Institute (Troy NY USA), with a courtesy joint appointment in the Computer Science Dept. His current NSF research project is to understand the mathematics of terrain. His research hobby is designing and implementing small, simple, and fast data structures and algorithms for large geometric datasets. Note that efficiency in both space and time can become more important as machines get faster. This research is applicable to computational cartography, computer graphics, computational geometry, and geographic information science. During 2000-2002 Franklin served a rotation to the National Science Foundation, as Director of the Numeric, Symbolic, and Geometric Computation Program. He was one of the prime movers of the two Computational Algorithms and Representations for Geometric Objects (CARGO) solicitations, joint between NSF and DARPA. Franklin’s degrees are from Toronto (BSc, Computer Science), and Harvard (AM & PhD, Mathematica Accomodata).

The objectives of the ThinkSpatial brown-bag presentations are to exchange ideas about spatial perspectives in research and teaching, to broaden communication and cooperation across disciplines among faculty and graduate students, and to encourage the sharing of tools and concepts.
Please contact Andrea Ballatore (893-5267, to review and schedule possible discussion topics or presentations that share your disciplinary interest in spatial thinking.

Follow spatial@ucsb on Facebook | Twitter | Google+ | Google Calendar

ThinkSpatial: W. Randolph Franklin