1.  Recent research

1.1  2010 ICA Sensors WS, 2010 ICSE

1.2  Autocarto 2010, ACM SIGSPATIAL GIS 2010

1.3  2010 FWCG, 2010 DARPA GRID2 WS

1.4  2010 HIS 2010 ICPMG

1.5  Parallel volumes, FWCG2009

1.6  ACM SIGSPATIAL GIS2009, FWCG2008

1.7  ACMGIS 2008

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

GeoStar

This recent major theme was a DARPA-funded project for representing and operating on terrain, that is, elevation. 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.

Titles include:

1. Two novel surface representation techniques
2. Tradeoffs when multiple observer siting on large terrain cells
3. Alternative sculpting hypotheses for terrain data compression
4. Compressing terrain datasets using segmentation
5. Terrain representation using tessellation of irregular planar tiles
6. Multiple observer siting on a compressed terrain
7. An improved LLL algorithm
8. Surface compression using over-determined Laplacian approximation
9. Path planning on lossily compressed terrain
10. Smugglers and border guards - the GeoStar project at RPI
11. Drainage network and watershed reconstruction on simplified terrain
12. Approximating terrain with over-determined Laplacian PDEs
13. Slope accuracy and path planning on compressed terrain
14. Progressive transmission of lossily compressed terrain
15. Efficient viewshed computation on terrain in external memory
16. Path planning on complex terrain
17. Operating on large geometric datasets
18. Parallel ODETLAP for terrain compression and reconstruction
19. Evaluating hydrology preservation of simplified terrain representations
20. Compressing terrain elevation datasets
21. Parallel terrain compression and reconstruction
22. Representation, compression and progressive transmission of digital terrain data using over-determined Laplacian partial differential equations
23. Evaluating and compressing hydrology on simplified terrain
24. Path planning and slope representation on compressed terrain

Some of its themes are broken out in the following sections.

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 10000x10000 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.

Titles include:

1. Terrain elevation data structure operations (with M Gousie),
2. Computational and geometric cartography,
3. Geospatial terrain: algorithms and representations,
4. Mathematical issues in terrain representatio
5. Automatic extraction of topographic features using adaptive triangular meshes (with H Pedrini and WR Schwartz),
6. Applications of analytical cartography,
7. Elevation data operations
8. Lossy compression of elevation data (with A Said), and
9. Compressing elevation data.

Multi-observer siting

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 quadi-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. Titles include:

1. Efficient multiple observer siting on large terrain cells (with C Vogt),
2. Siting observers on terrain,
3. Higher isn't necessarily better: visibility algorithms and experiments, (with CK Ray), and
4. Approximating visibility.

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). Titles include:

1. Augmenting grid-based contours to improve thin plate DEM generation, (with MB Gousie),
2. Converting elevation contours to a grid, (with MB Gousie),
3. Constructing a DEM from grid-based data by computing intermediate contours, (with MB Gousie).
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.

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.

Titles include:

1. OVERPROP - Calculating areas of map overlay polygons without calculating the overlay, (with V Sivaswami),
2. Calculating the area of overlaid polygons without constructing the overlay, (with V Sivaswami, D Sun, M Kankanhalli and C Narayanaswami),
3. Map overlay area animation and parallel simulation,
4. Calculating map overlay polygon~ areas without explicitly calculating the polygons - implementation, (and)
5. A Simplified map overlay algorithm.

Logic programming for map overlay

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

1. A Logic programming approach to cartographic map overlay, (with PYF Wu),
2. A Polygon overlay system in prolog, (with PYF Wu),
3. Experiences with using prolog for geometry, (with M Nichols, S Samaddar and PYF Wu)',
4. Geometry in prolog, (with PYF Wu, S Samaddar and M Nichols),
5. Prolog and geometry projects, (with PYF Wu, S Samaddar and M Nichols),
6. Computational geometry in Prolog, and
7. Polygon overlay in Prolog, (PYF Wu).

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, arrays of up to 10800x10800 posts can be processed. Therefore it also does not require that the points first be externally sorted.

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. Titles include:

1. Program translates statistics into 3-D color map of Europe,
2. Prism - A prism plotting program, and
3. 3-D graphic display of discrete spatial data by prism maps, (with HR Lewis).

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. Observations in support of automation with GPR,
2. On the possible role(s) of a university consortium for geographic information and analysis. (with the UCGIA Steering Committee),
3. Tutorial on curve fitting for GIS, and
4. Computer systems and low level data structures for GIS

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

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 E² and E³. 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.

Titles include:

1. Geometric computing and the uniform grid data technique (with V Akman, M Kankanhalli and C Narayanaswam),
2. Uniform grids: A technique for intersection detection on serial and parallel machines (with C Narayanaswami, M Kankanhalli, D Sun, MC Zhou, and PYF Wu),
3. Efficiency of uniform grids for intersection detection on serial and parallel machines (with N Chandrasekhar, M Kankanhalli, M Seshan, and V Akman),
4. Fast intersection detection on serial and parallel machines using the uniform grid technique (with N Chandrasekhar, M Kankanhalli, and V Akman), and
5. Adaptive grids for geometric operations.
6. Problems with raster graphics algorithms,
7. Cartographic errors symptomatic of underlying algebra problems,
8. Efficient rotation of an object.

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.

Titles include:

