Loading...

W Randolph Franklin home page
... (old version) Login


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.

1.  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 on Alternate Terrain Reps

1.1  Alternate Terrain Reps


This theme has the following goals:

  1. Study alternate terrain representations that are more compact.
  2. Since the new representations will therefore be lossy, evaluate the size / quality tradeoffs.
  3. These new representations ought to make it easier to represent legal terrain than illegal terrain.
  4. We wish to process datasets up to 50000x50000 elevation posts.
  5. With these new representations, uncompression speed is more important than compression speed.
  6. 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.)

  1. 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. (paper, talk).
  2. 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. (abstract, talk).
  3. 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. (paper, talk).
  4. 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). (abstract, talk).
  5. 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). (paper, poster).
  6. W. Randolph Franklin and Michael Gousie. Terrain Elevation Data Structure Operations. In C. Peter Keller, editor, Proceedings of the 19th International Cartographic Association Conference, pages 1011-1020, Ottawa, Aug 1999. (URL) (paper).
  7. 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. (paper).
  8. 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, Jun 2008. (paper).
  9. 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. International Society for Optical Engineering, 27 August 2007. paper 6697-15. (paper).
  10. 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). (abstract, poster).
  11. 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. International Society for Optical Engineering, 15-16 August 2006. 6313-17, Session 4. (paper).
  12. 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. (abstract, poster).
  13. W. Randolph Franklin, Metin Inanc and Zhongyi Xie. Two novel surface representation techniques. In Autocarto 2006, Vancouver Washington. Cartography and Geographic Information Society, 25-28 June 2006. (paper).
  14. W. Randolph Franklin. Applications of Analytical Cartography. Cartography and Geographic Information Systems, 27(3):225-237, 2000. (paper).
  15. W. Randolph Franklin. Compressing Elevation Data. In Fourth International Symposium on Large Spatial Databases — SSD '95, 6-9 Aug 1995. (paper).
  16. Hélio Pedrini, William Robson Schwartz and W. R. Franklin. Automatic Extraction of Topographic Features Using Adaptive Triangular Meshes. In 2001 International Conference on Image Processing (ICIP-2001), pages 732-735, Thessaloniki, Greece, 7-10 October 2001.
  17. W. Randolph Franklin and Amir Said. Lossy Compression of Elevation Data. In Seventh International Symposium on Spatial Data Handling, Delft, Aug 1996. (paper).

1.2  Parallel and distributed cartography computation

Publications include:

  1. 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. (paper, talk).
  2. 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) (paper, talk, poster).
  3. Wm Randolph Franklin. Map Overlay Area Animation and Parallel Simulation. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop, pages 200-203, July 28-August 2 1992. (paper).
  4. 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) (paper, talk, poster).

See also the parallel geometry papers below.

1.3  Hydrography, bathymetry

Publications include:

  1. Salles V. G. 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 and Didier Josselin and Danny Vandenbroucke, editor, Bridging the Geographic Information Sciences: International AGILE'2012 Conference, pages 391-407. Springer. 978-3-642-29062-6, 24-27 April 2012. Winner of the Best Paper Award (2nd place). (URL) (paper, talk).
  2. 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. (paper, talk).
  3. 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. (paper, talk).
  4. 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. (paper).
  5. 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. (paper, poster).
  6. Tsz-Yam Lau and W. Randolph Franklin. Completing fragmentary river networks via induced terrain. Cartography and Geographic Information Science, 38(2):162-174. doi: 10.1559/1523040638162, Apr 2011. (paper).
  7. 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. (paper, talk).
  8. 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). (abstract, talk).
  9. 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). (paper, talk).
  10. 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. The International Cartographic Association (ICA) Commission on Mapping from Satellite Imagery, 19 Nov 2010. (paper, talk).
  11. 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. (paper, video, talk: pptx, pdf, poster: pptx, pdf).
  12. 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) (paper, talk, poster).
  13. 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. (abstract, poster).

1.4  Erosion modeling

Publications include:

  1. 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. http://www.geocongress2012.org/. (paper).
  2. 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) (paper).
  3. 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 March 2011. (URL) (paper).
  4. Jared A. Gross, Christopher S. Stuetzle, Zhongxian Chen andBarbara 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. (paper, talk).
  5. 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). (paper, poster).
  6. 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. (paper, talk).
  7. 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). (abstract, talk).

