3 Prof: Wm Randolph Franklin

Name

Wm. Randolph Franklin

Affiliation

ECSE Dept. & CS Dept.

Office

JEC 6026

Phone

276-6077

WWW Home Page

http://www.ecse.rpi.edu/Homepages/wrf/

Email

wrf@ecse.rpi.edu (preferred way to reach me)

It's more reliable to send email for me only to ecse, even though I have accounts on other machines, and may send mail from them. These other machines are down sometimes, and may not forward mail to where I will see it.

If I don't answer your email in two days, then send it again.

Secretary:

Audrey Hayner, JEC 6012
ahayner@ecse.rpi.edu, (518) 276-6019

Paper Mail Address

ECSE Dept., 6026 JEC
Rensselaer Polytechnic Institute
Troy, New York 12180-3590
USA

Office Hours

Initially M-R 4:30-6 unless there is a departmental seminar or meeting, or otherwise indicated. Also, I remain after class to answer questions. You may also telephone to see if I am available at other times. Sometimes I may be debugging some massive program and uninterruptable.

Background

Ever since high school, I've been doing geometry, and I have been (constructively) hacking computers since 1966. I was Phdded by Hahvahd in 1978 and have been at RPI since then (except for sabbatical years) doing graphics, CAD, and geometry algorithms, and some AI. My first sabbatical was at UC Berzerkley for a year, and the second at the Dipartimento di Informatica e Scienze dell'Informazione, University of Genoa, the Dept. de Science Géodésique, Université de Laval, Quebec City, the Commonwealth Scientific and Industrial Research Organization, Canberra, and the Institute of Systems Science, National University of Singapore.

Various undergrad and grad projects are available from me. There is a more detailed research description in http://www.ecse.rpi.edu/wrf/master-list/master-list.html. It's a little old; I'll be updating it soon.

Efficiently processing large geometric databases is the goal of my research. Computational geometry, and graphics and CAD algorithms and data structures are the main themes. Various data structures for representing polygons and polyhedra, such as vertex neighborhood sets, are designed and compared. Algorithms for cartographic map overlay, polygon intersection and interference detection using set based data structures, single level grids, and no global topology, are designed and tested. All these algorithms are easily parallelizable. These algorithms are important in application areas ranging from cartography to computer aided design to interference detection in robotics and simulation of buried power transmission systems,

The underlying methodology of my work has followed a consistent theme since I was an undergrad, although the specific problems and tools used are updated regularly. Note that as hardware gets faster, then efficiency becomes more important, not less, if the algorithm will be executed often.

This consistency of direction has not prevented me from teaching courses totally unrelated to my research. This includes Software Engineering, Computer Organization and Logic Design, and Computer & Microprocessor Lab.

My geometry research has led to practical advances in several areas. Most of these have been implemented and tested on the largest available datasets. The algorithms include the following.

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

2. The uniform grid technique, which is used in many of the following applications. This idea is intended to be just sophisticated enough to solve the problem, without being so complicated that it is difficult to implement, including the messy special cases, and parallelize.

3. A linear expected-time (in the output size) parallelizable algorithm and implementation, for finding all the intersections among a large set of small edge segments. This is a common operation in many of the following problems.

4. A linear expected-time object-space hidden surface algorithm and implemented, useful in CAD.

5. A better method for creating octrees by a bottom-up approach instead of using top-down subdivision.

6. A new data structure for representing polygons and polyhedra by the location and purely local topology of each vertex. 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.

7. A map overlay algorithm for Geographic Information Systems, which can find the areas of the output regions without finding the regions themselves. The determination of the areas of all the output overlay polygons has been implemented. This is useful in interpolating data from one map to another.

8. A logic programming approach to map overlay, implemented in Prolog.

9. A parallel algorithm and implementation for determining mass properties of Constructive Solid Geometry objects.

10. An investigation into why raster graphics algorithms are so difficult. The short answer is that, in algebra, the integers are harder than the reals, not easier.

11. An algorithm for combining 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. This is now being implemented.

12. Several new algorithms and implementations relating to defending low-level avenues of approach in air defense. These involve fast approximations to the Line of Sight (LOS) problem, where we wish to compute the visibility index of every point in a Digital Elevation Model (DEM) array describing some terrain. The object is to find a set of site which, together, can cover the whole area of interest. This work has produced some counterintuitive results. For example, for some terrain, there is no significant correlation between elevation and visibility index; on the average, higher is no better for observation.

Many of these implementations are so efficient that the computation time is less than the I/O time.

All the implementations are tested on the largest datasets available. For example, the map overlay area program was tested on a map of US counties overlaid on a hydrography map. These contained over 5,000 polygons and 130,000 vertices in total. Finding edge intersections was tested on a database with 2,000,000 edges.

Future Plans

Computer hardware has advanced to the point where many of the problems in GIS are now solvable. These include processing very large databases with more complicated operations. My goal is to bring the state-of-the-art techniques from computer engineering over to this field, to solve some of their problems, and to enable them efficiently process data that would be infeasible for the to process otherwise.

Since data from other planets is now available, I'm also investigating whether terrestrial techniques, such as the Triangulated Irregular Network, would extend to describing Martian and Venusian terrain.

Line-of-sight calculation for a terrain database is a specific area in which I will be working for several years since this topic is just breaking open.

The use of Voronoi diagrams for the interpolation of values between irregularly spaced 2D points appears to be a powerful concept. However, there are unsolved problems relating to the formal properties and efficiency, which I am investigating.

More recently I'm working on compressing digital terrain elevation data with wavelet-based techniques.

For some recent papers, see ftp://ftp.cs.rpi.edu/pub/franklin/.

Other services that I provide for you

1. Bring your resume to me for suggestions. From time to time I read resumes with a view to hiring someone, so I have opinions on what makes a good resume. These opinions may vary from the Placement Office's. Sample suggestions: Explicitly mention major computer systems and packages, such as X, which you know. Don't mention your non-academic hobbies and marital status.
2. If someone sends me notice of a job opening, I mention it in class, and post it around my door, if the notice is paper, or email it to everyone, if electronic. I also put it on the WWW, in http://www.ecse.rpi.edu/Homepages/wrf/career.html.

Extra-curricular contacts

1. If you see me eating lunch in the Student Union, join me, and talk about whatever you want, such as the future of computer science.
2. Occasionally I lead hikes in the Adirondacks or Catskills. These tend to be 5-10 miles, with up to 2000 feet of climbing, i.e., easy for people in tolerable shape. No one has gotten lost yet, at least for very long. (Would I lose, permanently, a paying customer?)