1. Local topological properties of polyhedra,
2. Polygon properties calculated from the vertex neighborhoods,
3. Rays - new representation for polygons and polyhedra.

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. Titles include:

1. Connected Components on 1000x1000x1000 Datasets (with EN Landis).
2. Cracking, damage and fracture in four dimensions, (with EN Landis, T Zhang, EN Nagy and G Nagy),
3. 3D analysis of tomographic images, (with E Nagy, T Zhang, G Nagy and E Landis),
4. CONNECT - find 3D connected components, and
5. Volume and surface area distributions of cracks in concrete, (with G Nagy, T Zhang, E Landis, E Nagy and D Keane).

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³ 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.) Titles include:

1. Parallel object-space hidden surface removal, (with M Kankanhalli),
2. A Linear time exact hidden surface algorithm,
3. Adaptive grid for polyhedral visibility in object space, (with V Akman),
4. A simple and efficient haloed line algorithm for hidden line elimination, (with V Akman),
5. An exact hidden sphere algorithm that operates in linear time,
6. A linear time exact hidden surface algorithm, and
7. Combinatorics of hidden surface algorithms.

Nearest points in E² and E³

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

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³ 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. Titles include:

1. Nearpt3 - Nearest point query on 184M points in E³ with a uniform grid

All near point pairs in E³

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

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

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. Titles include:

1. Volumes From Overlaying 3-D Triangulations in Parallel, (with M Kankanhalli)

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.

Titles include:

1. Determination of mass properties of polygonal CSG objects in parallel, (with C Narayanaswami),
2. Analysis of mass properties of the union of millions of polygedra,
3. Mass properties of the union of millions of identical cubes,
4. Area and perimeter computation of the union of a set of iso-rectangles in parallel, (with M Kankanhalli),
5. Boolean combinations of polygons in parallel, (with C Narayanaswami),
6. Edge intersection on the hypercube computer, (with C Narayanaswami),
7. Determination of mass properties of polygonal CSG objects in parallel, (with C Narayanaswami),
8. Efficient geometric operations for CAD, (with N Chandrasekhar, M Kankanhalli, V Akman and PYF Wu),
9. Parallel algorithms for geometric computing, (with N Chandrasekhar andM Kankanhalli),
10. Efficient intersection calculations in large databases, (with M Kankanhalli C Narayanaswami and V Akman)
11. Efficient primitive geometric operations on large databases, (with M Kankanhalli and C Narayanaswami), and
12. Efficient polyhedron intersection and union.

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.

Octree creation

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

1. Building an octree from a set of parallelepipeds (with V Akman),
2. Octree data structures and creation by stacking (with V Akman),
3. Representing objects as rays, or how to pile up an octree? (with V Akman), and
4. Ray representation for k-d trees, (with V Akman)

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.

Misc papers

1. Implementing a topological picturebook (with V Akman, A Arslan and P J W ten Hagen),
2. Mental models of force and motion (with V Akman, D Ede and PJW ten Hagen),
3. Design systems with common sense (with V Akman and B Veth),
4. A workbench to compute unobstructed shortest paths in three-space (with V Akman),
5. Locus techniques for shortest path problems in robotics (with V Akman),
6. On the question "is sum₁ⁿ sqrt{a_i}<= l " ? (with V Akman),
7. Reconstructing visible regions from visible segments (with V Akman),
8. Shortest paths in 3-space, Voronoi diagrams with barriers, and related complexity and algebraic issues (with V Akman),
9. Voronoi diagrams with barriers and on polyhedra for minimal path planning (with V Akman and C Verrilli),
10. Partitioning the space to calculate shortest paths to any goal around polyhedral obstacles (with V Akman),
11. Shortest paths between source and goal points located on/around a convex polyhedron. (with V Akman),
12. A simpler iterative solution to the Towers of Hanoi problem,
13. Software engineering reasons for vlsi design methodology,
14. Simulation of buried power transmission systems: Some computer graphics options (with G Wazzan, W R Spillers, A Greenwood, TF Gantry and H Chu)
15. 3-D geometric databases using hierarchies of inscribing boxes,
16. Faster calculation of superquadric shapes (with AH Barr),
17. Evaluation of algorithms to display vector plots on raster devices,
18. Applications of geometry,
19. Software aspects of business graphics, (and)
20. The maturation of computer graphics (with WG Nisen)

4.  Other research topics

Expert system sensitivity analysis

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

1. Sensitivity Analysis of Expert Systems
2. Debugging and Tracing Expert Systems

Non-geometric data structures and algorithms

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

1. On an Improved Algorithm for Decentralized Extrema Finding
2. Padded Lists---Set Operations in O(log log N) Time

5.  Misc topics

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.

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 x²+y²=1?
3. OpenGL Summary
4. NTSC and Other TV Formats
5. Portability and Standards
6. Journals Are Obsolescent
7. Efficient Programming
8. More short notes that haven't yet been transferred to this wiki.

Proposal writers cheat sheet

Workshop organizers cheat sheet

Software notes and reviews

Usage notes and recommendations on various programs (not mine):

6.  Open topics

7.  All pages in this Research group

¹ (Merriam-Webster dictionary) ⇑

² The American Heritage® Book of English Usage ⇑

³ Cutler, Zimmie, Franklin. NSF CMMI-0835762: CDI-Type I: Fundamental Terrain Representations and Operations ⇑

<< | Research Page List | GeoStar >>