More info on GeoStar

1.5  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:

  1. efficient hi–res visibility computation on terrain,
  2. multiple observer siting to maximize joint viewshed,
  3. ODETLAP, an extension of the Laplacian PDE to an overdetermined system of equations, which is used in many of the following results,
  4. extremely compact lossy terrain (elevation) compression,
  5. terrain compression that reconstructs slopes accurately,
  6. lossily compressed terrain supports motion-planning (path planning),
  7. path planning with sophisticated cost metric on large terrain, and
  8. a better surface fitting procedure for bathymetry data that is very unevenly spaced.

Publications on Geo* as a project include:

  1. 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) (paper, talk).

In addition many other publications listed on this page present various aspects of Geo*.

More info on Siting

1.6  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:

  1. Salles V. G. 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), 3, 2011. (paper).
  2. Salles V. G. 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. (paper).
  3. Marcus V. A. Andrade, Salles V. G. Magalhães, Mirella A. Magalhães, W. Randolph Franklin and Barbara M. Cutler. Efficient viewshed computation on terrain in external memory. Geoinformatica. doi: 10.1007/s10707-009-0100-9, 2010. (online 26 Nov 2009). (URL) (paper).
  4. 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, editor, 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) (paper, talk: ppt, pdf, poster: ppt, pdf).
  5. 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). (abstract, talk).
  6. 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). (abstract, talk, poster).
  7. 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. International Society for Optical Engineering, 27 August 2007. paper 6697-16. (paper).
  8. 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. (paper, talk).
  9. W. Randolph Franklin and Christian Vogt. Tradeoffs when multiple observer siting on large terrain cells. In Andreas Riedl and Wolfgang Kainz and Gregory Elmes, editor, Progress in Spatial Data Handling: 12th International Symposium on Spatial Data Handling, pages 845-861. Springer, 2006. ISBN 978-3-540-35588-5. (paper, talk).
  10. 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. (paper, poster).
  11. 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. (paper, talk).
  12. W. Randolph Franklin. Siting observers on terrain. In Dianne Richardson and Peter van Oosterom, editor, Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling, pages 109-120, 2002. (paper).
  13. Wm Randolph Franklin and Clark Ray. Higher isn't Necessarily Better: Visibility Algorithms and Experiments. In Thomas C. Waugh and Richard G. Healey, editor, Advances in GIS Research: Sixth International Symposium on Spatial Data Handling, pages 751-770, Edinburgh. The International Geographical Union's Commission on Geographical Information Systems and The Association for Geographic Information, 5-9 Sept 1994. (paper).
  14. W. Randolph Franklin. Approximating visibility. In GIScience 2000, Savannah, Georgia, USA, 30 Oct 2000. (paper).

More info on Gridding Contours

1.7  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:

  1. 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. (paper).
  2. Michael Gousie and W. Randolph Franklin. Converting Elevation Contours to a Grid. In Eighth International Symposium on Spatial Data Handling, pages 647-656, Vancouver BC Canada, Jul 1998. (paper, talk).
  3. Michael Gousie and W. Randolph Franklin. Constructing a DEM from Grid-based Data by Computing Intermediate Contours. In Erik Hoel and Phillippe Rigaux, editor, GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, pages 71-77, New Orleans, 2003. (paper).
  4. Contours to digital elevation models: grid-based surface reconstruction methods, MB Gousie, and
  5. 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 on Overlaying Two Maps

1.8  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:

  1. Wm Randolph Franklin and Venkatesh Sivaswami. OVERPROP — Calculating Areas of Map Overlay Polygons without Calculating the Overlay. In Second National Conference on Geographic Information Systems, pages 1646-1654, Ottawa, 5-8 March 1990. (paper).
  2. Wm Randolph Franklin and Mohan S. Kankanhalli. Volumes From Overlaying 3-D Triangulations in Parallel. In D. Abel and B.C. Ooi, editor, Advances in Spatial Databases: Third Intl. Symp., SSD'93, pages 477-489. Springer-Verlag, Jun 1993. (paper).
  3. Wm Randolph Franklin. Map Overlay Area Animation and Parallel Simulation. In David H. Douglas, editor, Proceedings, SORSA'92 Symposium and Workshop, pages 200-203, July 28-August 2 1992. (paper).
  4. 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, Apr 1994. (paper).
  5. Wm Randolph Franklin. Calculating Map Overlay Polygon' Areas Without Explicitly Calculating the Polygons — Implementation. In 4th International Symposium on Spatial Data Handling, pages 151-160, Zürich, 23-27 July 1990. (paper).
  6. Wm Randolph Franklin. A Simplified Map Overlay Algorithm. In Harvard Computer Graphics Conference, Cambridge, Mass, USA, 31 July - 4 August 1983. (paper).

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.

