## Smoothing Imprecise 1.5D Terrains

A 1.5D terrain is an x-monotone polyline with n vertices. An imprecise 1.5D terrain is a 1.5D terrain with a y-interval at each vertex, rather than a fixed y-coordinate. A realization of an imprecise terrain is a sequence of n y-coordinates, one for each interval, such that each y-coordinate is within its corresponding interval. For certain applications in terrain analysis, it is important to be able to find a realization of an imprecise terrain that is smooth. In this paper we model smoothness by considering the change in slope between consecutive edges of the terrain. The goal is to find a realization of the terrain where the maximum slope change is minimized. We present an exact algorithm that runs in *O*(*n*^{2}) time.

, We study optimization problems for polyhedral terrains in the presence of data imprecision. An imprecise terrain is given by a triangulated point set where the height component of the vertices is specified by an interval of possible values. We restrict ourselves to terrains with a one-dimensional projection, usually referred to as 1.5-dimensional terrains, where an imprecise terrain is given by an x-monotone polyline, and the y-coordinate of each vertex is not fixed but only constrained to a given interval. Motivated mainly by applications in terrain analysis, in this paper we study five different optimization measures related to obtaining smooth terrains, for the 1.5-dimensional case. In particular, we present exact algorithms to minimize and maximize the total turning angle, as well as to minimize the maximum slope change. Furthermore, we also give approximation algorithms to minimize the largest turning angle and to maximize the smallest turning angle.

keywords: Computational Geometry, Geographical Information Analysis, Data Imprecision, Terrains

### Journal Article (peer-reviewed)

Chris Gray, Maarten Löffler, Rodrigo I. Silveira

Smoothing Imprecise 1.5D Terrains

International Journal of Computational Geometry and Applications

20, 4, 381–414, 2010

### Conference Proceedings (peer-reviewed)

Chris Gray, Maarten Löffler, Rodrigo I. Silveira

Smoothing Imprecise 1.5D Terrains

Proc. 6th Workshop on Approximation and Online Algorithms

LNCS 5426, 214–226, 2009

### Conference Proceedings (peer-reviewed)

Chris Gray, Maarten Löffler, Rodrigo I. Silveira

Minimizing Slope Change in Imprecise 1.5D terrains

Proc. 21th Canadian Conference on Computational Geometry

55–58, 2009

### Workshop or Poster (weakly reviewed)

Chris Gray, Maarten Löffler, Rodrigo I. Silveira

Smoothing Imprecise 1-Dimensional Terrains

Proc. 24th European Workshop on Computational Geometry

141–144, 2008

### Technical Report (not reviewed)

Chris Gray, Maarten Löffler, Rodrigo I. Silveira

Smoothing Imprecise 1.5D Terrains

UU-CS-2008-036, 2008

back to list