Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Triangulation-Based L1-fitting of Terrain Surfaces



Javier Bernal, Christoph J. Witzgall


Given a planar triangulation, the goal is to select elevations at its vertices so that resulting piecewise-linear triangulated surface approximates specified elevations using the L1-norm as the primary measure-of-fit. Several suboptimal algorithms relating to that problem have been devised and implemented, and are described here, as part of TIN prototype software for terrain modeling in the context of distributed simulation as well as elevation data editing. L1-approximation acts as a median filter and thus provides advantages for bare earth representation. For added flexibility, a sign-oriented scaling scheme has been developed, which generalizes standard norm-based measures-of-fit. L1-approximation is either tackled directly or by iterating suitably weighted L2-approximations. Numerical experiments are reported.
- 6346
Report Number


bare earth, distributed simulation, L-<sub>1</sub>-approximation, L<sub>2</sub>-approximation, linear programming, median filter, terrain surface modeling, TIN, triangulation


Bernal, J. and Witzgall, C. (1999), Triangulation-Based L<sub>1</sub>-fitting of Terrain Surfaces, - 6346, National Institute of Standards and Technology, Gaithersburg, MD, [online], (Accessed July 18, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created June 1, 1999, Updated November 10, 2018