1.9  Logic programming for map overlay


In the late 1980s, we investigated using declarative, rather than procedural, programming techniques for map overlay. Titles include:

  1. Invalid BibTex Entry in BibSummary! /wrf.bib wf-lpacm-90
  2. 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, pages 97-106, Baltimore, Maryland, 29 March - 3 April 1987. (paper).
  3. 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, pages 26-31, Vancouver, BC, 26-30 May 1986.
  4. 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, pages 71-78, Apr 1986. (paper).
  5. Wm Randolph Franklin, Peter Y.F. Wu, Sumitro Samaddar and Margaret Nichols. Prolog and Geometry Projects. IEEE Computer Graphics and Applications, Nov 1986. (paper).
  6. Wm Randolph Franklin. Computational Geometry in Prolog. In Proceedings of the NATO Advanced Study Institute on Fundamental Algorithms for Computer Graphics, pages 737-749. Springer-Verlag, 30 March - 12 April 1985. (paper).
  7. Polygon overlay in Prolog, (PYF Wu).

1.10  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.

  1. 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.
  2. 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 on Prism

1.11  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:

  1. 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).
  2. W. Randolph Franklin. Prism — A Prism Plotting Program. In Allan H. Schmidt, editor, Mapping Software and Cartographic Data Bases, pages 75-79. , 1979.
  3. Wm Randolph Franklin and Harry R. Lewis. 3-D Graphic Display of Discrete Spatial Data By Prism Maps. In Proc. SIGGRAPH'78, pages 70-75, Aug 1978. (paper).

More info on General Cartography

1.12  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:

  1. 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.
  2. 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. (paper).
  3. Wm Randolph Franklin. Computer Systems and Low Level Data Structures for GIS. In David Maguire and David Rhind and Mike Goodchild, editor, GIS: Principles and Practice, pages 215-225. Longman Higher Education and Reference, 1991. (paper).
  4. 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).

2.  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 on Fundamentals

2.1  Fundamentals


Here are pages on

  1. 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.
  2. The uniform grid data structure, for efficiently culling likely intersections in E2 and E3. 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.
  3. Why raster graphics is harder than vector graphics. It's because integers are harder than rationals.

