Loading...

Login


Paper and Talk Awards

  1. Winner (2nd place), GISCUP 2015:
    Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li. Fast path planning under polygonal obstacle constraints. In 4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS, Bellevue WA USA, 4 Nov 2015. (paper).
  2. Winner of the Best Paper Award (2nd place), AGILE 2012:
    Invalid BibTex Entry in BibSummary! /wrf.bib salles-agile-2012-nonote
  3. Winner of best paper award, Geoinfo 2013:
    Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. R. Franklin and Guilherme C. Pena. A Parallel Sweep Line Algorithm for Visibility Computation. In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics, Campos do Jordão, SP, Brazil, 24-27 Nov 2013. (paper).
  4. Winner of the best fast forward presentation award, ACM SIGSPATIAL GIS 2009:
    Invalid BibTex Entry in BibSummary! /wrf.bib lau-acmgis-2009-nonote

Research Summary

Geometry has been my overriding interest since high school in the 1960s. Geometry is the "branch of mathematics that deals with the measurement, properties, and relationships of points, lines, angles, surfaces, and solids" (Merriam–Webster dictionary). The Geo in geometry is from the Greek Γη meaning, ''earth, ground, land''. (The American Heritage� Book of English Usage). My major recently concluded project was Geo*, a DARPA–funded project for representing and operating on terrain, that is, elevation.

My big long-term unsolved problem is to devise a mathematics of terrain, which would respect its physical properties. To date, I've been nibbling around the edges.

One recently ended project (Cutler, Zimmie, Franklin. NSF CMMI-0835762: CDI-Type I: Fundamental Terrain Representations and Operations) attempted to predict how erosion occurs in levee failure by overtopping, and, after a failure, to reverse-simulate what happened.

A earlier major project was Geo*, funded by DARPA, studied representing and operating on terrain, that is, elevation.

I've applied the same underlying principles in Computational Geometry producing algorithms useful for large datasets, mostly in 3D, and usually implemented.

Both topics are applications of my long term theme of emphasizing small, simple, and fast data structures and algorithms. 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.

16 PhD students (7 currently employed at a college), and 68 masters students have been graduated under my advisement, (names and theses).

My research has been externally funded by the National Science Foundation under Grants ENG-7908139, ECS-8021504, ECS-8351942, CCF-9102553, CCF-0306502, DMS-0327634, CMMI-0835762 and IIS-1117277 by DARPA/DSO, via the NGA, under the GeoStar program, by the US Army Topographic Engineering Center, and by IBM, Sun Microsystems, and Schlumberger-Doll Research.

Many of the algorithms have been implemented. The code is available for nonprofit research and education. RPI Computer graphics group

  • A 2-slide summary of my research is here.
  • A good summary talk is this:

Geometric Operations on Millions of Objects.

  • An overview talk of the future of the field is my keynote talk at GeoInfo 2013, XIV Brazilian Symposium on GeoInformatics.
  • Some research results that I particularly like are here.

Research on Terrain Visibility, Viewshed, Observer Siting

Given a large DEM terrain, we have efficient parallel (using both OpenMP and CUDA) algorithms to compute

  1. the viewshed of an observer,
  2. the visibility index, i.e., the viewshed's area, of every point,
  3. how to site multiple observers to jointly cover the most terrain, perhaps while requiring the observers to be intervisible.

