Smoothing Imprecise 1.5D Terrains

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

Research output: Book/ReportReportAcademic


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.
Original languageEnglish
Place of PublicationUtrecht
PublisherUU BETA ICS Departement Informatica
Publication statusPublished - 2008

Publication series

NameTechnical Report Series
PublisherUU Beta ICS Departement Informatica
ISSN (Print)0924-3275




Dive into the research topics of 'Smoothing Imprecise 1.5D Terrains'. Together they form a unique fingerprint.

Cite this