Publications include:

  1. W. Randolph Franklin and Barb Cutler. KNOWMESH -- Meshless geometry with knowledge representation. In DARPA GRID2 workshop, 18-19 Aug 2010. (talk).
  2. Varol Akman, Wm Randolph Franklin, Mohan Kankanhalli and Chandrasekhar Narayanaswami. Geometric Computing and the Uniform Grid Data Technique. Computer Aided Design, 21(7):410-420, 1989. (paper).
  3. 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, pages 100-109, Baltimore, Maryland, 2-7 April 1989. (paper).
  4. 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, editor, New Trends in Computer Graphics (Proc. Computer Graphics International'88), pages 288-297. Springer-Verlag, 1988. (paper).
  5. Wm Randolph Franklin. Adaptive Grids for geometric operations. Cartographica, 21(2--3):161-167, Summer - Autumn 1984. monograph 32--33. (paper).
  6. Wm Randolph Franklin. Adaptive Grids for geometric operations. In Proc. Sixth International Symposium on Automated Cartography (Auto-Carto Six), pages 230-239, Ottawa, 1983.
  7. Wm Randolph Franklin. Problems with Raster Graphics Algorithms. In L.R.A. Kessener and F.J. Peters and M.L.P. van Lierop, editor, Data Structures for Raster Graphics, proceedings of a Workshop held at Steensel, The Netherlands, June 24--28, 1985Springer-Verlag EurographicSeminars, 1986. (paper).
  8. Wm Randolph Franklin. Cartographic Errors Symptomatic of Underlying Algebra Problems. In Proc. International Symposium on Spatial Data Handling, pages 190-208, Zürich, 20-24 August 1984. (paper).
  9. Wm Randolph Franklin. Efficient Rotation of an Object. IEEE Trans. Comput., C-32(11):1064-1067, Nov 1983. (paper).

More info on Local Topology

2.2  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:

  1. Wm Randolph Franklin. Polygon properties calculated from the vertex neighborhoods. In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 110-118, 1987. (paper).
  2. Wm Randolph Franklin. RAYS — New Representation for Polygons and Polyhedra. Computer Graphics and Image Processing, 22:327-338, 1983. (paper).

2.3  Parallel and distributed geometry algorithms

  1. 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. doi: 10.1006/jpdc.1995.1076, Jun 1995. (paper).
  2. Wm Randolph Franklin and Mohan S. Kankanhalli. Volumes From Overlaying 3-D Triangulations in Parallel. In D. Abel and B.C. Ooi, editor, Advances in Spatial Databases: Third Intl. Symp., SSD'93, pages 477-489. Springer-Verlag, Jun 1993. (paper).
  3. Chandrasekhar Narayanaswami and Wm Randolph Franklin. Boolean Combinations of Polygons in Parallel. In Proceedings of the 1992 International Conference on Parallel Processing, 17-21 Aug 1992. (paper).
  4. Chandrasekhar Narayanaswami and Wm Randolph Franklin. Edge Intersection on the Hypercube Computer. Information Processing Letters, 41(5):257-262, 3 April 1992. (paper).
  5. 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. (paper).
  6. Wm Randolph Franklin and Mohan Kankanhalli. Parallel Object-Space Hidden Surface Removal. In Proceedings of SIGGRAPH'90, pages 87-94, Aug 1990. (paper).
  7. W. Randolph Franklin, Narayanaswami Chandrasekhar and Mohan Kankanhalli. Parallel Algorithms for Geometric Computing. In Final Program, SIAM Conference on Geometric Design, page A17, 6-10 Nov 1989. (abstract only).
  8. 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, pages 100-109, Baltimore, Maryland, 2-7 April 1989. (paper).
  9. 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, editor, New Trends in Computer Graphics (Proc. Computer Graphics International'88), pages 288-297. Springer-Verlag, 1988. (paper).

More info on Connected Components

2.4  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:

  1. 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). (abstract, talk).
  2. 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. (URL) (paper).
  3. 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. (paper).
  4. 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 and L.P. Cordella and G. Sannitidi Baja, editor, Visual Form 2001: 4th International Workshop on Visual Form IWVF4Springer-Verlag Heidelberg, 28-30 May 2001. (paper, poster).

2.5  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 E3 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:

  1. Wm Randolph Franklin and Mohan Kankanhalli. Parallel Object-Space Hidden Surface Removal. In Proceedings of SIGGRAPH'90, pages 87-94, Aug 1990. (paper).
  2. Wm Randolph Franklin. A linear time exact hidden surface algorithm. In Kenneth I. Joy and others, editor, Tutorial: Computer Graphics: Image Synthesis, pages 218-224. , 1988.
  3. Wm Randolph Franklin and Varol Akman. Adaptive Grid for polyhedral visibility in object space, an implementation. Computer Journal, 31(1):56-60, Feb 1988. (paper).
  4. 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. (paper).
  5. Wm Randolph Franklin. An exact hidden sphere algorithm that operates in linear time. Comput. Graph. Image Process., 15:364-379, 1981. (paper).
  6. Wm Randolph Franklin. A linear time exact hidden surface algorithm. Comput. Graph., 14(3):117-123, 1980. (paper).
  7. Wm Randolph Franklin. Combinatorics of hidden surface algorithms. . PhD thesis, Center for Research in Computing Technology, Harvard Univ., Jun 1978. (parts: 1, 2, 3, 4).

More info on Nearpt3

2.6  Nearest points in E2 and E3


This is a pair of subroutines to find nearest points in E3. 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 E2.

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 7233 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:

  1. 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. (paper, talk).
  2. 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), pages 239-242, Windsor, Ontario, 10-12 August 2005. (paper (current version), paper, talk).

