(under construction)

Terrain representation and operation is my prime current research theme. The various words are defined as follows.

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.

Eleven PhD students (7 currently employed at a college), and 61 masters students have been graduated under my advisement.

Portions of this material are based upon work supported by the National Science Foundation under Grants ENG-7908139, ECS-8021504, ECS-8351942, CCF-9102553, CCF-0306502, and DMS-0327634, by DARPA/DSO under the GeoStar program, and by IBM, Sun Microsystems, and Schlumberger--Doll Research.

Here is my research Strategy in more detail.

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.

Computational Cartography Research

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

.......................................More info.

Alternate Terrain Reps

This project 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.

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.

.......................................More info.

Multiobserver 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 before, 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.

.......................................More info.

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

.......................................More info.

Overlaying Two Maps

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 subtask is to locate all the points of each map in a specific polygon of the other, which is a useful application in its own right. 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.

.......................................More info.

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

.......................................More info.

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. TIN operates by repeating the following steps:

1. Find the point farthest from the current TIN.
2. Insert it into the TIN.

Therefore, at any stage, TIN has identified, in some sense, the most important points on the terrain.

On a 32-bit PC, arrays of up to 10800x10800 posts can be processed.

.......................................More info.

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

.......................................More info.

Computational Geometry Research

Fundamentals

Here are pages on

1. PNPOLY, an 8-line program for determining point inclusion in a polygon,
2. the uniform grid data structure, for efficiently culling likely intersections in E² and E³,
3. local data structures for polyhedra, which simplify many operations, such as determination of the mass properties of boolean combinations of objects.
4. why raster graphics is harder than vector graphics.

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. Local topological properties of polyhedra,
7. Polygon properties calculated from the vertex neighborhoods,
8. Rays - new representation for polygons and polyhedra.
9. Problems with raster graphics algorithms,
10. Cartographic errors symptomatic of underlying algebra problems,
11. Efficient rotation of an object.

.......................................More info.

Connected Components in E³

Connect 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).

.......................................More info.

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.

.......................................More info.

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

.......................................More info.

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)

.......................................More info.

UNION2, UNION3, and Boolean Operations and Their Mass Properties

Here are various algorithms and demo implementations for processing large numbers of objects, such as for finding mass properties of the union of sets of polyhedra, typically in linear time. There is also a program for computing the volume and area of the union of up to 20,000,000 cubes on a dual xeon workstation in one hour. 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.

.......................................More info.

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)

.......................................More info.

Misc Geometry 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)

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

.......................................More info.

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

.......................................More info.

Program Solicitations and PI Advice

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, and
4. Proposal Writers Cheatsheet.

.......................................More info.

Short Notes

Here are short notes on various topics.

Bresenham Circle And Line Drawing

Polygon Equation

Does the (piecewise straight border) line of a polygon have an equation, as a circle has the equation x²+y²=1?

OpenGL Summary

NTSC and Other TV Formats

Portability and Standards

Journals Are Obsolescent

More short notes

that haven't yet been transferred to this wiki.

Conferences And Journals in GIS and graphics (very incomplete)

listed here just so that there will be a link.

Data Compression Refs (very incomplete)

Web Site Tools

Student Collaborators

61 Masters and 11 doctoral graduates have worked with me.

.......................................More info.

New Topics

1. Ideas Feb 2007
2. Unite Circles - find the perimeter length and area of the union of a large number of circles. This is being extended to E³.
3. Spheres Union Area

<< | Research Page List | Strategy >>