Research archive · original page Research.Research · last recorded update 2017-04-25
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 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 current funded project (Cutler, Zimmie, Franklin. NSF CMMI-0835762: CDI-Type I: Fundamental Terrain Representations and Operations) attempts 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.
There are two main groups in my research: Computational Cartography and Computational Geometry. The rest of this page describes various subtopics.
Computational cartography research
This, my major theme, includes terrain representation and operations thereon, applied to large datasets.
Terrain: This is the elevation of the earth's surface above the geoid.
Representation: What data structures should be used? Leading existing representations include Triangulated Irregular Networks (`TINs) and matrices of elevations. I am studying other methods such as scooping and Overdetermined Laplacian `PDEs. Part of the representation problem is how to compress the data, either losslessly or lossily, which maintaining some metric, such as RMS elevation or slope error or visibility.
The hard part of representation is devising more powerful, though less tractable, nonlinear encoding techniques to compat with the nonlinear physics of terrain formation. This research is cognizant of the peculiar properties of terrain, such as its low degree of continuity, its long-range correlations (drainage basins), and its vertical asymmetry (there are many local maxima, but few local minima). Important operations include lossy compression, drainage computation, observer siting, and mobility determination.
Operations: What do we want to do with the terrain? Typical operations include multiobserver siting and path planning.
More info: Alternate Terrain Reps
Alternate Terrain Reps
This theme has the following goals:
- Study alternate terrain representations that are more compact.
- Since the new representations will therefore be lossy, evaluate the size / quality tradeoffs.
- These new representations ought to make it easier to represent legal terrain than illegal terrain.
- We wish to process datasets up to 50000x50000 elevation posts.
- With these new representations, uncompression speed is more important than compression speed.
- The new representations are to be evaluated on metrics such as visibility and mobility.
This is my most promising long-term theme. Unfortunately, shortterm pressures have prevented its getting the time it deserves.
Publications include the following. (Publications relevant to more than one topic are listed under each topic.)
-
Christopher Stuetzle and W. Randolph Franklin. Representing terrain with mathematical operators. In 15th International Symposium on Spatial Data Handling. Bonn, Germany, 22–24 Aug 2012.
BibTeX
@InProceedings{stuetzle-sdh-2012, author = "Stuetzle, Christopher and Franklin, W. Randolph", title = "Representing terrain with mathematical operators", booktitle = "15th International Symposium on Spatial Data Handling", year = "2012", address = "Bonn, Germany", month = "22--24 Aug", fulltext = "https://wrfranklin.org/p/153-sdh2012-representing.pdf", customlinkslides = "https://wrfranklin.org/p/153-sdh2012-representing-talk.pdf", customlinkvideo = "https://wrfranklin.org/p/153-sdh2012-representing-video.mp4", mykey = "terrain stuetzle", href = "\bibhrefpt{153-sdh2012-representing}{153-sdh2012-representing-talk.pdf}" } -
Christopher Stuetzle and W. Randolph Franklin. Representation of terrain data by drilling process. In 2012 AutoCarto International Symposium on Automated Cartography. Columbus OH, 16–18 Sep 2012. abstract.
BibTeX
@InProceedings{stuetzle-autocarto-2012, author = "Stuetzle, Christopher and Franklin, W. Randolph", title = "Representation of terrain data by drilling process", booktitle = "2012 AutoCarto International Symposium on Automated Cartography", year = "2012", address = "Columbus OH", month = "16--18 Sep", note = "abstract", mykey = "terrain stuetzle", fulltext = "https://wrfranklin.org/p/155-autocarto2012-rep-terrain.pdf", customlinkslides = "https://wrfranklin.org/p/155-autocarto2012-rep-terrain-talk.pdf", href = "\bibhrefat{155-autocarto2012-rep-terrain-abs}{155-autocarto2012-rep-terrain-talk.pdf}" } -
You Li and W. Randolph Franklin. 4D-ODETLAP: a novel high-dimensional compression method on time-varying geospatial data. In Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of ISPRS Technical Commission IV & AutoCarto 2010. Orlando, Florida, 15–18 Nov 2010.
BibTeX
@InProceedings{li-autocarto-2010, author = "Li, You and Franklin, W. Randolph", title = "{4D-ODETLAP}: A Novel High-dimensional Compression Method on Time-varying Geospatial Data", booktitle = "Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of {ISPRS} Technical Commission {IV} \\& {AutoCarto} 2010", year = "2010", address = "Orlando, Florida", mykey = "youli odetlap", month = "15--18 Nov", fulltext = "https://wrfranklin.org/p/136-autocarto2010-li.pdf", customlinkslides = "https://wrfranklin.org/p/136-autocarto2010-li-talk.pptx", href = "\bibhrefpt{136-autocarto2010-li}{136-autocarto2010-li-talk.pptx}" } -
W. Randolph Franklin. Towards a mathematics of terrain. In 20th Annual Fall Workshop on Computational Geometry (FWCG 2010). Stony Brook University, Stony Brook, NY 11794, USA, 29–30 Oct 2010. (extended abstract and talk).
BibTeX
@InProceedings{terrain-fwcg-2010, author = "Franklin, W. Randolph", title = "Towards a Mathematics of Terrain", booktitle = "20th Annual Fall Workshop on Computational Geometry ({FWCG} 2010)", month = "29--30 Oct", year = "2010", note = "(extended abstract and talk)", address = "Stony Brook University, Stony Brook, NY 11794, USA", fulltext = "https://wrfranklin.org/p/144-fwcg2010-terrain.pdf", customlinkslides = "https://wrfranklin.org/p/144-fwcg2010-terrain-talk.pdf", mykey = "terrain", href = "\bibhrefat{144-fwcg2010-terrain}{144-fwcg2010-terrain-talk.pdf}" } -
Zhongyi Xie, W. Randolph Franklin, and Dan Tracy. Slope preserving lossy terrain compression. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010). San Jose, CA, USA, 2–5 Nov 2010. (PhD Dissertation Showcase).
BibTeX
@InProceedings{xie-acmgis-2010, author = "Xie, Zhongyi and Franklin, W. Randolph and Tracy, Dan", title = "Slope Preserving Lossy Terrain Compression", booktitle = "18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010)", year = "2010", month = "2--5 Nov", address = "San Jose, CA, USA", href = "\bibhrefpp{140-acmgis2010-xie}{140-acmgis2010-xie-poster.pdf}", fulltext = "https://wrfranklin.org/p/140-acmgis2010-xie.pdf", customlinkposter = "https://wrfranklin.org/p/140-acmgis2010-xie-poster.pdf", mykey = "tracy xie terrain", note = "(PhD Dissertation Showcase)" } -
W. Randolph Franklin and Michael Gousie. Terrain elevation data structure operations. In C. Peter Keller, editor, Proceedings of the 19th International Cartographic Association Conference, 1011–1020. Ottawa, August 1999. URL: https://wrfranklin.org/wiki/Research/ica99/.
BibTeX
@inproceedings{wrf-ica99-web, author = "Franklin, W. Randolph and Gousie, Michael", editor = "Keller, C. Peter", title = "Terrain Elevation Data Structure Operations", booktitle = "Proceedings of the 19th {International Cartographic Association} Conference", month = "August", pages = "1011--1020", isbn = "0-919088-54-6", address = "Ottawa", url = "https://wrfranklin.org/wiki/Research/ica99/", fulltext = "https://wrfranklin.org/p/90-ottawa-ica99-terrain.pdf", href = "\bibhref{90-ottawa-ica99-terrain}", mykey = "terrain", year = "1999" } -
Zhongyi Xie, Marcus A. Andrade, W Randolph Franklin, Barbara Cutler, Metin Inanc, Jonathan Muckell, and Daniel M. Tracy. Progressive transmission of lossily compressed terrain. In CLEI 2008 Conferencia Latinoamericana de Informática. Santa Fe, Argentina, 8–12 Sep 2008.
BibTeX
@InProceedings{andrade-prog-trans-2008, author = "Xie, Zhongyi and Andrade, Marcus A. and Franklin, W Randolph and Cutler, Barbara and Inanc, Metin and Muckell, Jonathan and Tracy, Daniel M.", title = "Progressive Transmission of Lossily Compressed Terrain", booktitle = "{CLEI 2008} Conferencia Latinoamericana de Informática", year = "2008", address = "Santa Fe, Argentina", month = "8--12 Sep", fulltext = "https://wrfranklin.org/p/127-andrade-prog-trans-2008.pdf", href = "\bibhref{127-andrade-prog-trans-2008}", mykey = "marcus tracy inanc muckell xie terrain" } -
W. Randolph Franklin, Daniel M. Tracy, Marcus Andrade, Jonathan Muckell, Metin Inanc, Zhongyi Xie, and Barbara Cutler. Slope accuracy and path planning on compressed terrain. In Symposium on Spatial Data Handling. Montpellier FR, June 2008.
BibTeX
@InProceedings{wrf-sdh-2008, author = "Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus and Muckell, Jonathan and Inanc, Metin and Xie, Zhongyi and Cutler, Barbara", title = "Slope Accuracy and Path Planning on Compressed Terrain", booktitle = "Symposium on Spatial Data Handling", year = "2008", month = "June", address = "Montpellier FR", fulltext = "https://wrfranklin.org/p/119-sdh08-slope.pdf", mykey = "tracy inanc marcus muckell xie pathplan terrain", href = "\bibhref{119-sdh08-slope}" } -
Zhongyi Xie, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Metin Inanc, and Daniel M. Tracy. Surface compression using over-determined Laplacian approximation. In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering. paper 6697-15.
BibTeX
@InProceedings{zx-wrf-spie-2007, author = "Xie, Zhongyi and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Inanc, Metin and Tracy, Daniel M.", title = "Surface compression using over-determined {Laplacian} approximation", booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}", year = "2007", month = "27 August", organization = "International Society for Optical Engineering", address = "San Diego CA", note = "paper 6697-15", fulltext = "https://wrfranklin.org/p/113-spie07-xie.pdf", href = "\bibhref{113-spie07-xie}", mykey = "marcus inanc xie odetlap", abstract = "" } -
Zhongyi Xie, Marcus A. Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Daniel M. Tracy, and Jonathan Muckell. Approximating terrain with over-determined Laplacian PDEs. In 17th Fall Workshop on Computational Geometry. IBM TJ Watson Research Center, Hawthorne NY, 2–3 Nov 2007. (poster session, no formal proceedings).
BibTeX
@InProceedings{xie-fwcg-2007, author = "Xie, Zhongyi and Andrade, Marcus A. and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Tracy, Daniel M. and Muckell, Jonathan", title = "Approximating terrain with over-determined {Laplacian} {PDEs}", booktitle = "17th Fall Workshop on Computational Geometry", month = "2--3 Nov", mykey = "tracy inanc marcus xie muckell odetlap", year = "2007", note = "(poster session, no formal proceedings)", address = "IBM TJ Watson Research Center, Hawthorne NY", fulltext = "https://wrfranklin.org/p/117-fwcg07-xie-abs.pdf", customlinkposter = "https://wrfranklin.org/p/117-fwcg07-xie-poster.ppt", href = "\bibhrefap{117-fwcg07-xie-abs}{117-fwcg07-xie-poster.ppt}" } -
W. Randolph Franklin and Metin Inanc. Compressing terrain datasets using segmentation. In Proceedings of SPIE Vol. 6313 Advanced Architectures, and Implementations XVI. San Diego CA, 15-16 August 2006. International Society for Optical Engineering. 6313-17, Session 4.
BibTeX
@InProceedings{wrf-mi-spie-2006, author = "Franklin, W. Randolph and Inanc, Metin", title = "Compressing terrain datasets using segmentation", booktitle = "Proceedings of {SPIE} Vol. 6313 Advanced Architectures, and Implementations {XVI}", year = "2006", month = "15-16 August", organization = "International Society for Optical Engineering", address = "San Diego CA", note = "6313-17, Session 4", abstract = "We propose a novel compression scheme to achieve lossless compression of elevation datasets. Our scheme does not use predictors in traditional sense. Predictors are based on dataset segments instead of the rows and columns processed so far. We believe that this is a far better way of expressing context in an image or elevation datasets since it can capture continuities in different geometries and is not limited to a subset of a pixel\textasciitilde s neighborhood. We compare the compression results of our scheme with that of JPEG-2000.", fulltext = "https://wrfranklin.org/p/112b-spie06-inanc.pdf", mykey = "terrain inanc", href = "\bibhref{112b-spie06-inanc}" } -
Metin Inanc and W Randolph Franklin. Terrain representation using tessellation of irregular planar tiles (extended abstract). In 16th Fall Workshop on Computational Geometry. Smith College, Northampton MA, 10-11 Nov 2006.
BibTeX
@InProceedings{inanc-fwcg-2006, author = "Inanc, Metin and Franklin, W Randolph", title = "Terrain Representation Using Tessellation of Irregular Planar Tiles (extended abstract)", booktitle = "16th Fall Workshop on Computational Geometry", year = "2006", month = "10-11 Nov", address = "Smith College, Northampton MA", fulltext = "https://wrfranklin.org/p/108-smith-fwcg06-tiles-inanc-abs.pdf", customlinkposter = "https://wrfranklin.org/p/108-smith-fwcg06-tiles-inanc-poster.jpg", href = "\bibhrefap{108-smith-fwcg06-tiles-inanc-abs}{108-smith-fwcg06-tiles-inanc-poster.jpg}", mykey = "inanc terrain" } -
W. Randolph Franklin, Metin Inanc, and Zhongyi Xie. Two novel surface representation techniques. In Autocarto 2006. Vancouver Washington, 25-28 June 2006. Cartography and Geographic Information Society, \url https://cartogis.org/autocarto/autocarto-2006/.
BibTeX
@InProceedings{wrf-autocarto-2006, author = "Franklin, W. Randolph and Inanc, Metin and Xie, Zhongyi", title = "Two novel surface representation techniques", booktitle = "Autocarto 2006", year = "2006", address = "Vancouver Washington", month = "25-28 June", organization = "Cartography and Geographic Information Society, \url{https://cartogis.org/autocarto/autocarto-2006/}", fulltext = "https://wrfranklin.org/p/111-vancouverwa-autocarto06-twonovel.pdf", mykey = "inanc xie terrain", href = "\bibhref{111-vancouverwa-autocarto06-twonovel}" } -
W. Randolph Franklin. Applications of analytical cartography. Cartography and Geographic Information Systems, 27(3):225–237, 2000.
BibTeX
@Article{wrf-cagis-00, author = "Franklin, W. Randolph", title = "Applications of Analytical Cartography", journal = "Cartography and Geographic Information Systems", year = "2000", volume = "27", number = "3", pages = "225-237", fulltext = "https://wrfranklin.org/p/94-cagis00-gisapps.pdf", href = "\bibhref{94-cagis00-gisapps}" } -
W. Randolph Franklin. Compressing elevation data. In Fourth International Symposium on Large Spatial Databases — SSD '95. Portland, Maine, USA, 6–9 Aug 1995.
BibTeX
@InProceedings{wrfelev95, author = "Franklin, W. Randolph", title = "Compressing Elevation Data", booktitle = "Fourth International Symposium on Large Spatial Databases --- {SSD} '95", year = "1995", publisher = "Portland, Maine, USA", month = "6--9 Aug", fulltext = "https://wrfranklin.org/p/86-ssd95-compress.pdf", href = "\bibhref{86-ssd95-compress}" } -
Original bibliography reference:
wrf-icip(record not found in the supplied bibliographies). -
W. Randolph Franklin and Amir Said. Lossy compression of elevation data. In Seventh International Symposium on Spatial Data Handling, 8B29ff. Delft, August 1996.
BibTeX
@inproceedings{wrflossy, author = "Franklin, W. Randolph and Said, Amir", title = "Lossy Compression of Elevation Data", booktitle = "Seventh International Symposium on Spatial Data Handling", address = "Delft", year = "1996", month = "August", pages = "8B29ff", fulltext = "https://wrfranklin.org/p/87-delft96-lossy.pdf", href = "\bibhref{87-delft96-lossy}" }
Parallel and distributed cartography computation
Publications include:
-
W. Randolph Franklin, You Li, Tsz-Yam Lau, and Peter Fox. CUDA-accelerated HD-ODETLAP: lossy high dimensional gridded data compression. In 2012 International Workshop on Modern Accelerator Technologies for GIScience (MAT4GIScience 2012). Columbus OH, 18 Sep 2012.
BibTeX
@InProceedings{giscience-hdodetlap-2012, author = "Franklin, W. Randolph and Li, You and Lau, Tsz-Yam and Fox, Peter", title = "{CUDA}-accelerated {HD-ODETLAP}: Lossy high dimensional gridded data compression", booktitle = "2012 International Workshop on Modern Accelerator Technologies for {GIScience} ({MAT4GIScience} 2012)", year = "2012", address = "Columbus OH", month = "18 Sep", mykey = "youli lau odetlap", fulltext = "https://wrfranklin.org/p/156-mat4giscience2012-hdodetlap.pdf", customlinkslides = "https://wrfranklin.org/p/156-mat4giscience2012-hdodetlap-talk.pdf", href = "\bibhrefpt{156-mat4giscience2012-hdodetlap}{156-mat4giscience2012-hdodetlap-talk.pdf}" } -
Jared Stookey, Zhongyi Xie, Barbara Cutler, W. Randolph Franklin, Daniel M. Tracy, and Marcus V.A. Andrade. Parallel ODETLAP for terrain compression and reconstruction. In Walid G. Aref, editor, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). 5–7 Nov 2008. URL: http://acmgis08.cs.umn.edu/.
BibTeX
@InProceedings{stookey-acmgis-2008, author = "Stookey, Jared and Xie, Zhongyi and Cutler, Barbara and Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus V.A.", editor = "Aref, Walid G.", title = "Parallel {ODETLAP} for terrain compression and reconstruction", booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)", year = "2008", location = "Irvine CA", month = "5--7 Nov", href = "\bibhrefptp{123-acmgis2008-stookey}{123-acmgis2008-stookey-talk.ppt}{123-acmgis2008-stookey-poster.ppt}", url = "http://acmgis08.cs.umn.edu/", fulltext = "https://wrfranklin.org/p/123-acmgis2008-stookey.pdf", customlinkslides = "https://wrfranklin.org/p/123-acmgis2008-stookey-talkb.pdf", customlinkposter = "https://wrfranklin.org/p/123-acmgis2008-stookey-poster.ppt", mykey = "odetlap tracy marcus xie stuetzle parallel", abstract = "We introduce a parallel approximation of an Over-determined Laplacian Partial Differential Equation solver (ODETLAP) applied to the compression and restoration of terrain data used for Geographical Information Systems (GIS). ODETLAP can be used to reconstruct a compressed elevation map, or to generate a dense regular grid from airborne Light Detection and Ranging (LIDAR) point cloud data. With previous methods, the time to execute ODETLAP does not scale well with the size of the input elevation map, resulting in running times that are prohibitively long for large data sets. Our algorithm divides the data set into patches, runs ODETLAP on each patch, and then merges the patches together. This method gives two distinct speed improvements. First, we provide scalability by reducing the complexity such that the execution time grows almost linearly with the size of the input, even when run on a single processor. Second, we are able to calculate ODETLAP on the patches concurrently in a parallel or distributed environment. Our new patchbased implementation takes 2 seconds to run ODETLAP on an 800 × 800 elevation map using 128 processors, while the original version of ODETLAP takes nearly 10 minutes on a single processor (271 times longer). We demonstrate the effectiveness of the new algorithm by running it on data sets as large as 16000 × 16000 on a cluster of computers. We also discuss our preliminary results from running on an IBM Blue Gene/L system with 32,768 processors." } -
Wm Randolph Franklin. Map overlay area animation and parallel simulation. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop, 200–203. July 28–August 2 1992.
BibTeX
@InProceedings{f-moaap-92, author = "Franklin, Wm Randolph", editor = "Douglas, David H.", title = "Map Overlay Area Animation and Parallel Simulation", booktitle = "Proceedings, SORSA'92 Symposium and Workshop", year = "1992", month = "July 28--August 2", pages = "200--203", fulltext = "https://wrfranklin.org/p/79-sorsa92-overlay.pdf", href = "\bibhref{79-sorsa92-overlay}", mykey = "overlay", keywords = "parallel computation, intersection, area" } -
Jared Stookey, Zhongyi Xie, Barbara Cutler, W. Randolph Franklin, Daniel M. Tracy, and Marcus V.A. Andrade. Parallel ODETLAP for terrain compression and reconstruction. In Walid G. Aref, editor, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). 5–7 Nov 2008. URL: http://acmgis08.cs.umn.edu/.
BibTeX
@InProceedings{stookey-acmgis-2008, author = "Stookey, Jared and Xie, Zhongyi and Cutler, Barbara and Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus V.A.", editor = "Aref, Walid G.", title = "Parallel {ODETLAP} for terrain compression and reconstruction", booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)", year = "2008", location = "Irvine CA", month = "5--7 Nov", href = "\bibhrefptp{123-acmgis2008-stookey}{123-acmgis2008-stookey-talk.ppt}{123-acmgis2008-stookey-poster.ppt}", url = "http://acmgis08.cs.umn.edu/", fulltext = "https://wrfranklin.org/p/123-acmgis2008-stookey.pdf", customlinkslides = "https://wrfranklin.org/p/123-acmgis2008-stookey-talkb.pdf", customlinkposter = "https://wrfranklin.org/p/123-acmgis2008-stookey-poster.ppt", mykey = "odetlap tracy marcus xie stuetzle parallel", abstract = "We introduce a parallel approximation of an Over-determined Laplacian Partial Differential Equation solver (ODETLAP) applied to the compression and restoration of terrain data used for Geographical Information Systems (GIS). ODETLAP can be used to reconstruct a compressed elevation map, or to generate a dense regular grid from airborne Light Detection and Ranging (LIDAR) point cloud data. With previous methods, the time to execute ODETLAP does not scale well with the size of the input elevation map, resulting in running times that are prohibitively long for large data sets. Our algorithm divides the data set into patches, runs ODETLAP on each patch, and then merges the patches together. This method gives two distinct speed improvements. First, we provide scalability by reducing the complexity such that the execution time grows almost linearly with the size of the input, even when run on a single processor. Second, we are able to calculate ODETLAP on the patches concurrently in a parallel or distributed environment. Our new patchbased implementation takes 2 seconds to run ODETLAP on an 800 × 800 elevation map using 128 processors, while the original version of ODETLAP takes nearly 10 minutes on a single processor (271 times longer). We demonstrate the effectiveness of the new algorithm by running it on data sets as large as 16000 × 16000 on a cluster of computers. We also discuss our preliminary results from running on an IBM Blue Gene/L system with 32,768 processors." }
See also the parallel geometry papers below.
Hydrography, bathymetry
Publications include:
-
Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Guilherme C. Pena. A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain. In Jérome Gensel, Didier Josselin, and Danny Vandenbroucke, editors, Bridging the Geographic Information Sciences: International AGILE'2012 Conference, pages 391–407. Springer, Avignon (France), 24–27 April 2012. URL: http://agile2012.imag.fr/.
BibTeX
@InCollection{salles-agile-2012, author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Pena, Guilherme C.", editor = "Gensel, Jérome and Josselin, Didier and Vandenbroucke, Danny", title = "A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain", booktitle = "Bridging the Geographic Information Sciences: International {AGILE'2012} Conference", publisher = "Springer", pages = "391--407", isbn = "978-3-642-29062-6", year = "2012", address = "Avignon (France)", month = "24--27 April", note = "Winner of the Best Paper Award (2nd place)", url = "http://agile2012.imag.fr/", fulltext = "https://wrfranklin.org/p/151-agile2012-rwflood.pdf", customlinkslides = "https://wrfranklin.org/p/151-agile2012-rwflood-talk.pdf", href = "\bibhrefpt{151-agile2012-rwflood}{151-agile2012-rwflood-talk.pdf}", mykey = "salles marcus hydro rwflood sallesagile2012" } -
Tsz-Yam Lau and W. Randolph Franklin. Improving river network completion under absence of height samples using geometry-based induced terrain approach. In 2012 AutoCarto International Symposium on Automated Cartography. Columbus OH, 16–18 Sep 2012.
BibTeX
@InProceedings{lau-autocarto-2012, author = "Lau, Tsz-Yam and Franklin, W. Randolph", title = "Improving river network completion under absence of height samples using geometry-based induced terrain approach", booktitle = "2012 AutoCarto International Symposium on Automated Cartography", year = "2012", address = "Columbus OH", month = "16--18 Sep", fulltext = "https://wrfranklin.org/p/154-autocarto2012-better-completion.pdf", customlinkslides = "https://wrfranklin.org/p/154-autocarto2012-better-completion-talk.pptx", href = "\bibhrefpt{154-autocarto2012-better-completion}{154-autocarto2012-better-completion-talk.pptx}", mykey = "lau hydro" } -
Tsz-Yam Lau and W. Randolph Franklin. Better completion of fragmentary river networks with the induced terrain approach by using known non-river locations. In 15th International Symposium on Spatial Data Handling. Bonn, Germany, 22–24 Aug 2012.
BibTeX
@InProceedings{lau-sdh-2012, author = "Lau, Tsz-Yam and Franklin, W. Randolph", title = "Better completion of fragmentary river networks with the induced terrain approach by using known non-river locations", booktitle = "15th International Symposium on Spatial Data Handling", year = "2012", address = "Bonn, Germany", month = "22--24 Aug", fulltext = "https://wrfranklin.org/p/157-sdh2012-completion.pdf", customlinkslides = "https://wrfranklin.org/p/157-sdh2012-completion-talk.ppt", mykey = "lau hydro", href = "\bibhrefpt{157-sdh2012-completion}{157-sdh2012-completion-talk.ppt}" } -
Tsz-Yam Lau, You Li, and W. Randolph Franklin. Joining fragmentary river segments with elevations and water flow directions using induced terrain (extended abstract). In 21st Fall Workshop on Computational Geometry. City College, New York City, USA, 4–5 Nov 2011.
BibTeX
@InProceedings{lau-fwcg-2011, author = "Lau, Tsz-Yam and Li, You and Franklin, W. Randolph", title = "Joining fragmentary river segments with elevations and water flow directions using induced terrain (extended abstract)", booktitle = "21st Fall Workshop on Computational Geometry", year = "2011", month = "4--5 Nov", address = "City College, New York City, USA", fulltext = "https://wrfranklin.org/p/150-fwcg2011-lau.pdf", mykey = "youli lau hydro", href = "\bibhref{150-fwcg2011-lau}" } -
Christopher Stuetzle, Barbara Cutler, Zhongxian Chen, W. Randolph Franklin, Mehrad Kamalzare, and Thomas Zimmie. Ph.d. showcase: measuring terrain distances through extracted channel networks. In 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2011). Chicago USA, 1–4 Nov 2011.
BibTeX
@InProceedings{stuetzle-acmgis-2011, author = "Stuetzle, Christopher and Cutler, Barbara and Chen, Zhongxian and Franklin, W. Randolph and Kamalzare, Mehrad and Zimmie, Thomas", title = "Ph.D. showcase: Measuring terrain distances through extracted channel networks", booktitle = "19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2011)", year = "2011", month = "1--4 Nov", address = "Chicago USA", mykey = "terrain stuetzle levee", href = "\bibhrefpp{149-acmgis2011-stuetzle}{149-acmgis2011-stuetzle-poster.pdf}", fulltext = "https://wrfranklin.org/p/149-acmgis2011-stuetzle.pdf", customlinkposter = "https://wrfranklin.org/p/149-acmgis2011-stuetzle-poster.pdf" } -
Tsz-Yam Lau and W. Randolph Franklin. Completing fragmentary river networks via induced terrain. Cartography and Geographic Information Science, 38(2):162–174, April 2011. URL: https://www.tandfonline.com/doi/abs/10.1559/15230406382161a, doi:https://doi.org/10.1559/15230406382161a.
BibTeX
@Article{lau-cagis-2011, author = "Lau, Tsz-Yam and Franklin, W. Randolph", title = "Completing fragmentary river networks via induced terrain", journal = "Cartography and Geographic Information Science", year = "2011", month = "April", pages = "162-174", volume = "38", number = "2", doi = "https://doi.org/10.1559/15230406382161a", url = "https://www.tandfonline.com/doi/abs/10.1559/15230406382161a", mykey = "lau hydro", fulltext = "https://wrfranklin.org/p/147-cagis-hydro-lau.pdf", abstract = "Fragmentary river segments have to be reconnected before addressing various routing and tracking problems. Elevation determines drainage directions, so the partial heights available through LiDAR may provide useful hints on how the segments should be joined. However, it is not trivial how this information can be applied. This paper bridges this gap by proposing the induced structure approach, which first approximates a terrain compatible with those observations, and then derives a river network from that induced terrain. Since the network is derived from an induced terrain that honors the partial observations, we expect that the derived river network will enforce most restrictions imposed by the partial observations. This paper also provides specifics on the implementation. In the first step regarding terrain reconstruction, we find that the optimal scheme depends on the height sample distribution. If the samples are sparsely yet evenly distributed, natural neighbor interpolation with stream burning (NN-SB) is the most cost-effective. If the samples are offered only at the given river locations, the hydrology-aware version of Over determined Palladian Partial Differential Equation (HA-ODETLAP) should be used instead. In the second step concerning river derivation, we find it necessary to favor those given river locations. Otherwise they will be missed out. We set their respective initial water amounts to the critical accumulation level to ensure a river flows across them. In the subsequent branch thinning process, those locations are protected from being trimmed. We foresee applications of our solution framework in a few 2D and 3D network tracing problems with similar observation distribution, like dendrite network reconstruction.", href = "\bibhref{147-cagis-hydro-lau}" } -
Tsz-Yam Lau and W. Randolph Franklin. Completing fragmentary river networks via induced terrain. In Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of ISPRS Technical Commission IV & AutoCarto 2010. Orlando, Florida, 15–18 Nov 2010.
BibTeX
@InProceedings{lau-autocarto-2010, author = "Lau, Tsz-Yam and Franklin, W. Randolph", title = "Completing fragmentary river networks via induced terrain", booktitle = "Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of {ISPRS} Technical Commission {IV} \\& {AutoCarto} 2010", year = "2010", address = "Orlando, Florida", month = "15--18 Nov", mykey = "lau hydro", fulltext = "https://wrfranklin.org/p/135-autocarto2010-lau.pdf", customlinkslides = "https://wrfranklin.org/p/135-autocarto2010-lau-talk.pptx", href = "\bibhrefpt{135-autocarto2010-lau}{135-autocarto2010-lau-talk.pptx}" } -
Tsz-Yam Lau and W. Randolph Franklin. Completing river networks with only partial river observations via hydrology-aware ODETLAP. In 20th Annual Fall Workshop on Computational Geometry (FWCG 2010). Stony Brook University, Stony Brook, NY 11794, USA, 29–30 Oct 2010. (extended abstract and talk).
BibTeX
@InProceedings{lau-fwcg-2010, author = "Lau, Tsz-Yam and Franklin, W. Randolph", title = "Completing River Networks with Only Partial River Observations via Hydrology-Aware {ODETLAP}", booktitle = "20th Annual Fall Workshop on Computational Geometry ({FWCG} 2010)", month = "29--30 Oct", year = "2010", note = "(extended abstract and talk)", mykey = "lau hydro odetlap", address = "Stony Brook University, Stony Brook, NY 11794, USA", fulltext = "https://wrfranklin.org/p/138-fwcg2010-lau.pdf", customlinkslides = "https://wrfranklin.org/p/138-fwcg2010-lau-talk.pdf", href = "\bibhrefat{138-fwcg2010-lau}{138-fwcg2010-lau-talk.pdf}" } -
You Li, Tsz-Yam Lau, Chris Stuetzle, Peter Fox, and W. Randolph Franklin. 3D oceanographic data compression using 3D-ODETLAP. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010). San Jose, CA, USA, 2–5 Nov 2010. (PhD Dissertation showcase).
BibTeX
@InProceedings{li-acmgis-2010, author = "Li, You and Lau, Tsz-Yam and Stuetzle, Chris and Fox, Peter and Franklin, W. Randolph", title = "{3D} oceanographic data compression using {3D-ODETLAP}", booktitle = "18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010)", year = "2010", month = "2--5 Nov", mykey = "youli odetlap lau stuetzle", address = "San Jose, CA, USA", fulltext = "https://wrfranklin.org/p/139-acmgis2010-li.pdf", customlinkslides = "https://wrfranklin.org/p/139-acmgis2010-li-talk.pptx", href = "\bibhrefpt{139-acmgis2010-li}{139-acmgis2010-li-talk.pptx}", note = "(PhD Dissertation showcase)" } -
W. Randolph Franklin, Zhongyi Xie, Eddie Lau, and You Li. Algorithms for terrain and bathymetric sensor data. In ICA Workshop on Advances in Sensors and Algorithms for Topographic and Thematic Mapping. Orlando, Florida, 19 Nov 2010. The International Cartographic Association (ICA) Commission on Mapping from Satellite Imagery.
BibTeX
@InProceedings{ica-2010, author = "Franklin, W. Randolph and Xie, Zhongyi and Lau, Eddie and Li, You", title = "Algorithms for terrain and bathymetric sensor data", booktitle = "{ICA} Workshop on Advances in Sensors and Algorithms for Topographic and Thematic Mapping", year = "2010", address = "Orlando, Florida", month = "19 Nov", organization = "The {International} Cartographic Association {(ICA)} Commission on Mapping from Satellite Imagery", fulltext = "https://wrfranklin.org/p/143-orlando-ica-sensors-2010.pdf", customlinkslides = "https://wrfranklin.org/p/143-orlando-ica-sensors-2010-talk.pdf", mykey = "xie youli lau bathy", href = "\bibhrefpt{143-orlando-ica-sensors-2010}{143-orlando-ica-sensors-2010-talk.pdf}" } -
Tsz-Yam Lau, You Li, Zhongyi Xie, and W. Randolph Franklin. Sea floor bathymetry trackline surface fitting without visible artifacts using ODETLAP. In 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009). Seattle WA USA, 4–6 Nov 2009. Winner of the best fast forward presentation award.
BibTeX
@InProceedings{lau-acmgis-2009, author = "Lau, Tsz-Yam and Li, You and Xie, Zhongyi and Franklin, W. Randolph", title = "Sea Floor Bathymetry Trackline Surface Fitting Without Visible Artifacts Using {ODETLAP}", booktitle = "17th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM SIGSPATIAL GIS} 2009)", year = "2009", address = "Seattle WA USA", month = "4--6 Nov", note = "Winner of the best fast forward presentation award", fulltext = "https://wrfranklin.org/p/129-acmgis2009-lau.pdf", customlinkslides = "https://wrfranklin.org/p/129-acmgis2009-lau-talk.pdf", customlinkposter = "https://wrfranklin.org/p/129-acmgis2009-lau-poster.pdf", customlinkvideo = "https://wrfranklin.org/p/129-acmgis2009-lau-video.avi", customlinkaward = "https://wrfranklin.org/p/129-acmgis2009-lau-ffaward.jpg", href = "\bibhrefpttppv{129-acmgis2009-lau}", mykey = "xie youli odetlap bathy lauacmgis2009" } -
Jared Stookey, Zhongyi Xie, Barbara Cutler, W. Randolph Franklin, Daniel M. Tracy, and Marcus V.A. Andrade. Parallel ODETLAP for terrain compression and reconstruction. In Walid G. Aref, editor, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). 5–7 Nov 2008. URL: http://acmgis08.cs.umn.edu/.
BibTeX
@InProceedings{stookey-acmgis-2008, author = "Stookey, Jared and Xie, Zhongyi and Cutler, Barbara and Franklin, W. Randolph and Tracy, Daniel M. and Andrade, Marcus V.A.", editor = "Aref, Walid G.", title = "Parallel {ODETLAP} for terrain compression and reconstruction", booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)", year = "2008", location = "Irvine CA", month = "5--7 Nov", href = "\bibhrefptp{123-acmgis2008-stookey}{123-acmgis2008-stookey-talk.ppt}{123-acmgis2008-stookey-poster.ppt}", url = "http://acmgis08.cs.umn.edu/", fulltext = "https://wrfranklin.org/p/123-acmgis2008-stookey.pdf", customlinkslides = "https://wrfranklin.org/p/123-acmgis2008-stookey-talkb.pdf", customlinkposter = "https://wrfranklin.org/p/123-acmgis2008-stookey-poster.ppt", mykey = "odetlap tracy marcus xie stuetzle parallel", abstract = "We introduce a parallel approximation of an Over-determined Laplacian Partial Differential Equation solver (ODETLAP) applied to the compression and restoration of terrain data used for Geographical Information Systems (GIS). ODETLAP can be used to reconstruct a compressed elevation map, or to generate a dense regular grid from airborne Light Detection and Ranging (LIDAR) point cloud data. With previous methods, the time to execute ODETLAP does not scale well with the size of the input elevation map, resulting in running times that are prohibitively long for large data sets. Our algorithm divides the data set into patches, runs ODETLAP on each patch, and then merges the patches together. This method gives two distinct speed improvements. First, we provide scalability by reducing the complexity such that the execution time grows almost linearly with the size of the input, even when run on a single processor. Second, we are able to calculate ODETLAP on the patches concurrently in a parallel or distributed environment. Our new patchbased implementation takes 2 seconds to run ODETLAP on an 800 × 800 elevation map using 128 processors, while the original version of ODETLAP takes nearly 10 minutes on a single processor (271 times longer). We demonstrate the effectiveness of the new algorithm by running it on data sets as large as 16000 × 16000 on a cluster of computers. We also discuss our preliminary results from running on an IBM Blue Gene/L system with 32,768 processors." } -
Jonathan Muckell, Marcus Andrade, W. Randolph Franklin, Barbara Cutler, Metin Inanc, Zhongyi Xie, and Daniel M. Tracy. Drainage network and watershed reconstruction on simplified terrain. In 17th Fall Workshop on Computational Geometry. IBM TJ Watson Research Center, Hawthorne NY, 2–3 Nov 2007. poster session, no formal proceedings.
BibTeX
@InProceedings{muckell-fwcg-2007, author = "Muckell, Jonathan and Andrade, Marcus and Franklin, W. Randolph and Cutler, Barbara and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M.", title = "Drainage network and watershed reconstruction on simplified terrain", booktitle = "17th Fall Workshop on Computational Geometry", month = "2--3 Nov", year = "2007", note = "poster session, no formal proceedings", address = "IBM TJ Watson Research Center, Hawthorne NY", fulltext = "https://wrfranklin.org/p/116-fwcg07-muckell-abs.pdf", customlinkslides = "https://wrfranklin.org/p/116-fwcg07-muckell-poster.ppt", mykey = "tracy marcus inanc muckell xie hydro", href = "\bibhrefap{116-fwcg07-muckell-abs}{116-fwcg07-muckell-poster.ppt}" }
Erosion modeling
Publications include:
-
Mehrad Kamalzare, Christopher Stuetzle, Zhongxian Chen, Thomas F. Zimmie, Barbara Cutler, and W. Randolph Franklin. Validation of erosion modeling: physical and numerical. In Geo-Congress 2012: Annual congress of the geo-institute of ASCE. Oakland, California, USA, 25–29 Mar 2012. \url http://www.geocongress2012.org/.
BibTeX
@InProceedings{kalamzare-geo-2012, author = "Kamalzare, Mehrad and Stuetzle, Christopher and Chen, Zhongxian and Zimmie, Thomas F. and Cutler, Barbara and Franklin, W. Randolph", title = "Validation of erosion modeling: physical and numerical", booktitle = "Geo-Congress 2012: Annual congress of the geo-institute of {ASCE}", year = "2012", address = "Oakland, California, USA", month = "25--29 Mar", note = "\url{http://www.geocongress2012.org/}", fulltext = "https://wrfranklin.org/p/152-geocongress2012.pdf", mykey = "levee stuetzle", href = "\bibhref{152-geocongress2012}" } -
Mehrad Kamalzare, Zhongxian Chen, Christopher Stuetzle, Barbara Cutler, W. Randolph Franklin, and Thomas F. Zimmie. Computer simulation of overtopping of levees. In 2011 Pam-Am CGS Geotechnical Conference: 14th Pan-American Conference on Soil Mechanics and Geotechnical Engineering. Toronto, 2–6 Oct 2011. URL: http://www.panam-cgc2011.ca/.
BibTeX
@InProceedings{panam-2011, author = "Kamalzare, Mehrad and Chen, Zhongxian and Stuetzle, Christopher and Cutler, Barbara and Franklin, W. Randolph and Zimmie, Thomas F.", title = "Computer simulation of overtopping of levees", booktitle = "2011 {Pam-Am} {CGS} Geotechnical Conference: 14th Pan-American Conference on Soil Mechanics and Geotechnical Engineering", month = "2--6 Oct", year = "2011", address = "Toronto", url = "http://www.panam-cgc2011.ca/", fulltext = "https://wrfranklin.org/p/146-panam-levees.pdf", mykey = "levee stuetzle", href = "\bibhref{146-panam-levees}" } -
Zhongxian Chen, Christopher S. Stuetzle, Barbara M. Cutler, Jared A. Gross, W. Randolph Franklin, and Thomas F. Zimmie. Analyses, simulations and physical modeling validation of levee and embankment erosion. In Geo-Frontiers 2011: Advances in geotechnical engineering. Dallas TX, 13–16 Mar 2011. URL: http://www.geofrontiers11.com/.
BibTeX
@InProceedings{chen-geofrontiers-2011, author = "Chen, Zhongxian and Stuetzle, Christopher S. and Cutler, Barbara M. and Gross, Jared A. and Franklin, W. Randolph and Zimmie, Thomas F.", title = "Analyses, Simulations and Physical Modeling Validation of Levee and Embankment Erosion", booktitle = "Geo-Frontiers 2011: Advances in geotechnical engineering", year = "2011", address = "Dallas TX", month = "13--16 Mar", fulltext = "https://wrfranklin.org/p/141-geofrontiers2011-analyses-chen.pdf", href = "\bibhref{141-geofrontiers2011-analyses-chen}", mykey = "levee stuetzle", url = "http://www.geofrontiers11.com/" } -
Jared A. Gross, Christopher S. Stuetzle, Zhongxian Chen, Barbara Cutler, W. Randolph Franklin, and Thomas F. Zimmie. Simulating levee erosion with physical modeling validation. In ICSE-5 5th international conference on scour and erosion. San Francisco, 7–10 Nov 2010.
BibTeX
@InProceedings{gross-icse-2010, author = "Gross, Jared A. and Stuetzle, Christopher S. and Chen, Zhongxian and Cutler, Barbara and Franklin, W. Randolph and Zimmie, Thomas F.", title = "Simulating levee erosion with physical modeling validation", booktitle = "{ICSE-5} 5th international conference on scour and erosion", year = "2010", address = "San Francisco", month = "7--10 Nov", fulltext = "https://wrfranklin.org/p/134-icse2010-gross.pdf", customlinkslides = "https://wrfranklin.org/p/134-icse2010-gross-talk.ps", href = "\bibhrefpt{134-icse2010-gross}{134-icse2010-gross-talk.ps}", mykey = "levee stuetzle" } -
Zhongxian Chen, Christopher Stuetzle, Barbara Cutler, Jared Gross, W. Randolph Franklin, and Thomas Zimmie. Quantitative analysis of simulated erosion for different soils. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010). San Jose, CA, USA, 2–5 Nov 2010. (poster).
BibTeX
@InProceedings{chen-acmgis-2010, author = "Chen, Zhongxian and Stuetzle, Christopher and Cutler, Barbara and Gross, Jared and Franklin, W. Randolph and Zimmie, Thomas", title = "Quantitative analysis of simulated erosion for different soils", booktitle = "18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010)", year = "2010", month = "2--5 Nov", address = "San Jose, CA, USA", href = "\bibhrefpp{137-acmgis2010-chen}{137-acmgis2010-chen-poster.pdf}", fulltext = "https://wrfranklin.org/p/137-acmgis2010-chen.pdf", customlinkposter = "https://wrfranklin.org/p/137-acmgis2010-chen-poster.pdf", mykey = "levee stuetzle", note = "(poster)" } -
Christopher S. Stuetzle, Zhongxian Chen, Barbara Cutler, W. Randolph Franklin, Jared Gross, Katrina Perez, and Thomas Zimmie. Computer simulations and physical modelling of erosion. In 7th International Conference on Physical Modelling in Geotechnics (ICPMG 2010). Zürich, 20–24 Jun 2010.
BibTeX
@InProceedings{stuetzle-icpmg-2010, author = "Stuetzle, Christopher S. and Chen, Zhongxian and Cutler, Barbara and Franklin, W. Randolph and Gross, Jared and Perez, Katrina and Zimmie, Thomas", title = "Computer simulations and physical modelling of erosion", booktitle = "7th International Conference on Physical Modelling in Geotechnics ({ICPMG} 2010)", year = "2010", address = "Zürich", fulltext = "https://wrfranklin.org/p/131-zurich2010-stuetzle.pdf", customlinkslides = "https://wrfranklin.org/p/131-zurich2010-stuetzle-talk.pdf", href = "\bibhrefpt{131-zurich2010-stuetzle}{131-zurich2010-stuetzle-talk.pdf}", mykey = "levee stuetzle", month = "20--24 Jun" } -
Christopher S. Stuetzle, Zhongxian Chen, Katrina Perez, Jared Gross, Barbara Cutler, W. Randolph Franklin, and Thomas Zimmie. Segmented height field and smoothed particle hydrodynamics in erosion simulation. In 19th Fall Workshop on Computational Geometry (FWCG 2009). Tufts University, Medford MA USA, 13–14 Nov 2009. (extended abstract and talk).
BibTeX
@InProceedings{stuetzle-fwcg-2009, author = "Stuetzle, Christopher S. and Chen, Zhongxian and Perez, Katrina and Gross, Jared and Cutler, Barbara and Franklin, W. Randolph and Zimmie, Thomas", title = "Segmented Height Field and Smoothed Particle Hydrodynamics in Erosion Simulation", booktitle = "19th Fall Workshop on Computational Geometry ({FWCG} 2009)", month = "13--14 Nov", year = "2009", note = "(extended abstract and talk)", address = "Tufts University, Medford MA USA", fulltext = "https://wrfranklin.org/p/130-fwcg2009-stuetzle.pdf", customlinkslides = "https://wrfranklin.org/p/130-fwcg2009-stuetzle-talk.pdf", href = "\bibhrefat{130-fwcg2009-stuetzle}{130-fwcg2009-stuetzle-talk.pdf}", mykey = "levee hydro stuetzle" }
More info: GeoStar
GeoStar
This major theme was a 2005-2009 DARPA-funded project for representing and operating on terrain, that is, elevation.
A good summary is this Geo* talk (7/2010), Videos in talk: 1, 2, 3.
Its accomplishments included:
- efficient hi–res visibility computation on terrain,
- multiple observer siting to maximize joint viewshed,
- ODETLAP, an extension of the Laplacian PDE to an overdetermined system of equations, which is used in many of the following results,
- extremely compact lossy terrain (elevation) compression,
- terrain compression that reconstructs slopes accurately,
- lossily compressed terrain supports motion-planning (path planning),
- path planning with sophisticated cost metric on large terrain, and
- a better surface fitting procedure for bathymetry data that is very unevenly spaced.
Publications on Geo* as a project include:
-
W. Randolph Franklin. The RPI GeoStar project. In Anne Ruas, editor, Proceedings of the 25th International Cartographic Conference. Paris, 3–8 July 2011. online, retrieved 26-Oct-13. URL: http://icaci.org/files/documents/ICC_proceedings/ICC2011/.
BibTeX
@InProceedings{icc-2011, author = "Franklin, W. Randolph", editor = "Ruas, Anne", title = "The {RPI} {GeoStar} project", booktitle = "Proceedings of the 25th International Cartographic Conference", year = "2011", address = "Paris", isbn = "978-1-907075-05-6", month = "3--8 July", url = "http://icaci.org/files/documents/ICC\_proceedings/ICC2011/", mykey = "geostar", note = "online, retrieved 26-Oct-13", fulltext = "https://wrfranklin.org/p/145-icc2011-geostar.pdf", customlinkslides = "https://wrfranklin.org/p/145-icc2011-geostar-talk.pdf", href = "\bibhrefpt{145-icc2011-geostar}{145-icc2011-geostar-talk.pdf}" }
In addition many other publications listed on this page present various aspects of Geo*.
More info: Siting
Visibility, Multi-observer siting, Path planning
The idea is to start with some terrain, i.e, elevation data, and then to place (site) a set of observers to oversee the terrain as well as possible. Previous work by other researchers has tended to compute the viewsheds of individual observers. Our work starts by computing higher resolution viewsheds than often computed elsewhere, and then extends the siting concept by choosing quasi-optimal sets of observers.
Even for single observer viewsheds, some counterintuitive results have been obtained. For example, for some terrain, there is no significant correlation between elevation and visibility index; on the average, higher is no better for observation. Publications include:
-
Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. Multiple observer siting in huge terrains stored in external memory. International Journal of Computer Information Systems and Industrial Management (IJCISIM), 2011.
BibTeX
@Article{magalhaes-ijcisim-2011, author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph", title = "Multiple Observer Siting in Huge Terrains Stored in External Memory", journal = "International Journal of Computer Information Systems and Industrial Management (IJCISIM)", year = "2011", volume = "3", issn = "2150-7988", fulltext = "https://wrfranklin.org/p/148-ijcisim11-emsite-magalhaes.pdf", href = "\bibhref{148-ijcisim11-emsite-magalhaes}", mykey = "visviewshedsiting marcus salles", abstract = "This paper presents an heuristic method to give an approximated solution to the observer siting problem on high resolution terrains that are too large to be processed in the internal memory. Informally, the problem is to determine an optimal positioning of as few as possible observers for being able to observe as many target points as possible. Tests have shown that the proposed heuristic can solve this problem using, on average, fifteen percent fewer observers than another heuristic described in the literature. This will permit more efficient positioning of facilities such as mobile phone towers, fire observation towers, and vigilance systems." } -
Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. An optimization heuristic for siting observers in huge terrains stored in external memory. In 10th International Conference on Hybrid Intelligent Systems (HIS 2010). Atlanta USA, 23–25 Aug 2010.
BibTeX
@InProceedings{magalhaes-his-2010, author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph", title = "An optimization heuristic for siting observers in huge terrains stored in external memory", booktitle = "10th International Conference on Hybrid Intelligent Systems ({HIS} 2010)", address = "Atlanta USA", month = "23--25 Aug", year = "2010", fulltext = "https://wrfranklin.org/p/132-atlanta-his10-emsite-magalhaes.pdf", href = "\bibhref{132-atlanta-his10-emsite-magalhaes}", mykey = "marcus salles" } -
Marcus V. A. Andrade, Salles V. G. de Magalhães, Mirella A. de Magalhães, W. Randolph Franklin, and Barbara M. Cutler. Efficient viewshed computation on terrain in external memory. Geoinformatica, 2010. (online 26 Nov 2009). URL: http://www.springerlink.com/content/p1783648185g1252/, doi:https://doi.org/10.1007/s10707-009-0100-9.
BibTeX
@Article{andrade-geoinfo-ext-viewshed-2008, author = "Andrade, Marcus V. A. and de Magalhães, Salles V. G. and de Magalhães, Mirella A. and Franklin, W. Randolph and Cutler, Barbara M.", title = "Efficient viewshed computation on terrain in external memory", journal = "Geoinformatica", year = "2010", fulltext = "https://wrfranklin.org/p/126-andrade-geoinfo-ext-viewshed-2008.pdf", href = "\bibhref{126-andrade-geoinfo-ext-viewshed-2008}", URL = "http://www.springerlink.com/content/p1783648185g1252/", DOI = "https://doi.org/10.1007/s10707-009-0100-9", mykey = "visviewshedsiting marcus salles", note = "(online 26 Nov 2009)", abstract = "The recent availability of detailed geographic data permits terrain applications to process large areas at high resolution. However the required massive data processing presents significant challenges, demanding algorithms optimized for bothdata movement and computation. One such application is viewshed computation,that is, to determine all the points visible from a given point p. In this paper, we present an efficient algorithm to compute viewsheds on terrain stored in external memory. In the usual case where the observer's radius of interest is smaller than the terrain size, the algorithm complexity is θ(scan(n2)) where n2 is the number of points in an n×n DEM and scan(n2)is the minimum number of I/O operations required to read n2 contiguous items from external memory. This is much faster than existing published algorithms." } -
Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Franklin T. Luk, Marcus Andrade, and Jared Stookey. Path planning on a compressed terrain. In Walid G. Aref and others, editors, 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008). Irvine CA, 5–7 Nov 2008. (poster and fast forward presentation). URL: http://acmgis08.cs.umn.edu/.
BibTeX
@InProceedings{tracy-acmgis-2008, author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Luk, Franklin T. and Andrade, Marcus and Stookey, Jared", editor = "Aref, Walid G. and others", title = "Path Planning on a Compressed Terrain", booktitle = "16th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems ({ACM GIS} 2008)", year = "2008", address = "Irvine CA", month = "5--7 Nov", fulltext = "https://wrfranklin.org/p/124-acmgis2008-tracy.pdf", customlinkslides = "https://wrfranklin.org/p/124-acmgis2008-tracy-talk.pdf", customlinkposter = "https://wrfranklin.org/p/124-acmgis2008-tracy-poster.pdf", mykey = "pathplan marcus tracy", href = "\bibhrefpttpp{124-acmgis2008-tracy}", note = "(poster and fast forward presentation)", url = "http://acmgis08.cs.umn.edu/" } -
W. Randolph Franklin. Operating on large geometric datasets. In 18th Fall Workshop on Computational Geometry. Rensselaer Polytechnic Institute, Troy NY, 31 Oct – 1 Nov 2008. (extended abstract and talk).
BibTeX
@InProceedings{wrf-fwcg-2008, author = "Franklin, W. Randolph", title = "Operating on large geometric datasets", booktitle = "18th Fall Workshop on Computational Geometry", month = "31 Oct -- 1 Nov", year = "2008", note = "(extended abstract and talk)", address = "Rensselaer Polytechnic Institute, Troy NY", fulltext = "https://wrfranklin.org/p/122-fwcg2008-big.pdf", customlinkslides = "https://wrfranklin.org/p/122-fwcg2008-big-talk.pdf", href = "\bibhrefat{122-fwcg2008-big}{122-fwcg2008-big-talk.pdf}" } -
Daniel M. Tracy, W Randolph Franklin, Barb Cutler, Franklin Luk, Marcus Andrade, and Jared Stookey. Path planning on complex terrain. In 18th Fall Workshop on Computational Geometry (FWCG 2008). Rensselaer Polytechnic Institute, Troy NY USA, 31 Oct – 1 Nov 2008. (extended abstract, talk and poster).
BibTeX
@InProceedings{tracy-fwcg-2008, author = "Tracy, Daniel M. and Franklin, W Randolph and Cutler, Barb and Luk, Franklin and Andrade, Marcus and Stookey, Jared", title = "Path Planning on Complex Terrain", booktitle = "18th Fall Workshop on Computational Geometry ({FWCG} 2008)", month = "31 Oct -- 1 Nov", year = "2008", note = "(extended abstract, talk and poster)", address = "Rensselaer Polytechnic Institute, Troy NY USA", fulltext = "https://wrfranklin.org/p/128-fwcg2008-tracy.pdf", customlinkslides = "https://wrfranklin.org/p/128-fwcg2008-tracy-talk.ppt", customlinkposter = "https://wrfranklin.org/p/128-fwcg2008-tracy-poster.ppt", mykey = "pathplan marcus tracy", href = "\bibhrefatp{128-fwcg2008-tracy}{128-fwcg2008-tracy-talk.ppt}{128-fwcg2008-tracy-poster.ppt}" } -
Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler, Marcus A Andrade, Franklin T Luk, Metin Inanc, and Zhongyi Xie. Multiple observer siting and path planning on lossily compressed terrain. In Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII. San Diego CA, 27 August 2007. International Society for Optical Engineering. paper 6697-16.
BibTeX
@InProceedings{dt-wrf-spie-2007, author = "Tracy, Daniel M. and Franklin, W. Randolph and Cutler, Barbara and Andrade, Marcus A and Luk, Franklin T and Inanc, Metin and Xie, Zhongyi", title = "Multiple observer siting and path planning on lossily compressed terrain", booktitle = "Proceedings of {SPIE} Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations {XVII}", year = "2007", month = "27 August", organization = "International Society for Optical Engineering", address = "San Diego CA", note = "paper 6697-16", mykey = "inanc tracy marcus xie pathplan visviewshedsiting", fulltext = "https://wrfranklin.org/p/114-spie07-tracy.pdf", href = "\bibhref{114-spie07-tracy}", abstract = "We examine a smugglers and border guards scenario. We place observers on a terrain so as to optimize their visible coverage area. Then we compute a path that a smuggler would take so as to avoid detection, while also minimizing the path length. We also examine how our results are affected by using a lossy representation of the terrain instead. We propose three new application-specific error metrics for evaluating terrain compression. Our target terrain applications are the optimal placement of observers on a landscape and the navigation through the terrain by smugglers. Instead of using standard metrics such as average or maximum elevation error, we seek to optimize our compression on the specific real-world application of smugglers and border guards." } -
W Randolph Franklin, Metin Inanc, Zhongyi Xie, Daniel M. Tracy, Barbara Cutler, Marcus V A Andrade, and Franklin Luk. Smugglers and border guards – the GeoStar project at RPI. In 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007). Seattle, WA, USA, Nov 2007.
BibTeX
@InProceedings{acmgis07, author = "Franklin, W Randolph and Inanc, Metin and Xie, Zhongyi and Tracy, Daniel M. and Cutler, Barbara and Andrade, Marcus V A and Luk, Franklin", title = "Smugglers and border guards -- the {GeoStar} project at {RPI}", booktitle = "15th {ACM} International Symposium on Advances in Geographic Information Systems {(ACM GIS 2007)}", year = "2007", address = "Seattle, WA, USA", month = "Nov", fulltext = "https://wrfranklin.org/p/115-seattle07-acmgis-smugglers.pdf", customlinkslides = "https://wrfranklin.org/p/115-seattle07-acmgis-smugglers-talk.ppt", mykey = "pathplan visviewshedsiting marcus tracy inanc xie", href = "\bibhrefpt{115-seattle07-acmgis-smugglers}{115-seattle07-acmgis-smugglers-talk.ppt}", abstract = "We present the GeoStar project at RPI, which researches various terrain (i.e., elevation) representations and operations thereon. This work is motivated by the large amounts of hi-res data now available. The purpose of each representation is to lossily compress terrain while maintaining important properties. Our ODETLAP representation generalizes a Laplacian partial differential equation by using two inconsistent equations for each known point in the grid, as well as one equation for each unknown point. The surface is reconstructed from a carefully chosen small set of known points. Our second representation segments the terrain intoa set of regions, each of which is simply described. Our third representation has the most long term potential: scooping, which forms the terrain by emulating surface water erosion. Siting hundreds of observers, such as border guards, so that their viewsheds jointly cover the maximum terrain is our first operation. This process allows both observer and target to be above the local terrain, and the observer to have a finite radius of interest. Planning a path so that a smuggler may get from point A to point B while maximally avoiding the border guards is our second operation. The path metric includes path length, distance traveled uphill,and amount of time visible to a guard. The quality of our representations is determined, not only by their RMS elevation error, but by how accurately they support these operations." } -
W. Randolph Franklin and Christian Vogt. Tradeoffs when multiple observer siting on large terrain cells. In Andreas Riedl, Wolfgang Kainz, and Gregory Elmes, editors, Progress in Spatial Data Handling: 12th International Symposium on Spatial Data Handling, pages 845–861. Springer, Vienna, 2006.
BibTeX
@InCollection{wrf-sdh2006, author = "Franklin, W. Randolph and Vogt, Christian", editor = "Riedl, Andreas and Kainz, Wolfgang and Elmes, Gregory", title = "Tradeoffs when multiple observer siting on large terrain cells", booktitle = "Progress in Spatial Data Handling: 12th International Symposium on Spatial Data Handling", pages = "845--861", publisher = "Springer", year = "2006", note = "ISBN 978-3-540-35588-5", address = "Vienna", mykey = "visviewshedsiting", fulltext = "https://wrfranklin.org/p/112-sdh06-vienna-siting-tradeoffs.pdf", customlinkslides = "https://wrfranklin.org/p/112-sdh06-vienna-siting-tradeoffs-talk.ppt", href = "\bibhrefpt{112-sdh06-vienna-siting-tradeoffs}{112-sdh06-vienna-siting-tradeoffs-talk.ppt}" } -
W. Randolph Franklin and Christian Vogt. Multiple observer siting on terrain with intervisibility or lo-res data. In XXth Congress, International Society for Photogrammetry and Remote Sensing. Istanbul, 12-23 July 2004.
BibTeX
@InProceedings{wrf-cv-siting-isprs, author = "Franklin, W. Randolph and Vogt, Christian", title = "Multiple observer siting on terrain with intervisibility or lo-res data", booktitle = "{XX}th Congress, International Society for Photogrammetry and Remote Sensing", year = "2004", address = "Istanbul", month = "12-23 July", fulltext = "https://wrfranklin.org/p/100-istanbul-isprs04-siting.pdf", customlinkposter = "https://wrfranklin.org/p/100-istanbul-isprs04-siting-poster.pdf", mykey = "visviewshedsiting", href = "\bibhrefpp{100-istanbul-isprs04-siting}{100-istanbul-isprs04-siting-poster.jpg}", abstract = "We describe two current projects with our toolkit for siting multiple observers on terrain. (Both observers and targets are at some specified height above ground level. Observers can see targets, when not hidden by the terrain, out to a specified radius of interest.) Siting the observers so that they are intervisible, i.e., so that the visibility graph is a connected set, is the first project. The second project tests the effect, on the optimality of the multiple observer siting (w/o intervisiblity), of reducing the map cell's horizontal or vertical resolution. We lowered the resolution, sited observers optimally, then computed those observers' joint visibility index on the hi-res data. We observed that much less precise vertical resolution is ok, but that reducing the horizontal resolution by even a factor of two leads to an observer siting with significantly reduced joint visibility index, when evaluated on the hi-res data. Applications of multiple observer siting include siting radio towers and mitigating visual nuisances." } -
W. Randolph Franklin and Christian Vogt. Efficient observer siting on large terrain cells (extended abstract). In GIScience 2004: Third International Conference on Geographic Information Science. U Maryland College Park, 20–23 Oct 2004.
BibTeX
@InProceedings{wrf-siting-apr2004, author = "Franklin, W. Randolph and Vogt, Christian", title = "Efficient observer siting on large terrain cells (extended abstract)", booktitle = "{GIScience} 2004: Third International Conference on Geographic Information Science", year = "2004", address = "U Maryland College Park", month = "20--23 Oct", mykey = "visviewshedsiting", fulltext = "https://wrfranklin.org/p/103-collegepark-giscience2004-siting.pdf", customlinkslides = "https://wrfranklin.org/p/103-collegepark-giscience2004-siting-talk.pdf", href = "\bibhrefpt{103-collegepark-giscience2004-siting}{103-collegepark-giscience2004-siting-talk.pdf}", abstract = "This paper refines our testbed implementation of a suite of programs, for fast viewshed, and for fast approximate visibility index determination, and for siting multiple observers jointly to cover terrain. We process DEMs up to 2402 × 2402, while executing so quickly that multiple experiments are easily possible. Both the observer and target may be at a given fixed height above the terrain. We conclude that estimating visibility index using 20-30 random targets per observer is a good compromise between speed and quality. When forcing the selection of top observers to be well spaced out, subdividing the cell into such small blocks that only 2-5 observers are selected per block is best. Applications of multiple observer siting include radio towers, terrain observation, and mitigation of environmental visual nuisances." } -
W. Randolph Franklin. Siting observers on terrain. In Dianne Richardson and Peter van Oosterom, editors, Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling, 109–120. Springer-Verlag, 2002.
BibTeX
@InProceedings{wrf-site, author = "Franklin, W. Randolph", editor = "Richardson, Dianne and van Oosterom, Peter", title = "Siting observers on terrain", booktitle = "Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling", publisher = "Springer-Verlag", pages = "109--120", year = "2002", fulltext = "https://wrfranklin.org/p/97-ottawa-sdh02-siting.pdf", href = "\bibhref{97-ottawa-sdh02-siting}", isbn = "2-540-43802-5", mykey = "visviewshedsiting", abstract = "This paper presents an experimental study of a new algorithm that synthesizes separate programs, for fast viewshed, and for fast approximate visibility index determination, into a working testbed for siting multiple observers jointly to cover terrain from a full level-1 DEM, and to do it so quickly that multiple experiments are easily possible. Both the observer and target may be at a given fixed distance above the terrain. The process operates as follows. (1) An approximate visibility index is calculated for each point in the cell under consideration. (2) A set of tentative observers is selected from the highly visible points. (3) The actual observers are selected from them, so as to cover as much of the cell of possibe, using a greedy algorithm. Various experiments with varying parameters were performed on the Lake Champlain West cell, with observations such as the following. (1) Forcing tentative observers to be well spaced was more important than using the most visible tentative observers. (2) Most of the new observers added (because they covered the most unseen points) were already visible to an existing observer. (3) Randomly deleting many tentative observers before final selection didn't reduce the final area covered." } -
Wm Randolph Franklin and Clark Ray. Higher isn't necessarily better: visibility algorithms and experiments. In Thomas C. Waugh and Richard G. Healey, editors, Advances in GIS Research: Sixth International Symposium on Spatial Data Handling, 751–770. Edinburgh, 5–9 Sept 1994. The International Geographical Union's Commission on Geographical Information Systems and The Association for Geographic Information, Taylor & Francis.
BibTeX
@InProceedings{fr-hinbv-94, author = "Franklin, Wm Randolph and Ray, Clark", editor = "Waugh, Thomas C. and Healey, Richard G.", title = "Higher isn't Necessarily Better: Visibility Algorithms and Experiments", booktitle = "Advances in {GIS} Research: Sixth International Symposium on Spatial Data Handling", organization = "The International Geographical Union's Commission on Geographical Information Systems and The Association for Geographic Information", year = "1994", month = "5--9 Sept", address = "Edinburgh", publisher = "Taylor \\& Francis", pages = "751--770", mykey = "visviewshedsiting", fulltext = "https://wrfranklin.org/p/84-edinburgh-sdh94-higher-not-better.pdf", href = "\bibhref{84-edinburgh-sdh94-higher-not-better}", abstract = "We describe several fast programs to compute viewsheds and weighted visibility indices for observation points in a raster terrain. These pro grams explore various tradeoffs between speed and accuracy. We have analyzed many cells of data; there is no strong correlation between a point's elevation and its weighted visibility index. However, the, very few, high visibility points tend to characterize features of the terrain. This work can form a basis for automatically locating observers jointly to cover a terrain region of interest." } -
W. Randolph Franklin. Approximating visibility. In GIScience 2000. Savannah, Georgia, USA, 30 Oct 2000.
BibTeX
@inproceedings{wrf-savannah, author = "Franklin, W. Randolph", title = "Approximating visibility", booktitle = "{GIScience} 2000", month = "30 Oct", address = "Savannah, Georgia, USA", year = "2000", mykey = "visviewshedsiting", fulltext = "https://wrfranklin.org/p/91-savannah-giscience00-appvis.pdf", href = "\bibhref{91-savannah-giscience00-appvis}" }
More info: Gridding Contours
Gridding contours
Mike Gousie and I have new techniques for the classic problem of converting elevation contours to a grid, and generally fitting a surface to data. Our innovations reduce the terracing effect seen in many other methods, and produce a smoother, more realistic, result. One technique is based on ODETLAP (described separately). Publications include:
-
Michael B. Gousie and Wm. Randolph Franklin. Augmenting grid-based contours to improve thin plate dem generation. Photogrammetric Engineering & Remote Sensing, 71(1):69–79, 2005.
BibTeX
@article{Gousie05, author = "Gousie, Michael B. and Franklin, Wm. Randolph", title = "Augmenting Grid-based Contours to Improve Thin Plate DEM Generation", journal = "Photogrammetric Engineering \\& Remote Sensing", volume = "71", number = "1", pages = "69-79", year = "2005", fulltext = "https://wrfranklin.org/p/106-pers05-thinplate.pdf", mykey = "terrain", href = "\bibhref{106-pers05-thinplate}" } -
Michael Gousie and W. Randolph Franklin. Converting elevation contours to a grid. In Eighth International Symposium on Spatial Data Handling, 647–656. Vancouver BC Canada, July 1998. Dept of Geography, Simon Fraser University, Burnaby, BC, Canada.
BibTeX
@inproceedings{gousie98, author = "Gousie, Michael and Franklin, W. Randolph", title = "Converting Elevation Contours to a Grid", booktitle = "Eighth International Symposium on Spatial Data Handling", address = "Vancouver BC Canada", year = "1998", month = "July", pages = "647-656", publisher = "Dept of Geography, Simon Fraser University, Burnaby, BC, Canada", fulltext = "https://wrfranklin.org/p/89-vancouver-sdh98-contour-gousie.pdf", customlinkslides = "https://wrfranklin.org/p/89-vancouver-sdh98-contour-gousie-talk.pdf", mykey = "terrain odetlap", href = "\bibhrefpt{89-vancouver-sdh98-contour-gousie}{89-vancouver-sdh98-contour-gousie-talk.pdf}" } -
Michael Gousie and W. Randolph Franklin. Constructing a DEM from grid-based data by computing intermediate contours. In Erik Hoel and Phillippe Rigaux, editors, GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, 71–77. New Orleans, 2003.
BibTeX
@InProceedings{acmgis2003, author = "Gousie, Michael and Franklin, W. Randolph", editor = "Hoel, Erik and Rigaux, Phillippe", title = "Constructing a {DEM} from Grid-based Data by Computing Intermediate Contours", booktitle = "GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems", date = "November 7--8", address = "New Orleans", pages = "71-77", year = "2003", fulltext = "https://wrfranklin.org/p/99-acmgis03-intermed-contour.pdf", mykey = "terrain", href = "\bibhref{99-acmgis03-intermed-contour}" } - Contours to digital elevation models: grid-based surface reconstruction methods, MB Gousie, and
- Development of a two-level iterative computational method for solution of the Franklin approximation algorithm for the interpolation of large contour line, J Childs.
More info: Overlaying Two Maps
Overlaying two maps (aka Planar graphs)
An algorithm for calculating the areas of overlaid polygons without calculating the overlay itself, is presented. OVERPROP is useful when the sole purpose of overlaying two maps is to find some mass property of the resulting polygons, or for an areal interpolation of data from one map to the other. Finding the areas of all the output polygons is both simpler and more robust than finding the polygons themselves. OVERPROP works from a reduced representation of each map as a set of `half-edges'; with no global topology. It uses the uniform grid to find edge intersections. The method is not statistical, but is exact within the arithmetic precision of the machine. It is well suited to a parallel machine, and could be extended to overlaying more than two maps simultaneously, and to determining other properties of the output polygons, such as perimeter or center of mass. OVERPROP has been implemented as a C program, and is very fast.
One useful subtask is to locate all the points of each map in a specific polygon of the other. Its expected execution time is constant per query point regardless of the other map's complexity.
Publications include:
-
Wm Randolph Franklin and Venkatesh Sivaswami. OVERPROP — calculating areas of map overlay polygons without calculating the overlay. In Canadian National Conference on Geographic Information Systems: Challenge for the 1990's, 1646–1654. Ottawa, 5-8 Mar 1990. Canadian Institute of Surveying and Mapping.
BibTeX
@inproceedings{fs-ocamo-90-in-geom, author = "Franklin, Wm Randolph and Sivaswami, Venkatesh", title = "{OVERPROP} --- Calculating Areas of Map Overlay Polygons without Calculating the Overlay", booktitle = "Canadian National Conference on Geographic Information Systems: Challenge for the 1990's", publisher = "Canadian Institute of Surveying and Mapping", address = "Ottawa", pages = "1646--1654", month = "5-8 Mar", year = "1990", fulltext = "https://wrfranklin.org/p/61-ottawa90-overlay.pdf", href = "\bibhref{61-ottawa90-overlay}", mykey = "overlay", keywords = "intersection, area, grids" } -
Wm Randolph Franklin and Mohan S. Kankanhalli. Volumes from overlaying 3-D triangulations in parallel. In D. Abel and B.C. Ooi, editors, Advances in Spatial Databases: Third Intl. Symp., SSD'93, volume 692 of Lecture Notes in Computer Science, pages 477–489. Springer-Verlag, June 1993.
BibTeX
@incollection{fk-vo3tp-93, author = "Franklin, Wm Randolph and Kankanhalli, Mohan S.", editor = "Abel, D. and Ooi, B.C.", title = "Volumes From Overlaying 3-{D} Triangulations in Parallel", booktitle = "Advances in Spatial Databases: Third Intl. Symp., SSD'93", publisher = "Springer-Verlag", month = "June", year = "1993", series = "Lecture Notes in Computer Science", volume = "692", pages = "477--489", comment = "SSD = Symp on Large Spatial DBs, Singapore", fulltext = "https://wrfranklin.org/p/78-ssd93-tet.pdf", href = "\bibhref{78-ssd93-tet}", keywords = "parallel computation, intersection, volume, CAD", mykey = "kankanhalli overlay parallel" } -
Wm Randolph Franklin. Map overlay area animation and parallel simulation. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop, 200–203. July 28–August 2 1992.
BibTeX
@InProceedings{f-moaap-92, author = "Franklin, Wm Randolph", editor = "Douglas, David H.", title = "Map Overlay Area Animation and Parallel Simulation", booktitle = "Proceedings, SORSA'92 Symposium and Workshop", year = "1992", month = "July 28--August 2", pages = "200--203", fulltext = "https://wrfranklin.org/p/79-sorsa92-overlay.pdf", href = "\bibhref{79-sorsa92-overlay}", mykey = "overlay", keywords = "parallel computation, intersection, area" } -
Wm Randolph Franklin, Venkateshkumar Sivaswami, David Sun, Mohan Kankanhalli, and Chandrasekhar Narayanaswami. Calculating the area of overlaid polygons without constructing the overlay. Cartography and Geographic Information Systems, pages 81–89, April 1994.
BibTeX
@article{fsskn-ofmop-93, author = "Franklin, Wm Randolph and Sivaswami, Venkateshkumar and Sun, David and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar", title = "Calculating the Area of Overlaid Polygons Without Constructing the Overlay", year = "1994", month = "April", pages = "81--89", journal = "Cartography and Geographic Information Systems", succeeds = "f-cmopa-90", mykey = "overlay kankanhalli chandra", keywords = "intersection, grids, area", fulltext = "https://wrfranklin.org/p/81-cagis94-overlay.pdf", href = "\bibhref{81-cagis94-overlay}" } -
Wm Randolph Franklin. Calculating map overlay polygon' areas without explicitly calculating the polygons — implementation. In 4th International Symposium on Spatial Data Handling, 151–160. Zürich, 23-27 July 1990.
BibTeX
@inproceedings{f-cmopa-90, author = "Franklin, Wm Randolph", title = "Calculating Map Overlay Polygon' Areas Without Explicitly Calculating the Polygons --- Implementation", booktitle = "4th International Symposium on Spatial Data Handling", month = "23-27 July", year = "1990", pages = "151--160", address = "Zürich", fulltext = "https://wrfranklin.org/p/67-sdh90-overlay.pdf", href = "\bibhref{67-sdh90-overlay}", precedes = "fsskn-ofmop-93", mykey = "overlay", keywords = "intersection, area, grids, measure, polygons" } -
Wm Randolph Franklin. A simplified map overlay algorithm. In Harvard Computer Graphics Conference. Cambridge, Mass, USA, 31 July – 4 August 1983.
BibTeX
@inproceedings{fsmoa-83, author = "Franklin, Wm Randolph", title = "A Simplified Map Overlay Algorithm", booktitle = "Harvard Computer Graphics Conference", address = "Cambridge, Mass, USA", month = "31 July -- 4 August", year = "1983", fulltext = "https://wrfranklin.org/p/22-harvard83-overlay.pdf", mykey = "overlay", href = "\bibhref{22-harvard83-overlay}", keywords = "intersection" }
The current version of Overprop uses the Exact Predicates kernel of CGAL. That avoids problems caused by roundoff error, but runs 100x more slowly. However, badly formed input maps still cause erroneous output. The unsolved question is, whether these might be handled automatically.
Overprop is an example of applying topology in cartography.
More info: Logic Programming Map Overlay
Logic programming for map overlay
In the late 1980s, we investigated using declarative, rather than procedural, programming techniques for map overlay. Titles include:
-
Original bibliography reference:
wf-lpacm-90(record not found in the supplied bibliographies). -
Wm Randolph Franklin and Peter YF Wu. A polygon overlay system in prolog. In Autocarto 8: Proceedings of the Eighth International Symposium on Computer-Assisted Cartography, 97–106. Baltimore, Maryland, 29 Mar – 3 April 1987.
BibTeX
@inproceedings{fw-posp-87, author = "Franklin, Wm Randolph and Wu, Peter YF", title = "A Polygon Overlay System in Prolog", booktitle = "Autocarto 8: Proceedings of the Eighth International Symposium on Computer-Assisted Cartography", address = "Baltimore, Maryland", month = "29 Mar -- 3 April", year = "1987", pages = "97--106", fulltext = "https://wrfranklin.org/p/45-autocarto87-overlay-prolog.pdf", href = "\bibhref{45-autocarto87-overlay-prolog}", mykey = "overlay", keywords = "intersection, artificial intelligence" } -
Wm Randolph Franklin, Margaret Nichols, Sumitro Samaddar, and Peter YF Wu. Experiences with using prolog for geometry. In Proceedings of Graphics Interface'86, Vision Interface'86, 26–31. Vancouver, BC, 26–30 May 1986.
BibTeX
@inproceedings{fnsw-eupg-86, author = "Franklin, Wm Randolph and Nichols, Margaret and Samaddar, Sumitro and Wu, Peter YF", title = "Experiences with Using Prolog for Geometry", booktitle = "Proceedings of Graphics Interface'86, Vision Interface'86", address = "Vancouver, BC", month = "26--30 May", year = "1986", pages = "26--31", keywords = "computer graphics, artificial intelligence" } -
Wm Randolph Franklin, Peter Y.F. Wu, Sumitro Samaddar, and Margaret Nichols. Geometry in prolog. In Tosiyasu Kunii, editor, Advanced Computer Graphics, Proceedings of Computer Graphics Tokyo 86, 71–78. April 1986.
BibTeX
@inproceedings{fwsn-gp-86, author = "Franklin, Wm Randolph and Wu, Peter Y.F. and Samaddar, Sumitro and Nichols, Margaret", editor = "Kunii, Tosiyasu", title = "Geometry in Prolog", booktitle = "Advanced Computer Graphics, Proceedings of Computer Graphics Tokyo 86", month = "April", year = "1986", pages = "71-78", fulltext = "https://wrfranklin.org/p/41-tokyo86-geom-prolog.pdf", href = "\bibhref{41-tokyo86-geom-prolog}", keywords = "computer graphics, artificial intelligence" } -
Wm Randolph Franklin, Peter Y.F. Wu, Sumitro Samaddar, and Margaret Nichols. Prolog and geometry projects. IEEE Computer Graphics and Applications, pages 46–55, November 1986.
BibTeX
@article{fwsn-pgp-86, author = "Franklin, Wm Randolph and Wu, Peter Y.F. and Samaddar, Sumitro and Nichols, Margaret", title = "Prolog and Geometry Projects", journal = "IEEE Computer Graphics and Applications", month = "November", year = "1986", pages = "46--55", fulltext = "https://wrfranklin.org/p/44-cga86-prolog.pdf", href = "\bibhref{44-cga86-prolog}", keywords = "computer graphics, artificial intelligence" } -
Wm Randolph Franklin. Computational geometry in prolog. In Proceedings of the NATO Advanced Study Institute on Fundamental Algorithms for Computer Graphics, volume 17 of NATO ASI Series F, pages 737–749. Springer-Verlag, Ilkley, Yorkshire, England, 30 March – 12 April 1985.
BibTeX
@incollection{f-cgp-85, author = "Franklin, Wm Randolph", title = "Computational Geometry in Prolog", booktitle = "Proceedings of the {NATO} Advanced Study Institute on Fundamental Algorithms for Computer Graphics", address = "Ilkley, Yorkshire, England", month = "30 March -- 12 April", year = "1985", publisher = "Springer-Verlag", series = "{NATO} {ASI} Series F", volume = "17", pages = "737--749", fulltext = "https://wrfranklin.org/p/33-nato85-prolog.pdf", href = "\bibhref{33-nato85-prolog}", keywords = "artificial intelligence" } - Polygon overlay in Prolog, (PYF Wu).
More info: Triangulated Irregular Network
Triangulated irregular network
This program takes an array of terrain elevations, and iteratively approximates it with a Triangulated Irregular Network, aka a piecewise linear triangular spline. I implemented the first TIN in cartography or geography, back in 1973; my PL/1 code is online. My current program has the following advantages compared to its competitors.
- Since it operates incrementally, by repeatedly inserting the worst point into the TIN, after the K-th stage, it has identified, in some sense, the K most important points. That is useful for, e.g., progressive transmission.
- By virtue of a compact data structure, it does not require external storage even for rather large datasets. On a 32-bit PC, even many years ago, arrays of up to 10800x10800 posts could be processed; much larger datasets would be feasible today. Therefore it also does not require that the points first be externally sorted. >><<
More info: Prism
Prism
This is a 1970s algorithm and implementation for displaying 3D prism maps showing data depending on geographic regions by raising a prism above each region. The program preprocessed the 2D map in advance so that new data could be displayed, with hidden surfaces removed, quickly. Publications include:
-
W. Randolph Franklin. Program translates statistics into 3-D color map of europe. IEEE Computer and Applications, 2(5):front cover and p. 4, July 1982. (invited).
BibTeX
@article{wrf-cga-82, author = "Franklin, W. Randolph", title = "Program Translates Statistics into 3-{D} Color Map of Europe", journal = "IEEE Computer and Applications", volume = "2", number = "5", month = "July", year = "1982", pages = "front cover and p. 4", note = "(invited)" } -
W. Randolph Franklin. Prism — a prism plotting program. In Allan H. Schmidt, editor, Mapping Software and Cartographic Data Bases, Harvard Library of Computer Mapping, 1979 collection, pages 75–79. 1979.
BibTeX
@incollection{wrf-prism-hu, author = "Franklin, W. Randolph", editor = "Schmidt, Allan H.", title = "Prism --- A Prism Plotting Program", booktitle = "Mapping Software and Cartographic Data Bases", year = "1979", pages = "75--79", mykey = "vis3dobj", series = "Harvard Library of Computer Mapping, 1979 collection" } -
Wm Randolph Franklin and Harry R. Lewis. 3-D graphic display of discrete spatial data by prism maps. In Proc. SIGGRAPH'78, volume 12(3), 70–75. August 1978.
BibTeX
@inproceedings{fl-3gdds-78, author = "Franklin, Wm Randolph and Lewis, Harry R.", title = "3-{D} Graphic Display of Discrete Spatial Data By Prism Maps", booktitle = "Proc. {SIGGRAPH}'78", journal = "Computer Graphics", volume = "12(3)", month = "August", year = "1978", pages = "70--75", keywords = "computer graphics, hidden line/surface elimination", mykey = "vis3dobj", fulltext = "https://wrfranklin.org/p/5b-sig78-prism.pdf", href = "\bibhref{5b-sig78-prism}" }
More info: General Cartography
General cartography
Here are broader papers and talks covering more than one topic, or reviewing the field, or that don't fit into one of the other categories. Titles of papers and talks include:
-
UCGIA Steering Committee. On the possible role(s) of a “university consortium for geographic information and analysis” (UCGIA). In Proceedings, American Congress on Surveying and Mapping / American Society for Photogrammetry and Remote Sensing '93. New Orleans, 1993.
BibTeX
@InProceedings{wrf-ucgia, author = "Committee, UCGIA Steering", title = "On the Possible Role(s) of a ``University Consortium for Geographic Information and Analysis'' ({UCGIA})", booktitle = "Proceedings, American Congress on Surveying and Mapping / American Society for Photogrammetry and Remote Sensing '93", year = "1993", address = "New Orleans" } -
Wm Randolph Franklin. Tutorial on curve fitting for GIS. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop. July 28–August 2 1992.
BibTeX
@InProceedings{f-tcfg-92, author = "Franklin, Wm Randolph", editor = "Douglas, David H.", title = "Tutorial on Curve Fitting for {GIS}", booktitle = "Proceedings, SORSA'92 Symposium and Workshop", year = "1992", optpages = "235--250", month = "July 28--August 2", fulltext = "https://wrfranklin.org/p/77-sorsa92-bezier.pdf", href = "\bibhref{77-sorsa92-bezier}", keywords = "splines, tutorial" } -
Wm Randolph Franklin. Computer systems and low level data structures for GIS. In David Maguire, Mike Goodchild, and David Rhind, editors, Geographical Information Systems, Principles and Applications, volume 1, pages 215–225. Longman Scientific and Technical, London UK, 1991.
BibTeX
@incollection{f-cslld-91, author = "Franklin, Wm Randolph", editor = "Maguire, David and Goodchild, Mike and Rhind, David", title = "Computer Systems and Low Level Data Structures for {GIS}", booktitle = "Geographical Information Systems, Principles and Applications", publisher = "Longman Scientific and Technical", address = "London UK", year = "1991", pages = "215--225", volume = "1", fulltext = "https://wrfranklin.org/p/73-maguire91-gis.pdf", href = "\bibhref{73-maguire91-gis}", keywords = "tutorial" } -
Harold Moellering, Keith Clarke, Robert Cromley, Wm Randolph Franklin, Alan Saalfeld, Jon Kimerling, and Marc Armstrong. Analytical cartography. UCGIS Emerging Research Themes in GIScience (white paper), Dec 2000. (UCGIS = University Consortium for Geographic Information Science).
BibTeX
@Article{ucgis-ancart, author = "Moellering, Harold and Clarke, Keith and Cromley, Robert and Franklin, Wm Randolph and Saalfeld, Alan and Kimerling, Jon and Armstrong, Marc", title = "Analytical Cartography", journal = "UCGIS Emerging Research Themes in GIScience (white paper)", year = "2000", month = "Dec", note = "(UCGIS = University Consortium for Geographic Information Science)" }
Computational geometry research
Efficient geometric operations on large datasets, or efficient spatial algorithms and data structures, is another research theme.
Here are the slides of a good summary talk: Geometric Operations on Millions of Objects, presented at Koc University, Istanbul, 16 July, Sabanci University, Istanbul, 20 July, Bilkent University, 26 July, and Middle Eastern Technical University, 27 July 2004.
More info: Fundamentals
Fundamentals
Here are pages on
- PNPOLY, an 8-line program for determining point inclusion in a polygon. Written in 1970 it is both shorter and more robust than many later competitors.
- The uniform grid data structure, for efficiently culling likely intersections in E'^2^' and E'^3^'. Although this appears to be too simple to work, implementations (supported by analysis) show that it does work quite well, even on unevenly distributed data. It is also simple enough to implemente and test, and also parallelizes well.
- Why raster graphics is harder than vector graphics. It's because integers are harder than rationals.
Publications include:
-
W. Randolph Franklin and Barb Cutler. KNOWMESH – meshless geometry with knowledge representation. In DARPA GRID2 workshop. 18–19 Aug 2010.
BibTeX
@InProceedings{grid-2010, author = "Franklin, W. Randolph and Cutler, Barb", title = "{KNOWMESH} -- Meshless geometry with knowledge representation", booktitle = "{DARPA GRID2} workshop", year = "2010", customlinkslides = "https://wrfranklin.org/p/142-darpa-knowmesh-talk.pdf", href = "\bibhreft{142-darpa-knowmesh-talk.pdf}", month = "18--19 Aug" } -
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.
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.
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.
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" } -
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" } -
Wm Randolph Franklin. Problems with raster graphics algorithms. In L.R.A. Kessener, F.J. Peters, and M.L.P. van Lierop, editors, Data Structures for Raster Graphics, proceedings of a Workshop held at Steensel, The Netherlands, June 24–28, 1985, pages 1–8. Springer-Verlag EurographicSeminars, 1986.
BibTeX
@incollection{f-prga-85, author = "Franklin, Wm Randolph", editor = "Kessener, L.R.A. and Peters, F.J. and van Lierop, M.L.P.", title = "Problems with Raster Graphics Algorithms", booktitle = "Data Structures for Raster Graphics, proceedings of a Workshop held at Steensel, The Netherlands, June 24--28, 1985", publisher = "Springer-Verlag EurographicSeminars", year = "1986", pages = "1--8", comments = "(invited presentation)", fulltext = "https://wrfranklin.org/p/34-eindhoven85-raster.pdf", href = "\bibhref{34-eindhoven85-raster}", keywords = "computer graphics, discrete geometry" } -
Wm Randolph Franklin. Cartographic errors symptomatic of underlying algebra problems. In Proc. International Symposium on Spatial Data Handling, volume 1, 190–208. Zürich, 20–24 August 1984.
BibTeX
@inproceedings{f-cesua-84, author = "Franklin, Wm Randolph", title = "Cartographic Errors Symptomatic of Underlying Algebra Problems", booktitle = "Proc. International Symposium on Spatial Data Handling", volume = "1", month = "20--24 August", year = "1984", address = "Zürich", pages = "190--208", fulltext = "https://wrfranklin.org/p/27-sdh84-cartoerrs.pdf", href = "\bibhref{27-sdh84-cartoerrs}" } -
Wm Randolph Franklin. Efficient rotation of an object. IEEE Trans. Comput., C-32(11):1064–1067, November 1983.
BibTeX
@article{f-ero-83, author = "Franklin, Wm Randolph", title = "Efficient Rotation of an Object", journal = "IEEE Trans. Comput.", volume = "C-32", number = "11", month = "November", year = "1983", pages = "1064--1067", fulltext = "https://wrfranklin.org/p/16-ieeetc83-rotation.pdf", href = "\bibhref{16-ieeetc83-rotation}", keywords = "computer graphics, CAD" }
More info: Local Topology
Local data structures for polyhedra
These representations use little or no global topology. This contrasts with the complete topologies used in many CAD systems. My local data structure simplifies many operations, such as determination of the mass properties of boolean combinations of objects. That simplifies many operations, such as determination of the mass properties of boolean combinations of objects. There are fewer special cases, and parallel processing is facilitated.
Publications include:
-
Wm Randolph Franklin. Polygon properties calculated from the vertex neighborhoods. In Proc. 3rd Annu. ACM Sympos. Comput. Geom., 110–118. 1987.
BibTeX
@inproceedings{f-ppcvn-87, author = "Franklin, Wm Randolph", title = "Polygon properties calculated from the vertex neighborhoods", booktitle = "Proc. 3rd Annu. ACM Sympos. Comput. Geom.", year = "1987", pages = "110--118", oldlabel = "geom-1214", fulltext = "https://wrfranklin.org/p/46-scg87-vertex.pdf", href = "\bibhref{46-scg87-vertex}", mykey = "topology", keywords = "rays, measure, polygons" } -
Wm Randolph Franklin. Rays — new representation for polygons and polyhedra. Computer Graphics and Image Processing, 22:327–338, 1983.
BibTeX
@article{f-rnrpp-83, author = "Franklin, Wm Randolph", title = "RAYS --- New Representation for Polygons and Polyhedra", journal = "Computer Graphics and Image Processing", volume = "22", year = "1983", pages = "327--338", fulltext = "https://wrfranklin.org/p/13-cvgip83-rays.pdf", href = "\bibhref{13-cvgip83-rays}", keywords = "measure, polygons, rays" }
Parallel and distributed geometry algorithms
-
Mohan Kankanhalli and Wm Randolph Franklin. Area and perimeter computation of the union of a set of iso-rectangles in parallel. J. Parallel Distrib. Comput., 27(2):107–117, June 1995. doi:https://doi.org/10.1006/jpdc.1995.1076.
BibTeX
@article{kf-apcus-92, author = "Kankanhalli, Mohan and Franklin, Wm Randolph", title = "Area and Perimeter Computation of the Union of a Set of Iso-Rectangles in Parallel", year = "1995", pages = "107--117", volume = "27", number = "2", doi = "https://doi.org/10.1006/jpdc.1995.1076", month = "June", journal = "J. Parallel Distrib. Comput.", keywords = "intersection, parallel computation, grids, area", fulltext = "https://wrfranklin.org/p/85-jpdc95-parallel-union-area.pdf", href = "\bibhref{85-jpdc95-parallel-union-area}", abstract = "Finding the area and perimeter of the union/intersection of a set of iso-rectangles is a very important part of circuit extraction in VLSI design. We combine two techniques, the uniform grid and the vertex neighborhoods, to develop a new parallel algorithm for the area and perimeter problems which has an average linear time performance but is not worst-case optimal. The uniform grid technique has been used to generate the candidate vertices of the union or intersection of the rectangles. An efficient point-in-rectangles inclusion test filters the candidate set to obtain the relevant vertices of the union or intersection. Finally, the vertex neighborhood technique is used to compute the mass properties from these vertices. This algorithm has an average time complexity of O(((n + k)/p) + log p) where n is the number of input rectangle edges with k intersections on p processors assuming a PRAM model of computation. The analysis of the algorithm on a SIMD architecture is also presented. This algorithm requires very simple data structures which makes the implementation easy. We have implemented the algorithm on a Sun 4/280 workstation and a Connection Machine. The sequential implementation performs better than the optimal algorithm for large datasets. The parallel implementation on a Connection Machine CM-2 with 32K processors also shows good results.", mykey = "topology kankanhalli parallel" } -
Wm Randolph Franklin and Mohan S. Kankanhalli. Volumes from overlaying 3-D triangulations in parallel. In D. Abel and B.C. Ooi, editors, Advances in Spatial Databases: Third Intl. Symp., SSD'93, volume 692 of Lecture Notes in Computer Science, pages 477–489. Springer-Verlag, June 1993.
BibTeX
@incollection{fk-vo3tp-93, author = "Franklin, Wm Randolph and Kankanhalli, Mohan S.", editor = "Abel, D. and Ooi, B.C.", title = "Volumes From Overlaying 3-{D} Triangulations in Parallel", booktitle = "Advances in Spatial Databases: Third Intl. Symp., SSD'93", publisher = "Springer-Verlag", month = "June", year = "1993", series = "Lecture Notes in Computer Science", volume = "692", pages = "477--489", comment = "SSD = Symp on Large Spatial DBs, Singapore", fulltext = "https://wrfranklin.org/p/78-ssd93-tet.pdf", href = "\bibhref{78-ssd93-tet}", keywords = "parallel computation, intersection, volume, CAD", mykey = "kankanhalli overlay parallel" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Boolean combinations of polygons in parallel. In Proceedings of the 1992 International Conference on Parallel Processing, volume. 17–21 Aug 1992.
BibTeX
@inproceedings{nf-bcpp-92, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", title = "Boolean Combinations of Polygons in Parallel", booktitle = "Proceedings of the 1992 International Conference on Parallel Processing", month = "17--21 Aug", year = "1992", volume = "", pages = "", fulltext = "https://wrfranklin.org/p/76-icpp92-boolean.pdf", href = "\bibhref{76-icpp92-boolean}", mykey = "chandra", keywords = "parallel computation, grids, intersection, CAD" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Edge intersection on the Hypercube computer. Information Processing Letters, 41(5):257–262, 3 April 1992.
BibTeX
@article{nf-eihc-92, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", title = "Edge Intersection on the {H}ypercube Computer", journal = "Information Processing Letters", year = "1992", volume = "41", number = "5", month = "3 April", pages = "257--262", keywords = "parallel algorithms, performance evaluation, intersection, grids", fulltext = "https://wrfranklin.org/p/68-ipl92-hypercube.pdf", mykey = "chandra", href = "\bibhref{68-ipl92-hypercube}" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Determination of mass properties of polygonal CSG objects in parallel. In Joshua Turner, editor, Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 279–288. ACM/SIGGRAPH, 5–7 June 1991.
BibTeX
@Incollection{nf-dmppci-91, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", editor = "Turner, Joshua", title = "Determination of Mass Properties of Polygonal {CSG} Objects in Parallel", year = "1991", month = "5--7 June", pages = "279--288", booktitle = "Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications", publisher = "ACM/SIGGRAPH", fulltext = "https://wrfranklin.org/p/69a-turner91-determination.pdf", href = "\bibhref{69a-turner91-determination}", mykey = "chandra", precedes = "nf-dmppcj-91", keywords = "parallel computation, intersection, grids, constructive solid geometry, area" } -
Wm Randolph Franklin and Mohan Kankanhalli. Parallel object-space hidden surface removal. In Proceedings of SIGGRAPH'90, volume 24, 87–94. August 1990.
BibTeX
@inproceedings{fk-poshs-90-in-geom, author = "Franklin, Wm Randolph and Kankanhalli, Mohan", title = "Parallel Object-Space Hidden Surface Removal", booktitle = "Proceedings of SIGGRAPH'90", journal = "Comput. Graph.", comments = "Dallas, Texas", volume = "24", month = "August", year = "1990", pages = "87--94", fulltext = "https://wrfranklin.org/p/62-siggraph90-parallel.pdf", href = "\bibhref{62-siggraph90-parallel}", mykey = "vis3dobj kankanhalli", keywords = "computer graphics, parallel computation, hidden line/surface elimination, grids" } -
W. Randolph Franklin, Narayanaswami Chandrasekhar, and Mohan Kankanhalli. Parallel algorithms for geometric computing. In Final Program, SIAM Conference on Geometric Design, A17. 6–10 Nov 1989. (abstract only).
BibTeX
@InProceedings{fck-pagc-siam-89, author = "Franklin, W. Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan", title = "Parallel Algorithms for Geometric Computing", pages = "A17", booktitle = "Final Program, {SIAM} Conference on Geometric Design", year = "1989", month = "6--10 Nov", mykey = "chandra kankanhalli", note = "(abstract only)" } -
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.
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.
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" }
More info: Connected Components
Connected components in \(E^3\)
This is an efficient implementation on a laptop computer of the union-find algorithm for finding connected components when the input is a 1000x1000×1000 3D box of binary voxels. Each voxel may be connected either to its 6 orthogonal neighbors, or to all 26 neighbors. Component properties, such as area, and volume are also computed. This implementation is fast enough to permit experimental studies of random connectivity. Publications include:
-
W. Randolph Franklin and Eric Landis. Connected components on 1000x1000x1000 datasets. In 16th Fall Workshop on Computational Geometry. Smith College, Northampton, MA, 10-11 Nov 2006. (extended abstract).
BibTeX
@InProceedings{wrf-connect-fwcg2006, author = "Franklin, W. Randolph and Landis, Eric", title = "Connected components on 1000x1000x1000 datasets", booktitle = "16th Fall Workshop on Computational Geometry", address = "Smith College, Northampton, MA", month = "10-11 Nov", year = "2006", mykey = "connect", note = "(extended abstract)", fulltext = "https://wrfranklin.org/p/110-smith-fwcg06-connect.pdf", customlinkslides = "https://wrfranklin.org/p/110-smith-fwcg06-connect-talk.pdf", href = "\bibhrefat{110-smith-fwcg06-connect}{110-smith-fwcg06-connect-talk}" } -
Eric N. Landis, Tong Zhang, Edwin N. Nagy, George Nagy, and W. Randolph Franklin. Cracking, damage and fracture in four dimensions. Materials and Structures, online date: 13 July 2006.
BibTeX
@Article{landis2006, author = "Landis, Eric N. and Zhang, Tong and Nagy, Edwin N. and Nagy, George and Franklin, W. Randolph", title = "Cracking, damage and fracture in four dimensions", journal = "Materials and Structures", publisher = "Springer", year = "2006", mykey = "connect", month = "online date: 13 July", fulltext = "https://wrfranklin.org/p/109-matstruct2006-cracking-landis.pdf", href = "\bibhref{109-matstruct2006-cracking-landis}", abstract = "Abstract Concrete and cracking are nearly synonymous despite our best efforts and intentions. Relationships between cracking and the stress states that lead to cracking can be instructive. In an effort to better understand these relationships, X-ray microtomography was used to make high-resolution three-dimensional digital images of small concrete specimens under load. Using 3D image analysis, quantitative measurements of internal crack growth were made that include effects of crack tortuosity, branching and microcracking. Successive images at different levels of cracking and damage provide us with a detailed picture of internal crack progression. When coupled with load-deformation response, bulk material properties such as fracture toughness or damage variables can be quantitatively linked with cracking. Measurements to date have shown distinct fracture regimes linked to crack formation and propagation. In addition, the crack measurements offer a way to provide a physical basis for a scalar damage variable.", Keywords = "Concrete - Fracture - Damage - Tomography", publisher-url = "http://www.springerlink.com/content/ftgmk3m461716833/" } -
Edwin Nagy, Tong Zhang, Wm Randolph Franklin, George Nagy, and E Landis. 3D analysis of tomographic images. In 16th ASCE Engineering Mechanics Conference. U Washington, Seattle, 16-18 July 2003. electronic proceedings.
BibTeX
@InProceedings{acse2003, author = "Nagy, Edwin and Zhang, Tong and Franklin, Wm Randolph and Nagy, George and Landis, E", title = "{3D} Analysis of Tomographic Images", booktitle = "16th {ASCE} Engineering Mechanics Conference", year = "2003", address = "U Washington, Seattle", month = "16-18 July", mykey = "connect", note = "electronic proceedings", fulltext = "https://wrfranklin.org/p/98-acse03-3danalysis-nagy.pdf", href = "\bibhref{98-acse03-3danalysis-nagy}" } -
G Nagy, T Zhang, WR Franklin, E Landis, E Nagy, and D Keane. Volume and surface area distributions of cracks in concrete. In C. Arcelli, L.P. Cordella, and G. Sanniti di Baja, editors, Visual Form 2001: 4th International Workshop on Visual Form IWVF4, volume 2051/2001 of Lecture Notes in Computer Science. Springer-Verlag Heidelberg, Capri, Italy, 28-30 May 2001.
BibTeX
@InCollection{capri01, author = "Nagy, G and Zhang, T and Franklin, WR and Landis, E and Nagy, E and Keane, D", editor = "Arcelli, C. and Cordella, L.P. and di Baja, G. Sanniti", title = "Volume and Surface Area Distributions of Cracks in Concrete", booktitle = "Visual Form 2001: 4th International Workshop on Visual Form {IWVF4}", publisher = "Springer-Verlag Heidelberg", year = "2001", mykey = "connect", volume = "2051/2001", series = "Lecture Notes in Computer Science", address = "Capri, Italy", month = "28-30 May", href = "\bibhrefpp{95-capri01-paper}{95-capri01-poster.gif}", fulltext = "https://wrfranklin.org/p/95-capri01-paper.pdf", customlinkposter = "https://wrfranklin.org/p/95-capri01-poster.gif" }
More info: Linear Object Space Hidden Surfaces
Linear time object space hidden surfaces
This is an object space algorithm from the late 1970s for determining the visible parts of objects such as polyhedra and spheres in E'^3^' that operates in expected time linear in the number of objects, independent of their depth complexity. We have implemented it for spheres and cubes. Around 1980, it could handle 10,000 random spheres stacked 10 deep. (Some other algorithm's times are quadratic in the depth.) Publications include:
-
Wm Randolph Franklin and Mohan Kankanhalli. Parallel object-space hidden surface removal. In Proceedings of SIGGRAPH'90, volume 24, 87–94. August 1990.
BibTeX
@inproceedings{fk-poshs-90-in-geom, author = "Franklin, Wm Randolph and Kankanhalli, Mohan", title = "Parallel Object-Space Hidden Surface Removal", booktitle = "Proceedings of SIGGRAPH'90", journal = "Comput. Graph.", comments = "Dallas, Texas", volume = "24", month = "August", year = "1990", pages = "87--94", fulltext = "https://wrfranklin.org/p/62-siggraph90-parallel.pdf", href = "\bibhref{62-siggraph90-parallel}", mykey = "vis3dobj kankanhalli", keywords = "computer graphics, parallel computation, hidden line/surface elimination, grids" } -
Wm Randolph Franklin. A linear time exact hidden surface algorithm. In Kenneth I. Joy and others, editors, Tutorial: Computer Graphics: Image Synthesis, pages 218–224. 1988.
BibTeX
@incollection{f-ltehs-88, author = "Franklin, Wm Randolph", editor = "Joy, Kenneth I. and others", title = "A linear time exact hidden surface algorithm", booktitle = "Tutorial: Computer Graphics: Image Synthesis", year = "1988", pages = "218--224", succeeds = "f-ltehs-80", precedes = "f-ehsao-81", mykey = "vis3dobj", keywords = "computer graphics, hidden line/surface elimination" } -
Wm Randolph Franklin and Varol Akman. Adaptive grid for polyhedral visibility in object space, an implementation. Computer Journal, 31(1):56–60, February 1988.
BibTeX
@article{fa-agpvo-88-in-geom, author = "Franklin, Wm Randolph and Akman, Varol", title = "Adaptive Grid for polyhedral visibility in object space, an implementation", journal = "Computer Journal", volume = "31", number = "1", pages = "56-60", month = "February", year = "1988", fulltext = "https://wrfranklin.org/p/43-cj88-polyvis.pdf", href = "\bibhref{43-cj88-polyvis}", mykey = "akman vis3dobj", keywords = "computer graphics, hidden line/surface elimination" } -
Wm Randolph Franklin and Varol Akman. A simple and efficient haloed line algorithm for hidden line elimination. Computer Graphics Forum, 6(2):103–109, May 1987.
BibTeX
@article{fa-sehla-87, author = "Franklin, Wm Randolph and Akman, Varol", title = "A simple and efficient haloed line algorithm for hidden line elimination", journal = "Computer Graphics Forum", volume = "6", number = "2", pages = "103-109", month = "May", year = "1987", fulltext = "https://wrfranklin.org/p/42-cgf87-haloed.pdf", href = "\bibhref{42-cgf87-haloed}", mykey = "akman vis3dobj", keywords = "computer graphics, hidden line/surface elimination" } -
Wm Randolph Franklin. An exact hidden sphere algorithm that operates in linear time. Comput. Graph. Image Process., 15:364–379, 1981.
BibTeX
@article{f-ehsao-81, author = "Franklin, Wm Randolph", title = "An exact hidden sphere algorithm that operates in linear time", journal = "Comput. Graph. Image Process.", volume = "15", year = "1981", pages = "364--379", oldlabel = "geom-224", fulltext = "https://wrfranklin.org/p/8-cgip81-hsa.pdf", href = "\bibhref{8-cgip81-hsa}", succeeds = "f-ltehs-80", mykey = "vis3dobj", keywords = "computer graphics, hidden line/surface elimination" } -
Wm Randolph Franklin. A linear time exact hidden surface algorithm. Comput. Graph., 14(3):117–123, 1980.
BibTeX
@article{f-ltehs-80-in-geom, author = "Franklin, Wm Randolph", title = "A linear time exact hidden surface algorithm", booktitle = "Proc. SIGGRAPH '80", journal = "Comput. Graph.", volume = "14", number = "3", year = "1980", pages = "117--123", oldlabel = "geom-223", precedes = "f-ltehs-88", fulltext = "https://wrfranklin.org/p/7-siggraph80-linear-hsa.pdf", href = "\bibhref{7-siggraph80-linear-hsa}", keywords = "computer graphics, hidden line/surface elimination", mykey = "vis3dobj", portal = "\url{http://portal.acm.org/citation.cfm?id= 807480\&dl= GUIDE\&coll= GUIDE\&CFID= 52002891\&CFTOKEN= 56467748}" } -
Wm Randolph Franklin. Combinatorics of hidden surface algorithms. Technical Report, Center for Research in Computing Technology, Harvard Univ., Cambridge, MA, June 1978.
BibTeX
@PhdThesis{f-chsa-78, author = "Franklin, Wm Randolph", title = "Combinatorics of hidden surface algorithms", type = "Technical {Report}", number = "TR-12-78", school = "Center for Research in Computing Technology, Harvard Univ.", address = "Cambridge, MA", year = "1978", month = "June", oldlabel = "geom-221", href = "\bibhrefthesis{0-harvard78-thesis}", fulltext = "https://wrfranklin.org/p/0-harvard78-thesis.pdf", comments = "Thesis w/o appendices available as a TR from CRCT. Complete thesis available only on microfilm from Harvard, since Harvard did not then subscribe to UMI.", mykey = "vis3dobj", keywords = "computer graphics, hidden line/surface elimination" }
More info: Nearpt3
Nearest points in E'^2^' and E'^3^'
This is a pair of subroutines to find nearest points in E'^3^'. Preprocess takes a list of fixed points, and preprocesses them into a data structure. Query takes a query point, and returns the closest fixed point to it. Nearpt2 is a special case for E'^2^'.
Nearpt3 is very fast, very small, and can process very nonhomogeneous data. The largest example run on a laptop computer was St Matthew from the Stanford Digital Michelangelo Project Archive, with 184,088,599 fixed points.
Preprocessing the David data set, with 28,158,109 fixed points, into a 723'^3^' grid took 0.6 microseconds per fixed point. Each query required 6 microseconds. The platform was an IBM T43p laptop computer with a 2GHz Intel Pentium M processor and 2GB of memory. Publications include:
-
W. Randolph Franklin. Nearpt3 — Nearest point query in $E^3$ with a uniform grid (extended abstract). In 14th Annual Fall Workshop on Computational Geometry. MIT, 20 Nov 2004.
BibTeX
@inproceedings{wrf-nearpt3-mit-2004, author = "Franklin, W. Randolph", title = "Nearpt3 --- {Nearest} Point Query in {$E^3$} with a Uniform Grid (extended abstract)", booktitle = "14th Annual Fall Workshop on Computational Geometry", address = "{MIT}", month = "20 Nov", year = "2004", mykey = "nearpt", fulltext = "https://wrfranklin.org/p/102-fwcg2004-nearpt3.pdf", customlinkslides = "https://wrfranklin.org/p/102-fwcg2004-nearpt3-talk.pdf", href = "\bibhrefpt{102-fwcg2004-nearpt3}{102-fwcg2004-nearpt3-talk.pdf}" } -
W. Randolph Franklin. Nearpt3 — Nearest point query on 184M points in $E^3$ with a uniform grid. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG'05), 239–242. Windsor, Ontario, 10-12 August 2005.
BibTeX
@InProceedings{wrf-nearpt3-cccg-2005, author = "Franklin, W. Randolph", title = "Nearpt3 --- {Nearest} Point Query on {184M} Points in {$E^3$} with a Uniform Grid", year = "2005", booktitle = "Proceedings of the 17th {Canadian} Conference on Computational Geometry {(CCCG'05)}", address = "Windsor, Ontario", month = "{10-12 August}", pages = "239--242", mykey = "nearpt", fulltext = "https://wrfranklin.org/p/105-nearpt3.pdf", customlinkslides = "https://wrfranklin.org/p/105-nearpt3-talk.pdf", href = "\bibhrefnpt{paper (current version)}{105-nearpt3}{105-nearpt3-talk.pdf}" }
More info: All Near Pairs
All near point pairs in E'^3^'
This is a program to report all pairs of points nearer than a given distance, from a fixed set of points in E'^3^'.
Sample time: Processing 20K points to report 688K pairs took 20msec CPU time, excluding I/O on a 2.8GHz machine.
More info: Overlaying 3D Triangulations
Overlaying 3D triangulations
This 1992 algorithm combines two different triangulations of the same 3D faceted object, to determine which pairs of tetrahedra overlap, and the intersection volumes. This is useful for interpolating data from one triangulation of an object to another. Publications include:
-
Wm Randolph Franklin and Mohan S. Kankanhalli. Volumes from overlaying 3-D triangulations in parallel. In D. Abel and B.C. Ooi, editors, Advances in Spatial Databases: Third Intl. Symp., SSD'93, volume 692 of Lecture Notes in Computer Science, pages 477–489. Springer-Verlag, June 1993.
BibTeX
@incollection{fk-vo3tp-93, author = "Franklin, Wm Randolph and Kankanhalli, Mohan S.", editor = "Abel, D. and Ooi, B.C.", title = "Volumes From Overlaying 3-{D} Triangulations in Parallel", booktitle = "Advances in Spatial Databases: Third Intl. Symp., SSD'93", publisher = "Springer-Verlag", month = "June", year = "1993", series = "Lecture Notes in Computer Science", volume = "692", pages = "477--489", comment = "SSD = Symp on Large Spatial DBs, Singapore", fulltext = "https://wrfranklin.org/p/78-ssd93-tet.pdf", href = "\bibhref{78-ssd93-tet}", keywords = "parallel computation, intersection, volume, CAD", mykey = "kankanhalli overlay parallel" }
More info: Union
UNION2, UNION3, and Boolean operations and their mass properties
This theme computes mass properties of boolean operations on large sets of polyhedra, typically in linear time. Besides algorithms, it includes demo implementations such as computing the volume and area of the union of up to 20,000,000 cubes. That took one hour on a dual xeon workstation.
My technique is to combine several other themes. The first is to optimizes the composition of volume and union operators; finding the volume of the union of two polyhedra does not require finding their explicit union with global topology etc. That also uses my local topological formulae. Finally, the linear execution time is effected with a uniform grid.
Publications include:
-
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Determination of mass properties of polygonal CSG objects in parallel. In Joshua Turner, editor, Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 279–288. ACM/SIGGRAPH, 5–7 June 1991.
BibTeX
@Incollection{nf-dmppci-91, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", editor = "Turner, Joshua", title = "Determination of Mass Properties of Polygonal {CSG} Objects in Parallel", year = "1991", month = "5--7 June", pages = "279--288", booktitle = "Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications", publisher = "ACM/SIGGRAPH", fulltext = "https://wrfranklin.org/p/69a-turner91-determination.pdf", href = "\bibhref{69a-turner91-determination}", mykey = "chandra", precedes = "nf-dmppcj-91", keywords = "parallel computation, intersection, grids, constructive solid geometry, area" } -
W. Randolph Franklin. Analysis of mass properties of the union of millions of polyhedra. In M. L. Lucian and M. Neamtu, editors, Geometric Modeling and Computing: Seattle 2003, pages 189–202. Nashboro Press, Brentwood TN, 2004.
BibTeX
@InCollection{wrf-union-analysis-2004, author = "Franklin, W. Randolph", editor = "Lucian, M. L. and Neamtu, M.", title = "Analysis of Mass Properties of the Union of Millions of Polyhedra", year = "2004", booktitle = "Geometric Modeling and Computing: Seattle 2003", publisher = "Nashboro Press, Brentwood TN", pages = "189--202", isbn = "0-0-9728482-3-1", mykey = "union3 topology parallel", fulltext = "https://wrfranklin.org/p/101-siam04-union.pdf", href = "\bibhref{101-siam04-union}" } -
Wm. Randolph Franklin. Mass properties of the union of millions of identical cubes. In Ravi Janardan, Debashish Dutta, and Michiel Smid, editors, Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 67, pages 329–345. American Mathematical Society, 2005.
BibTeX
@InCollection{wrf-dimacs2005, author = "Franklin, Wm. Randolph", editor = "Janardan, Ravi and Dutta, Debashish and Smid, Michiel", title = "Mass Properties of the Union of Millions of Identical Cubes", booktitle = "Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, {DIMACS} Series in Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "67", year = "2005", pages = "329--345", mykey = "union3 topology", succeeds = "wrf-dimacs2003", fulltext = "https://wrfranklin.org/p/104-dimacs03-union.pdf", customlinkslides = "https://wrfranklin.org/p/104-dimacs03-union-talk.pdf", href = "\bibhrefpt{104-dimacs03-union}{104-dimacs03-union-talk.pdf}" } -
Mohan Kankanhalli and Wm Randolph Franklin. Area and perimeter computation of the union of a set of iso-rectangles in parallel. J. Parallel Distrib. Comput., 27(2):107–117, June 1995. doi:https://doi.org/10.1006/jpdc.1995.1076.
BibTeX
@article{kf-apcus-92, author = "Kankanhalli, Mohan and Franklin, Wm Randolph", title = "Area and Perimeter Computation of the Union of a Set of Iso-Rectangles in Parallel", year = "1995", pages = "107--117", volume = "27", number = "2", doi = "https://doi.org/10.1006/jpdc.1995.1076", month = "June", journal = "J. Parallel Distrib. Comput.", keywords = "intersection, parallel computation, grids, area", fulltext = "https://wrfranklin.org/p/85-jpdc95-parallel-union-area.pdf", href = "\bibhref{85-jpdc95-parallel-union-area}", abstract = "Finding the area and perimeter of the union/intersection of a set of iso-rectangles is a very important part of circuit extraction in VLSI design. We combine two techniques, the uniform grid and the vertex neighborhoods, to develop a new parallel algorithm for the area and perimeter problems which has an average linear time performance but is not worst-case optimal. The uniform grid technique has been used to generate the candidate vertices of the union or intersection of the rectangles. An efficient point-in-rectangles inclusion test filters the candidate set to obtain the relevant vertices of the union or intersection. Finally, the vertex neighborhood technique is used to compute the mass properties from these vertices. This algorithm has an average time complexity of O(((n + k)/p) + log p) where n is the number of input rectangle edges with k intersections on p processors assuming a PRAM model of computation. The analysis of the algorithm on a SIMD architecture is also presented. This algorithm requires very simple data structures which makes the implementation easy. We have implemented the algorithm on a Sun 4/280 workstation and a Connection Machine. The sequential implementation performs better than the optimal algorithm for large datasets. The parallel implementation on a Connection Machine CM-2 with 32K processors also shows good results.", mykey = "topology kankanhalli parallel" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Boolean combinations of polygons in parallel. In Proceedings of the 1992 International Conference on Parallel Processing, volume. 17–21 Aug 1992.
BibTeX
@inproceedings{nf-bcpp-92, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", title = "Boolean Combinations of Polygons in Parallel", booktitle = "Proceedings of the 1992 International Conference on Parallel Processing", month = "17--21 Aug", year = "1992", volume = "", pages = "", fulltext = "https://wrfranklin.org/p/76-icpp92-boolean.pdf", href = "\bibhref{76-icpp92-boolean}", mykey = "chandra", keywords = "parallel computation, grids, intersection, CAD" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Edge intersection on the Hypercube computer. Information Processing Letters, 41(5):257–262, 3 April 1992.
BibTeX
@article{nf-eihc-92, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", title = "Edge Intersection on the {H}ypercube Computer", journal = "Information Processing Letters", year = "1992", volume = "41", number = "5", month = "3 April", pages = "257--262", keywords = "parallel algorithms, performance evaluation, intersection, grids", fulltext = "https://wrfranklin.org/p/68-ipl92-hypercube.pdf", mykey = "chandra", href = "\bibhref{68-ipl92-hypercube}" } -
Wm Randolph Franklin, Narayanaswami Chandrasekhar, Mohan Kankanhalli, Varol Akman, and Peter YF Wu. Efficient geometric operations for CAD. In Michael J. Wozny, Joshua U. Turner, and K. Preiss, editors, Geometric Modeling for Product Engineering, pages 485–498. Elsevier Science Publishers B.V. (North-Holland), 1990.
BibTeX
@incollection{fckaw-egoc-90, author = "Franklin, Wm Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan and Akman, Varol and Wu, Peter YF", editor = "Wozny, Michael J. and Turner, Joshua U. and Preiss, K.", title = "Efficient Geometric Operations for {CAD}", booktitle = "Geometric Modeling for Product Engineering", publisher = "Elsevier Science Publishers B.V. (North-Holland)", year = "1990", note = "Selected and expanded papers from the IFIP WG 5.2/NSF Working Conference on Geometric Modeling, Rensselaerville, USA, 18-22 September 1988", pages = "485--498", fulltext = "https://wrfranklin.org/p/58-wozny90-efficient.pdf", href = "\bibhref{58-wozny90-efficient}", mykey = "topology chandra akman kankanhalli", keywords = "intersection, CAD, grids" } -
W. Randolph Franklin, Narayanaswami Chandrasekhar, and Mohan Kankanhalli. Parallel algorithms for geometric computing. In Final Program, SIAM Conference on Geometric Design, A17. 6–10 Nov 1989. (abstract only).
BibTeX
@InProceedings{fck-pagc-siam-89, author = "Franklin, W. Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan", title = "Parallel Algorithms for Geometric Computing", pages = "A17", booktitle = "Final Program, {SIAM} Conference on Geometric Design", year = "1989", month = "6--10 Nov", mykey = "chandra kankanhalli", note = "(abstract only)" } -
Wm Randolph Franklin, Mohan Kankanhalli, Chandrasekhar Narayanaswami, and Varol Akman. Efficient intersection calculations in large databases. In International Cartographic Association 14th World Conference, A–62 – A–63. Budapest, August 1989.
BibTeX
@inproceedings{f-eiclb-89, author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar and Akman, Varol", title = "Efficient Intersection Calculations in Large Databases", booktitle = "International Cartographic Association 14th World Conference", address = "Budapest", month = "August", year = "1989", pages = "A-62 -- A-63", fulltext = "https://wrfranklin.org/p/60-budapest89-efficient.pdf", href = "\bibhref{60-budapest89-efficient}", mykey = "akman chandra kankanhalli", keywords = "intersection, grids" } -
Wm Randolph Franklin, Mohan Kankanhalli, and Chandrasekhar Narayanaswami. Efficient primitive geometric operations on large databases. In Proceedings National Conference Challenge for the 1990s GIS Geographic Information Systems, 1247–1256. Ottawa, 27 February - 3 Mar 1989. Canadian Institute of Surveying and Mapping.
BibTeX
@inproceedings{fkn-epgol-89, author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar", title = "Efficient Primitive Geometric Operations on Large Databases", booktitle = "Proceedings National Conference Challenge for the 1990s {GIS} Geographic Information Systems", address = "Ottawa", organization = "Canadian Institute of Surveying and Mapping", month = "27 February - 3 Mar", year = "1989", pages = "1247--1256", mykey = "geometry kankanhalli chandra", fulltext = "https://wrfranklin.org/p/59-ottawa89-efficient.pdf", href = "\bibhref{59-ottawa89-efficient}", keywords = "intersection, CAD, grids" } -
Wm Randolph Franklin. Efficient polyhedron intersection and union. In Proc. Graphics Interface, 73–80. Toronto, 1982.
BibTeX
@inproceedings{f-epiu-82, author = "Franklin, Wm Randolph", title = "Efficient polyhedron intersection and union", booktitle = "Proc. Graphics Interface", pages = "73-80", address = "Toronto", year = "1982", fulltext = "https://wrfranklin.org/p/15-gi82-xsect.pdf", href = "\bibhref{15-gi82-xsect}", mykey = "topology", keywords = "intersection, CAD" }
More info: Unite Circles
Perimeter and area of the union of circles
This is a variation of the above theme: to find mass properties of the union of many circles. For i.i.d. circles, the expected time is linear in the number of circles, regardless of the number of intersections. The algorithm is not statistical, but is exact up to the machine's numerical precision.
A test implementation taking cubic time is included, for circles of identical radii.
More info: Octrees
Octree creation
Forming an octree from the bottom up by combining individual voxels has several advantages over top-down construction. Publications include:
-
Wm Randolph Franklin and Varol Akman. Building an octree from a set of parallelepipeds. IEEE Computer Graphics and Applications, 5(10):58–64, October 1985.
BibTeX
@article{fa-bospj-85, author = "Franklin, Wm Randolph and Akman, Varol", title = "Building an Octree from a Set of Parallelepipeds", journal = "IEEE Computer Graphics and Applications", month = "October", year = "1985", volume = "5", number = "10", pages = "58-64", fulltext = "https://wrfranklin.org/p/40-cga85-octree.pdf", href = "\bibhref{40-cga85-octree}", mykey = "akman", succeeds = "fa-bospi-85", keywords = "computer graphics, oct trees" } -
Wm Randolph Franklin and Varol Akman. Building an octree from a set of parallelepipeds. In Graphics Interface. 1985.
BibTeX
@inproceedings{fa-bospi-85, author = "Franklin, Wm Randolph and Akman, Varol", title = "Building an Octree from a Set of Parallelepipeds", booktitle = "Graphics Interface", year = "1985", precedes = "fa-bospj-85", keywords = "computer graphics, oct trees, CAD", fulltext = "https://wrfranklin.org/p/29-gi85-building.pdf", mykey = "akman", href = "\bibhref{29-gi85-building}" } -
Wm Randolph Franklin and Varol Akman. Octree data structures and creation by stacking. In Nadia Magenat-Thalmann, editor, Computer Generated Images, State of the Art. Springer-Verlag, 1985.
BibTeX
@incollection{fa-odscs-85, author = "Franklin, Wm Randolph and Akman, Varol", editor = "Magenat-Thalmann, Nadia", title = "Octree Data Structures and Creation by Stacking", booktitle = "Computer Generated Images, State of the Art", publisher = "Springer-Verlag", year = "1985", fulltext = "https://wrfranklin.org/p/39-cgi85-octree-stack.pdf", href = "\bibhref{39-cgi85-octree-stack}", mykey = "akman", keywords = "computer graphics, oct trees" } -
Varol Akman and Wm Randolph Franklin. Representing objects as rays, or how to pile up an octree? Computers and Graphics, 13(3):373–379, 1989.
BibTeX
@article{af-rorhp-89, author = "Akman, Varol and Franklin, Wm Randolph", title = "Representing Objects as Rays, or How to Pile up an Octree?", journal = "Computers and Graphics", volume = "13", number = "3", year = "1989", pages = "373--379", fulltext = "https://wrfranklin.org/p/64-cg89-rays.pdf", href = "\bibhref{64-cg89-rays}", mykey = "akman", keywords = "oct trees, measure, polyhedra, rays" } -
Varol Akman and Wm Randolph Franklin. Ray representation for k-d trees. Pattern Recognition Letters, pages 315–320, November 1989.
BibTeX
@article{af-rrkt-89, author = "Akman, Varol and Franklin, Wm Randolph", title = "Ray Representation for K-d Trees", journal = "Pattern Recognition Letters", month = "November", year = "1989", pages = "315--320", fulltext = "https://wrfranklin.org/p/66-prl89-ray.pdf", href = "\bibhref{66-prl89-ray}", mykey = "akman", keywords = "oct trees, measure, rays" }
Edge intersection
- 2D edge intersection in expected time linear in the input plus output size (1978). This is a subproblem of most of the other algorithms. The algorithm is input-sensitive, but has been shown to be fast for a wide range of very uneven real data, including edges of a nonuniform grid, edge on a USGS Digital Line Graph, and edges of rectangles in an integrated circuit design. This algorithm's design, a uniform grid, illustrates a longterm theme of the research. Since most data's spatial density varies, the obvious optimization is to adapt the grid to the data's varying density. That is wrong, repeat wrong. First, it is ugly. Second, it is unnecessary, both theoretically and practically. Theoretically, if the data's density variation is limited, then the mean times still hold, i.e., linear in the size of the input plus output. Second, this behavior has been observed in practice. Why is there not even a log factor in the time? Sorting an objects into a grid cell takes constant time. That is a more powerful operation than the binary decision that is the basis of many time analyses, such as sorting, that produce a log factor.
- Red-blue edge intersection: Given a set of red edges and a set of blue edges, determine only the intersections of a red and a blue edge, in expected time linear in the size of the input plus the size of the output. Note that there may be a quadratic number of red-red and blue-blue intersections, but only a linear number of red-blue intersections, the time should be linear. This was implemented as part of the planar graph overlay. Red-blue edge intersection illustrates the strength of these input-sensitive techniques. SFAIK, the best worst-case algorithm requires time linear in the number of red-red intersections.
Misc papers
-
Varol Akman, A. Arslan, W. Randolph Franklin, and P. J. W. ten Hagen. Implementing a topological picturebook. In Proc. 13th IMACS World Congress on Computation and Applied Maths. Dublin, 1991.
BibTeX
@InProceedings{akman-dublin, author = "Akman, Varol and Arslan, A. and Franklin, W. Randolph and ten {H}agen, P. J. W.", title = "Implementing a Topological Picturebook", booktitle = "Proc. 13th IMACS World Congress on Computation and Applied Maths", year = "1991", address = "Dublin", mykey = "akman" } -
Varol Akman, D. Ede, W. Randolph Franklin, and P. J. W. ten Hagen. Mental models of force and motion. In Okyay Kaynak, editor, Proc. IEEE International Workshop on Intelligent Motion Control, volume 1, 153–158. Bogazici University, Istanbul, 20-22 August 1990. IEEE Press. Catalog No. 90TH0272-5.
BibTeX
@InProceedings{akman-mental, author = "Akman, Varol and Ede, D. and Franklin, W. Randolph and ten {H}agen, P. J. W.", Editor = "Kaynak, Okyay", title = "Mental Models of Force and Motion", booktitle = "Proc. {IEEE} International Workshop on Intelligent Motion Control", Address = "Bogazici University, Istanbul", volume = "1", year = "1990", Month = "20-22 August", pages = "153--158", Publisher = "IEEE Press. Catalog No. 90TH0272-5", mykey = "akman" } -
Varol Akman, W. Randolph Franklin, and B. Veth. Design systems with common sense. In PJW ten Hagen and P. Veerkamp, editors, Proceedings of the Third Eurographics Workshop on Intelligent CAD Systems: Practical Experience and Evaluation, 317–322. Texel, the Netherlands, 3-7 Apr 1989. Springer–Verlag.
BibTeX
@inproceedings{akman-design-89, author = "Akman, Varol and Franklin, W. Randolph and Veth, B.", editor = "ten Hagen, PJW and Veerkamp, P.", title = "Design Systems with Common Sense", booktitle = "Proceedings of the Third Eurographics Workshop on Intelligent CAD Systems: Practical Experience and Evaluation", month = "3-7 Apr", year = "1989", pages = "317--322", address = "Texel, the Netherlands", publisher = "Springer--Verlag", mykey = "akman" } -
Wm Randolph Franklin and V. Akman. A workbench to compute unobstructed shortest paths in three-space. In Proc. 1st Internat. Conf. Indust. Applied Math., 1–38. Paris, France, 1987.
BibTeX
@inproceedings{fa-wcusp-87, author = "Franklin, Wm Randolph and Akman, V.", title = "A workbench to compute unobstructed shortest paths in three-space", booktitle = "Proc. 1st Internat. Conf. Indust. Applied Math.", address = "Paris, France", year = "1987", pages = "1--38", oldlabel = "geom-1319", fulltext = "https://wrfranklin.org/p/36-siam87-shortest.pdf", href = "\bibhref{36-siam87-shortest}", mykey = "akman pathplan", keywords = "motion planning" } -
Varol Akman and W. Randolph Franklin. Locus techniques for shortest path problems in robotics. In IFAC Symposium on Robot Control (SYSROCO'85). Barcelona, 1986.
BibTeX
@incollection{akman-barcelona-86, author = "Akman, Varol and Franklin, W. Randolph", title = "Locus Techniques for Shortest Path Problems in Robotics", booktitle = "IFAC Symposium on Robot Control (SYSROCO'85)", address = "Barcelona", year = "1986", fulltext = "https://wrfranklin.org/p/35-sysroco85-locus.pdf", href = "\bibhref{35-sysroco85-locus}", mykey = "akman pathplan" } -
Varol Akman and Wm Randolph Franklin. On the question `is $\sum _1^n \sqrt a_i\le L ?$'. EATCS Bulletin, pages 16–20, February 1986.
BibTeX
@article{af-oqiss-86, author = "Akman, Varol and Franklin, Wm Randolph", title = "On the Question `Is {$\sum\_1^n \sqrt{a\_i}\le L ?$}'", journal = "EATCS Bulletin", number = "28", month = "February", year = "1986", pages = "16--20", fulltext = "https://wrfranklin.org/p/38-eatcs86-question.pdf", href = "\bibhref{38-eatcs86-question}", mykey = "akman", keywords = "motion planning" } -
Wm Randolph Franklin and Varol Akman. Reconstructing visible regions from visible segments. BIT, 26:430–441, 1986.
BibTeX
@article{fa-rvrvs-86, author = "Franklin, Wm Randolph and Akman, Varol", title = "Reconstructing Visible Regions From Visible Segments", journal = "BIT", volume = "26", pages = "430--441", year = "1986", fulltext = "https://wrfranklin.org/p/30-bit86-reconstruct.pdf", href = "\bibhref{30-bit86-reconstruct}", mykey = "akman", keywords = "computer graphics, hidden line/surface elimination" } -
Wm Randolph Franklin and Varol Akman. Shortest paths in 3-space, Voronoi diagrams with barriers, and related complexity and algebraic issues. In Proceedings of the NATO Advanced Study Institute on Fundamental Algorithms for Computer Graphics, volume 17 of NATO ASI Series F, pages 895–917. Springer-Verlag, Ilkley, Yorkshire, England, 30 March – 12 April 1985.
BibTeX
@incollection{fa-sp3sv-85, author = "Franklin, Wm Randolph and Akman, Varol", title = "Shortest Paths in 3-Space, {V}oronoi Diagrams with Barriers, and Related Complexity and Algebraic Issues", booktitle = "Proceedings of the {NATO} Advanced Study Institute on Fundamental Algorithms for Computer Graphics", address = "Ilkley, Yorkshire, England", month = "30 March -- 12 April", year = "1985", publisher = "Springer-Verlag", series = "{NATO} {ASI} Series F", volume = "17", pages = "895--917", fulltext = "https://wrfranklin.org/p/31-nato85-shortest.pdf", href = "\bibhref{31-nato85-shortest}", mykey = "akman pathplan", keywords = "motion planning" } -
Wm Randolph Franklin, Varol Akman, and Colin Verrilli. Voronoi diagrams with barriers and on polyhedra for minimal path planning. Visual Comput., 1(2):133–150, October 1985.
BibTeX
@article{fav-vdbpm-85, author = "Franklin, Wm Randolph and Akman, Varol and Verrilli, Colin", title = "Voronoi diagrams with barriers and on polyhedra for minimal path planning", journal = "Visual Comput.", volume = "1", number = "2", month = "October", year = "1985", pages = "133--150", oldlabel = "geom-1246", fulltext = "https://wrfranklin.org/p/18-vc85-voronoi.pdf", href = "\bibhref{18-vc85-voronoi}", mykey = "akman pathplan", keywords = "robotics, planar partitions, motion planning, Voronoi diagrams" } -
Varol Akman and W. Randolph Franklin. Partitioning the space to calculate shortest paths to any goal around polyhedral obstacles. In Proceedings of ROBEXS'85, the First Annual Workshop on Robotics and Expert Systems. NASA/Johnson Space Center, 27–28 June 1985.
BibTeX
@inproceedings{akman-robexs-85, author = "Akman, Varol and Franklin, W. Randolph", title = "Partitioning the Space to Calculate Shortest Paths to any Goal Around Polyhedral Obstacles", booktitle = "Proceedings of ROBEXS'85, the First Annual Workshop on Robotics and Expert Systems", address = "NASA/Johnson Space Center", month = "27--28 June", year = "1985", fulltext = "https://wrfranklin.org/p/32-robexs85-shortest.pdf", href = "\bibhref{32-robexs85-shortest}", mykey = "pathplan akman" } -
Wm Randolph Franklin and Varol Akman. Shortest paths between source and goal points located on/around a convex polyhedron. In 22nd Annual Allerton Conference on Communication, Control, and Computing. Urbana, Illinois, USA, 3–5 October 1984.
BibTeX
@inproceedings{fa-spsgo-84, author = "Franklin, Wm Randolph and Akman, Varol", title = "Shortest Paths Between Source and Goal Points Located On/Around a Convex Polyhedron", booktitle = "22nd Annual Allerton Conference on Communication, Control, and Computing", month = "3--5 October", year = "1984", address = "Urbana, Illinois, USA", fulltext = "https://wrfranklin.org/p/26-allerton84-shortest.pdf", href = "\bibhref{26-allerton84-shortest}", mykey = "akman pathplan", keywords = "motion planning" } -
W. Randolph Franklin. A simpler iterative solution to the Towers of Hanoi problem. SIGPLAN Notices, 19(8):87–88, August 1984.
BibTeX
@article{wrf-sigplan-84, author = "Franklin, W. Randolph", title = "A Simpler Iterative Solution to the {T}owers of {H}anoi Problem", journal = "SIGPLAN Notices", volume = "19", number = "8", month = "August", year = "1984", pages = "87--88", fulltext = "https://wrfranklin.org/p/28-sigplan84-hanoi.pdf", href = "\bibhref{28-sigplan84-hanoi}" } -
W. Randolph Franklin. Software engineering reasons for vlsi design methodology. In IEEE Computer Society Workshop Report: VLSI and Software Engineering Workshop, pages 86–89. Port Chester, NY, USA, 4–6 October 1982.
BibTeX
@incollection{wrf-vlsi-82, author = "Franklin, W. Randolph", title = "Software Engineering Reasons for VLSI Design Methodology", booktitle = "IEEE Computer Society Workshop Report: VLSI and Software Engineering Workshop", month = "4--6 October", year = "1982", address = "Port Chester, NY, USA", pages = "86--89", fulltext = "https://wrfranklin.org/p/21-portchester82-vlsi.pdf", href = "\bibhref{21-portchester82-vlsi}" } -
G. Wazzan, W. Randolph Franklin, W. R. Spillers, A. Greenwood, T. F. Gantry, and H. Chu. Simulation of buried power transmission systems: some computer graphics options. Computers and Graphics, 6(1):7–14, 1982.
BibTeX
@article{wrf-cg-82, author = "Wazzan, G. and Franklin, W. Randolph and Spillers, W. R. and Greenwood, A. and Gantry, T. F. and Chu, H.", title = "Simulation of Buried Power Transmission Systems: Some Computer Graphics Options", journal = "Computers and Graphics", volume = "6", number = "1", year = "1982", pages = "7--14", fulltext = "https://wrfranklin.org/p/12-cg82-buried-power.pdf", href = "\bibhref{12-cg82-buried-power}" } -
Wm Randolph Franklin. 3-D geometric databases using hierarchies of inscribing boxes. In Proceedings of the 7th Canadian Man-Computer Conference, 173–180. Waterloo, Ontario, Canada, 10–12 June 1981.
BibTeX
@inproceedings{f-3gduh-81, author = "Franklin, Wm Randolph", title = "3-{D} Geometric Databases Using Hierarchies of Inscribing Boxes", booktitle = "Proceedings of the 7th Canadian Man-Computer Conference", month = "10--12 June", year = "1981", address = "Waterloo, Ontario, Canada", pages = "173--180", fulltext = "https://wrfranklin.org/p/10-waterloo81-inscribing.pdf", href = "\bibhref{10-waterloo81-inscribing}", keywords = "computer graphics, CAD" } -
W. Randolph Franklin and Alan H. Barr. Faster calculation of superquadric shapes. IEEE Computer Graphics and Applications, 1(3):41–47, July 1981.
BibTeX
@article{wrf-cga-81, author = "Franklin, W. Randolph and Barr, Alan H.", title = "Faster Calculation of Superquadric Shapes", journal = "IEEE Computer Graphics and Applications", volume = "1", number = "3", month = "July", year = "1981", pages = "41--47", fulltext = "https://wrfranklin.org/p/11-cga81-superquadrics.pdf", href = "\bibhref{11-cga81-superquadrics}" } -
Wm Randolph Franklin. Evaluation of algorithms to display vector plots on raster devices. Computer Graphics and Image Processing, 11(4):377–397, December 1979.
BibTeX
@article{f-eadvp-79, author = "Franklin, Wm Randolph", title = "Evaluation of Algorithms to Display Vector Plots on Raster Devices", journal = "Computer Graphics and Image Processing", volume = "11", number = "4", month = "December", year = "1979", pages = "377--397", keywords = "computer graphics, CAD, discrete geometry" } -
W. Randolph Franklin. Applications of geometry. In Kenneth H Rosen, editor, Handbook of Discrete and Combinatorial Mathematics, chapter 13.8, pages 867–888. CRC Press, 2000.
BibTeX
@InCollection{wrf-crc00, author = "Franklin, W. Randolph", editor = "Rosen, Kenneth H", title = "Applications of Geometry", booktitle = "Handbook of Discrete and Combinatorial Mathematics", pages = "867-888", publisher = "{CRC} Press", year = "2000", chapter = "13.8" } -
W. Randolph Franklin. Software aspects of business graphics. Computers and Graphics, 1983. (invited paper).
BibTeX
@article{wrf-business-83, author = "Franklin, W. Randolph", title = "Software Aspects of Business Graphics", journal = "Computers and Graphics", volume = "7", number = "1", year = "1983", fulltext = "https://wrfranklin.org/p/20-cag83-swaspects.pdf", href = "\bibhref{20-cag83-swaspects}", note = "(invited paper)" } -
William G. Nisen and W. Randolph Franklin. The maturation of computer graphics. ICP Interface Manufacturing and Engineering, 3(4):5–11, 1978.
BibTeX
@article{nisen-maturation-78, author = "Nisen, William G. and Franklin, W. Randolph", title = "The Maturation of Computer Graphics", journal = "ICP Interface Manufacturing and Engineering", volume = "3", number = "4", year = "1978", pages = "5--11", fulltext = "https://wrfranklin.org/p/2-nisen78-maturation.pdf", href = "\bibhref{2-nisen78-maturation}" }
Other research topics
This section presents research that is neither computational cartography nor computational geometry.
More info: Expert System Sensitivity Analysis
Expert system sensitivity analysis
In the 1980s we applied sensitivity analysis from software engineering to expert systems. The titles include:
-
W. Randolph Franklin, Rahul Bansal, and Elissa Gilbert. Sensitivity analysis of expert systems. In Uma G. Gupta, editor, Validating and Verifying Knowledge-Based Systems, pages 347–355. IEEE Computer Society Press, 1991.
BibTeX
@Incollection{wrf-gupta, author = "Franklin, W. Randolph and Bansal, Rahul and Gilbert, Elissa", editor = "Gupta, Uma G.", title = "Sensitivity Analysis of Expert Systems", booktitle = "Validating and Verifying Knowledge-Based Systems", publisher = "IEEE Computer Society Press", year = "1991", pages = "347--355", fulltext = "https://wrfranklin.org/p/51-vv91-sensitivity-es.pdf", href = "\bibhref{51-vv91-sensitivity-es}" } -
W. Randolph Franklin, Rahul Bansal, Elissa Gilbert, and Gautam Shroff. Debugging and tracing expert systems. In Benn R. Konsynski, editor, Proceeding of the 21st International Hawaii International Conference on System Sciences, volume III, 159–167. Kona, Hawaii, January 1988.
BibTeX
@inproceedings{wrf-hawaii-88, author = "Franklin, W. Randolph and Bansal, Rahul and Gilbert, Elissa and Shroff, Gautam", editor = "Konsynski, Benn R.", title = "Debugging and Tracing Expert Systems", booktitle = "Proceeding of the 21st International Hawaii International Conference on System Sciences", volume = "III", address = "Kona, Hawaii", month = "January", year = "1988", pages = "159--167", fulltext = "https://wrfranklin.org/p/48-hawaii88-debuges.pdf", href = "\bibhref{48-hawaii88-debuges}" }
More info: Non Geometric Data Structures Algorithms
Non-geometric data structures and algorithms
Here are some algorithms and data structures that are neither geometric nor cartographic. The titles include:
-
W. Randolph Franklin. On an improved algorithm for decentralized extrema finding. Comm. ACM, 25(5):336–337, May 1982.
BibTeX
@article{wrf-cacm-82, author = "Franklin, W. Randolph", title = "On an Improved Algorithm for Decentralized Extrema Finding", journal = "Comm. ACM", volume = "25", number = "5", month = "May", year = "1982", pages = "336--337", fulltext = "https://wrfranklin.org/p/14-cacm82-ring.pdf", href = "\bibhref{14-cacm82-ring}" } -
W. Randolph Franklin. Padded lists—set operations in $O(log log N)$ time. Information Processing Letters, 9(4):161–166, November 1979.
BibTeX
@article{wrf-ipl-79, author = "Franklin, W. Randolph", title = "Padded Lists---Set Operations in {$O(log log N)$} Time", journal = "Information Processing Letters", volume = "9", number = "4", month = "November", year = "1979", pages = "161--166", fulltext = "https://wrfranklin.org/p/3-ipl79-padded.pdf", href = "\bibhref{3-ipl79-padded}" }
Open topics
Students looking to work with me should read this separate page; its table of contents is below.
More info: Old Program Solicitations
Old program solicitations
Here are some solicitations and planning documents I wrote while at NSF from 2000 to 2003. They include:
- NSF01-111 and NSF02-155 Computational Algorithms and Representations for Geometric Objects (CARGO). (with B Mann and D Cochran).
- GeoSpatial Terrain Analysis and Representations (Geo*), ''(with D Cochran)'',
- Computational and Geometric Cartography.
Short notes
Here are short notes on various topics more-or-less research-related, but not about my research.
- Bresenham Circle And Line Drawing
- Polygon Equation Does the (piecewise straight border) line of a polygon have an equation, as a circle has the equation x'^2^'+y'^2^'=1?
- OpenGL Summary
- NTSC and Other TV Formats
- Portability and Standards
- Journals Are Obsolescent
- Efficient Programming
- Splines
- More short notes that haven't yet been transferred to this wiki.
No publications match your search. Try another word or clear the search.