Here is some of our published work. There are links to papers and talks.

  1. Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães and W. Randolph Franklin. An efficient external memory algorithm for terrain viewshed computation. ACM Trans. on Spatial Algorithms and Systems, 2016. (to appear). (paper).
  2. Max J Egenhofer, Keith C Clarke, Song Gao, Teriitutea Quesnot, W. Randolph Franklin, May Yuan and David Coleman. Contributions of GIScience over the Past Twenty Years. In Harlan Onsrud and Werner Kuhn, editor, Advancing Geographic Information Science: The Past and Next Twenty Years, pages 9-34. GSDI association press, 2016. (paper).
  3. Mehrad Kamalzare, Thomas F. Zimmie, Barbara Cutler and W. Randolph Franklin. A New Visualization Method to Evaluate Sediment Transport and Erosion. Geotechnical Testing Journal, 39(3), May 2016. (paper).
  4. Mehrad Kamalzare, Thomas F. Zimmie, Zhongxian Chen, Christopher Stuetzle, Barbara Cutler and W Randolph Franklin. Computer Erosion Modeling Considering Soil Hydraulic Conductivity. Journal of Geotechnical and Transportation Engineering, 1(1), 22 June 2015. http://jgtte.com/issues/Online/Paper%201.pdf. (paper).
  5. Maurício G. Gruppi, Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li. Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification. In Geoinfo 2015, XVI Brazilian Symposium on GeoInformatics, Campos do Jordão, SP, Brazil, 29 Nov - 2 Dec 2015. (paper, talk).
  6. Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li. Fast path planning under polygonal obstacle constraints. In 4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS, Bellevue WA USA, 4 Nov 2015. Winner (2nd place). (paper).
  7. Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li. Fast exact parallel map overlay using a two-level uniform grid. In 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial), Bellevue WA USA, 3 Nov 2015. (paper).
  8. Thiago L. Gomes, Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Guilherme C. Pena. Efficiently computing the drainage network on massive terrains with an external memory flooding process. Geoinformatica, Apr 2015. http://link.springer.com/article/10.1007/s10707-015-0225-y. (paper).
  9. Guilherme C. Pena, Marcus V.A. Andrade, Salles V.G. Magalhães, W. R. Franklin and Chaulio R. Ferreira. An Improved Parallel Algorithm using GPU for Siting Observers on Terrain. In 16th International Conference on Enterprise Information Systems (ICEIS 2014), pages 367-375, Lisbon, 27-30 April 2014. (paper, talk).
  10. Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. R. Franklin and Guilherme C. Pena. A parallel algorithm for viewshed computation on grid terrains. Journal of information and data management, 5(1), 2014. invited. (paper).
  11. Guilherme Pena, Salles Magalhães, Marcus Andrade, Randolph Franklin, Chaulio Ferreira, Wenli Li and Daniel Benedetti. An efficient GPU multiple-observer siting method based on sparse-matrix multiplication. In 3rd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014, Dallas TX USA, 4 Nov 2014. (paper, talk).
  12. Wenli Li, W. Randolph Franklin, Daniel N. Benedetti and Salles V. G. Magalhães. Parallel Multiple Observer Siting on Terrain. In 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014), Dallas, Texas, USA, 4-7 Nov 2014. (paper, poster).
  13. Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. R. Franklin and Guilherme C. Pena. A Parallel Sweep Line Algorithm for Visibility Computation. In Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics, Campos do Jordão, SP, Brazil, 24-27 Nov 2013. Winner of best paper award, http://www.geoinfo.info/geoinfo2013/index.php. (paper).
  14. Invalid BibTex Entry in BibSummary! /wrf.bib magalhaes-ijcisim-2011
  15. Invalid BibTex Entry in BibSummary! /wrf.bib andrade-geoinfo-ext-viewshed-2008
  16. Invalid BibTex Entry in BibSummary! /wrf.bib dt-wrf-spie-2007
  17. Invalid BibTex Entry in BibSummary! /wrf.bib tracy-fwcg-2006
  18. Invalid BibTex Entry in BibSummary! /wrf.bib wrf-sdh2006
  19. Invalid BibTex Entry in BibSummary! /wrf.bib wrf-siting-apr2004
  20. Invalid BibTex Entry in BibSummary! /wrf.bib wrf-site
  21. Invalid BibTex Entry in BibSummary! /wrf.bib wrf-savannah
  22. Invalid BibTex Entry in BibSummary! /wrf.bib fr-hinbv-94

Here are some related papers on 3D object visibility:

  1. Invalid BibTex Entry in BibSummary! /wrf.bib fk-poshs-90-in-geom
  2. Invalid BibTex Entry in BibSummary! /wrf.bib fa-agpvo-88-in-geom
  3. Invalid BibTex Entry in BibSummary! /wrf.bib f-ltehs-88
  4. Invalid BibTex Entry in BibSummary! /wrf.bib fa-sehla-87
  5. Invalid BibTex Entry in BibSummary! /wrf.bib f-ehsao-81
  6. Invalid BibTex Entry in BibSummary! /wrf.bib f-ltehs-80-in-geom
  7. Invalid BibTex Entry in BibSummary! /wrf.bib f-chsa-78
  8. Invalid BibTex Entry in BibSummary! /wrf.bib wrf-prism-hu
  9. Invalid BibTex Entry in BibSummary! /wrf.bib fl-3gdds-78

Enjoy!

More Research Details

These are on a separate page, whose table of contents follows.


Misc