More info on All Near Pairs

2.7  All near point pairs in E3


This is a program to report all pairs of points nearer than a given distance, from a fixed set of points in E3.

Sample time: Processing 20K points to report 688K pairs took 20msec CPU time, excluding I/O on a 2.8GHz machine.

2.8  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:

  1. Wm Randolph Franklin and Mohan S. Kankanhalli. Volumes From Overlaying 3-D Triangulations in Parallel. In D. Abel and B.C. Ooi, editor, Advances in Spatial Databases: Third Intl. Symp., SSD'93, pages 477-489. Springer-Verlag, Jun 1993. (paper).

More info on Union

2.9  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:

  1. 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. (paper).
  2. W. Randolph Franklin. Analysis of Mass Properties of the Union of Millions of Polyhedra. In M. L. Lucian and M. Neamtu, editor, Geometric Modeling and Computing: Seattle 2003, pages 189-202. Nashboro Press, Brentwood TN. 0-0-9728482-3-1, 2004. (paper).
  3. Wm. Randolph Franklin. Mass Properties of the Union of Millions of Identical Cubes. In Ravi Janardan and Debashish Dutta and Michiel Smid, editor, Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 329-345. American Mathematical Society, 2005. (paper, talk).
  4. 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. doi: 10.1006/jpdc.1995.1076, Jun 1995. (paper).
  5. Chandrasekhar Narayanaswami and Wm Randolph Franklin. Boolean Combinations of Polygons in Parallel. In Proceedings of the 1992 International Conference on Parallel Processing, 17-21 Aug 1992. (paper).
  6. Chandrasekhar Narayanaswami and Wm Randolph Franklin. Edge Intersection on the Hypercube Computer. Information Processing Letters, 41(5):257-262, 3 April 1992. (paper).
  7. Wm Randolph Franklin, Narayanaswami Chandrasekhar, Mohan Kankanhalli, Varol Akman and Peter YF Wu. Efficient Geometric Operations for CAD. In Michael J. Wozny and Joshua U. Turner and K. Preiss, editor, Geometric Modeling for Product Engineering, pages 485-498. Elsevier Science Publishers B.V. (North-Holland), 1990. Selected and expanded papers from the IFIP WG 5.2/NSF Working Conference on Geometric Modeling, Rensselaerville, USA, 18-22 September 1988. (paper).
  8. W. Randolph Franklin, Narayanaswami Chandrasekhar and Mohan Kankanhalli. Parallel Algorithms for Geometric Computing. In Final Program, SIAM Conference on Geometric Design, page A17, 6-10 Nov 1989. (abstract only).
  9. Wm Randolph Franklin, Mohan Kankanhalli, Chandrasekhar Narayanaswami and Varol Akman. Efficient Intersection Calculations in Large Databases. In International Cartographic Association 14th World Conference, pages A-62 - A-63, Budapest, Aug 1989. (paper).
  10. 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, pages 1247-1256, Ottawa. Canadian Institute of Surveying and Mapping, 27 February - 3 March 1989. (paper).
  11. Wm Randolph Franklin. Efficient polyhedron intersection and union. In Proc. Graphics Interface, pages 73-80, Toronto, 1982. (paper).

More info on Unite Circles

2.10  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 on Octrees

2.11  Octree creation


Forming an octree from the bottom up by combining individual voxels has several advantages over top-down construction. Publications include:

  1. Wm Randolph Franklin and Varol Akman. Building an Octree from a Set of Parallelepipeds. IEEE Computer Graphics and Applications, 5(10):58-64, Oct 1985. (paper).
  2. Wm Randolph Franklin and Varol Akman. Building an Octree from a Set of Parallelepipeds. In Graphics Interface, 1985. (paper).
  3. Wm Randolph Franklin and Varol Akman. Octree Data Structures and Creation by Stacking. In Nadia Magenat-Thalmann, editor, Computer Generated Images, State of the ArtSpringer-Verlag, 1985. (paper).
  4. 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. (paper).
  5. Varol Akman and Wm Randolph Franklin. Ray Representation for K-d Trees. Pattern Recognition Letters, Nov 1989. (paper).

