Terrain: elevation generally.
Ever more data available, e.g., SAR
More processing power
Applications: visibility, mobility, ...
Complicated nonlinear relations (drainage)...
Induce deep (but solvable) math problems in representation
I.e., nice mix of theory and applications
NSF/DARPA: CARGO
DARPA/DSO: GEO* (proposed)
US Army Topographic Engineering Center
NIMA
Inadequacy of current systems when playing wargames.
Piecewise triangular approx to surface.
Complicated data structure
Independent of coordinate system (good).
I implemented first TIN in GIS, in 1973.
Simple
Dependent on coordinate system (bad).
We'll use this format for rest of talk.
Not differentiable many times.
Maybe not continuous (cliffs).
Long range correlations (river basins).
Scale variance (rock has finite strength).
Heterogeneity...
Many local maxima; few local minima (above sea level). -- lakes.
Nevertheless, 2D sampled data set will have local minima.
Earth vs moon terrain.
Fourier series
Wavelets
Fractals
Fourier series are good for representing electrical signals because the physics matches the math.
Truncating a series representing a signal produces another legal signal, the low-pass filter of the original.
Truncating a Fourier series representing terrain produces something that is not real terrain.
Too continuous
Too many local minina
Also a linear combo of a basis set.
Local support - changing one coefficient changes only a local region (good).
Can represent discontinuities (depending on basis set) (good).
Truncating series still produces illegal terrain (bad).
I cannot understand why anyone thinks that they look realistic.
Unless you add so many extras (heterogeneity, erosion, ...) that the original fractals seem less important.
Enough degrees of freedom can make (almost) any representation work.
Ptolemaic epicycles were as accurate as Keplerian ellipses.
However... what's natural?
We could formally ask about best algorithms for
compression,
visibility
Nonlinear
The formative agent (on earth) is water erosion.
Also uplift, downcut, etc.
We do lose the ability to form a linear combo of a set of basis
functions.
There may be several correlated layers of data for the same surface.
E.g.: elevation and slope.
Q: Why store slope explicitly?
A: Computation on demand is error-prone.
If each layer is compressed separately, they become inconsistent.
That's worse than being inaccurate.
These are from a commercial mapping product.
Users of commercial GIS packages think that these problems
are natural.
aka data fusion
The same data may be available from different sources,
... at different resolutions, with varying accuracies.
E.g., elevations from...
Combine them, to create one layer, plus error bars.
The proper data representation can make difficult problems vanish.
E.g., we want to interpolate contour lines thru some data.
The obvious method is to trace each contour line thru the grid cells, independently of its neighbors.
However, the distance between the lines is not smooth. The lines might even cross.
Solution: Interpolate a surface from the data. Then trace the contour lines on it.
Important operation, given increasing data.
Not yet true that storage is big and cheap enough.
Earth at 1 meter resolution: 5x1016 posts.
PDAs have severely restricted power and resource bounds
Lossy compression is probably fine.
Error Metric:
RMSE too simplistic.
Rather: effect of errors on derived properties, such as visibility.
How much can each possible observer see?
Assume two points on the moon's surface want to communicate.
No ionosphere to reflect radio.
No stable satellite orbits.
Obvious solutions:
Fiber, or
Relay towers
What, specifically, can a particular observer see?
Small changes in the input cause large changes in the input.
The previous beautiful image is partly (mostly?) fiction.
However certain regions are definitely hidden, and others are definitely visible.
Find them.
Note the nonlinearity: visibility is a step function.
If...
The input elevations are noisy, and
The output visibilities are very sensitive to the input,
Then...
A much quicker, less accurate, computation might produce just as good output.
A serious quantitative speed increase will translate into a qualitative improvement in what can be done.
Red side places observers to cover as much terrain as possible.
Blue side, knowing the red observers, finds areas guaranteed to be hidden.
Visibility is multidimensional:
Observer height, target height, radius of interest, number of test samples used, ...
How visibility index depends on height:
Can the function be simplified?
Interplay between theoreticians and applications (c.f. physics)
Algorithm and data structure design principles:
Things we know that are not so (e.g., inefficiency of partitioning before compression)
Interplay between different formats