2.12  Edge intersection

  1. 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.
  2. 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.

2.13  Misc papers

  1. 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.
  2. 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, pages 153-158, Bogazici University, Istanbul, 20-22 August 1990.
  3. Varol Akman, W. Randolph Franklin and B. Veth. Design Systems with Common Sense. In PJW ten Hagen and P. Veerkamp, editor, Proceedings of the Third Eurographics Workshop on Intelligent CAD Systems: Practical Experience and Evaluation, pages 317-322, Texel, the Netherlands, 3-7 Apr 1989.
  4. Wm Randolph Franklin and V. Akman. A workbench to compute unobstructed shortest paths in three-space. In Proc. 1st Internat. Conf. Indust. Applied Math., pages 1-38, Paris, France, 1987. (paper).
  5. Varol Akman and W. Randolph Franklin. Locus Techniques for Shortest Path Problems in Robotics. In IFAC Symposium on Robot Control (SYSROCO'85), 1986. (paper).
  6. Varol Akman and Wm Randolph Franklin. On the Question `Is $\sum_1^n \sqrta_i\le L ?$'. EATCS Bulletin, Feb 1986. (paper).
  7. Wm Randolph Franklin and Varol Akman. Reconstructing Visible Regions From Visible Segments. BIT, 26:430-441, 1986. (paper).
  8. 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, pages 895-917. Springer-Verlag, 30 March - 12 April 1985. (paper).
  9. 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, Oct 1985. (paper).
  10. 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. (paper).
  11. 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. (paper).
  12. W. Randolph Franklin. A Simpler Iterative Solution to the Towers of Hanoi Problem. SIGPLAN Notices, 19(8):87-88, Aug 1984. (paper).
  13. W. Randolph Franklin. Software Engineering Reasons for VLSI Design Methodology. In IEEE Computer Society Workshop Report: VLSI and Software Engineering Workshop, pages 86-89. , 4-6 October 1982. (paper).
  14. 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. (paper).
  15. Wm Randolph Franklin. 3-D Geometric Databases Using Hierarchies of Inscribing Boxes. In Proceedings of the 7th Canadian Man-Computer Conference, pages 173-180, Waterloo, Ontario, Canada, 10-12 June 1981. (paper).
  16. W. Randolph Franklin and Alan H. Barr. Faster Calculation of Superquadric Shapes. IEEE Computer Graphics and Applications, 1(3):41-47, Jul 1981. (paper).
  17. Wm Randolph Franklin. Evaluation of Algorithms to Display Vector Plots on Raster Devices. Computer Graphics and Image Processing, 11(4):377-397, Dec 1979.
  18. 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.
  19. W. Randolph Franklin. Software Aspects of Business Graphics. Computers and Graphics, 7(1), 1983. (invited paper). (paper).
  20. William G. Nisen and W. Randolph Franklin. The Maturation of Computer Graphics. ICP Interface Manufacturing and Engineering, 3(4):5-11, 1978. (paper).

3.  Other research topics

This section presents research that is neither computational cartography nor computational geometry.

3.1  Expert system sensitivity analysis


In the 1980s we applied sensitivity analysis from software engineering to expert systems. The titles include:

  1. 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. (paper).
  2. 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, pages 159-167, Kona, Hawaii, Jan 1988. (paper).

3.2  Non-geometric data structures and algorithms


Here are some algorithms and data structures that are neither geometric nor cartographic. The titles include:

  1. W. Randolph Franklin. On an Improved Algorithm for Decentralized Extrema Finding. Comm. ACM, 25(5):336-337, May 1982. (paper).
  2. W. Randolph Franklin. Padded Lists—Set Operations in $O(log log N)$ Time. Information Processing Letters, 9(4):161-166, Nov 1979. (paper).

4.  Open topics

5.  Old program solicitations


Here are some solicitations and planning documents I wrote while at NSF from 2000 to 2003. They include:

  1. NSF01-111 and NSF02-155 Computational Algorithms and Representations for Geometric Objects (CARGO). (with B Mann and D Cochran).
  2. GeoSpatial Terrain Analysis and Representations (Geo*), ''(with D Cochran)'',
  3. Computational and Geometric Cartography.

6.  Short notes

Here are short notes on various topics more-or-less research-related, but not about my research.

  1. Bresenham Circle And Line Drawing
  2. Polygon Equation Does the (piecewise straight border) line of a polygon have an equation, as a circle has the equation x2+y2=1?
  3. OpenGL Summary
  4. NTSC and Other TV Formats
  5. Portability and Standards
  6. Journals Are Obsolescent
  7. Efficient Programming
  8. Splines
  9. More short notes that haven't yet been transferred to this wiki.

7.  Advice

8.  Proposal writers cheat sheet

Contents of page Proposal Writers Cheat Sheet... (hide)

  1.   1.  Proposal preparation
  2.   2.  Budget
  3.   3.  Reviewing
  4.   4.  After the decision
  5.   5.  Summary

9.  Workshop organizers cheat sheet

10.  Software notes and reviews

A separate page with usage notes and recommendations on various programs written by others.

Contents of page Software Notes... (hide)

  1.   1.  Linux
    1.   1.1  Booting with old grub
    2.   1.2  Booting with grub 2
    3.   1.3  Linux multimedia incl video
    4.   1.4  Using an ipod with linux
    5.   1.5  MS Office in linux
    6.   1.6  Ubuntu Network Remix
    7.   1.7  Encrypted partitions
    8.   1.8  Linux other
    9.   1.9  Firefox
  2.   2.  Linux virtual machine (VM) notes
  3.   3.  Converting a VM from VMWare to KVM
  4.   4.  Linux mail user agents - comparisons, advantages and problems
    1.   4.1  Kmail
    2.   4.2  Claws-mail
    3.   4.3  Evolution
    4.   4.4  Thunderbird
    5.   4.5  Gmail
    6.   4.6  Mulberry
  5.   5.  Zsh
  6.   6.  Cellphone as modem in linux
  7.   7.  Retrieving Motorola V325i cellphone addressbook with Bitpim in Linux
  8.   8.  Boot ISO image
    1.   8.1  Boot ISO image from disk (hard drive)
    2.   8.2  Boot ISO image from USB flash drive
  9.   9.  C++ Compilers
  10. 10.  Numeric and statistical computing
    1. 10.1  SW
    2. 10.2  Sparse least squares
    3. 10.3  Matlab hints
    4. 10.4  Syntax comparisons - Matlab, Mathematica, Maple
  11. 11.  Graphics and media
    1. 11.1  Big packages
    2. 11.2  Plotting (functions and data)
    3. 11.3  Drawing figures
    4. 11.4  Image format conversions
    5. 11.5  Stitching, panoramas
    6. 11.6  Cameras
    7. 11.7  Download video
    8. 11.8  Flickr from ubuntu
  12. 12.  LaTeX
    1. 12.1  Misc
    2. 12.2  LaTeX into HTML
    3. 12.3  HTML into LaTeX
    4. 12.4  XML to LaTeX or HTML
    5. 12.5  Replacements or supplements:
    6. 12.6  Fonts
    7. 12.7  Lucida fonts
  13. 13.  PDF
    1. 13.1  XML into PDF
    2. 13.2  LaTeX figures and PDF
    3. 13.3  Watermark a PDF file
    4. 13.4  Convert a directory of image files to PDF files
    5. 13.5  Crop and resize PDF pages
    6. 13.6  Combine a directory of PDF files into one file
    7. 13.7  Update PDF file metadata
    8. 13.8  PDF to RTF (good for MS Word)
    9. 13.9  Paginate a PDF file
    10. 13.10  Complete (fill in) a PDF form
    11. 13.11  Linux PDF w embedded multimedia
  14. 14.  Talk (Presentation) Slide Tools
  15. 15.  Other Words
    1. 15.1  Others' words
    2. 15.2  Speak words
  16. 16.  Geo
    1. 16.1  Major sites of information
    2. 16.2  Packages
    3. 16.3  Rendering terrain with povray
    4. 16.4  GPS, specifically Garmin 60csx
    5. 16.5  Convert gpx files to kml for Google maps
    6. 16.6  SRTM
  17. 17.  VMWare - shrink pre-allocated disk on windows client
  18. 18.  MS Windows
    1. 18.1  Retrieve passwords and activation keys
  19. 19.  Web fonts